Lower bounds for 2-dimensional range counting

ABSTRACT

Proving lower bounds for range queries has been an active topic of research since the late 70s, but so far nearly all results have been limited to the (rather restrictive) semigroup model. We consider one of the most basic range problem, orthogonal range counting in two dimensions, and show almost optimal bounds in the group model and the (holy grail) cell-probe model.

Specifically, we show the following bounds, which were known in the semigroup model, but are major improvements in the more general models:* In the group and cell-probe models, a static data structure of size n lg^O(1) n requires Omega(lg n lglg n) time per query. This is an exponential improvement over previous bounds, and matches known upper bounds.* In the group model, a dynamic data structure takes time Omega((lg n lglg n)²) per operation. This is close to the O(lg² n) upper bound, where as the previous lower bound was Omega(lg n).

Proving such (static and dynamic) bounds in the group model has been regarded as an important challenge at least since [Fredman, JACM 1982] and [Chazelle, FOCS 1986].

REFERENCES

• 1: P.K. Agarwal. Range searching. In J.E. Goodman and J. O'Rourke, editors, Handbook of Discrete and Computational Geometry (2nd edition). Chapman & Hall/CRC, 2004.
• 2: Bernard Chazelle, Lower bounds for orthogonal range searching: part II. The arithmetic model, Journal of the ACM (JACM), v.37 n.3, p.439-463, July 1990 [doi>10.1145/79147.79149]
• 3: Bernard Chazelle, Lower bounds for off-line range searching, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.733-740, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225291]
• 4: Michael L. Fredman, A Lower Bound on the Complexity of Orthogonal Range Queries, Journal of the ACM (JACM), v.28 n.4, p.696-705, Oct. 1981 [doi>10.1145/322276.322281]
• 5: Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982 [doi>10.1145/322290.322305]
• 6: M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73040]
• 7: Haripriyan Hampapuram , Michael L. Fredman, Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums, SIAM Journal on Computing, v.28 n.1, p.1-9, Feb. 1999 [doi>10.1137/S0097539795291598]
• 8: Peter Bro Miltersen , Noam Nisan , Shmuel Safra , Avi Wigderson, On data structures and asymmetric communication complexity, Journal of Computer and System Sciences, v.57 n.1, p.37-49, Aug. 1998 [doi>10.1006/jcss.1998.1577]
• 9: Mihai Patrascu , Erik D. Demaine, Logarithmic Lower Bounds in the Cell-Probe Model, SIAM Journal on Computing, v.35 n.4, p.932-963, 2006 [doi>10.1137/S0097539705447256]
• 10: Mihai Patrascu , Mikkel Thorup, Higher Lower Bounds for Near-Neighbor and Further Rich Problems, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), p.646-654, October 21-24, 2006 [doi>10.1109/FOCS.2006.35]
• 11: Mihai Pătraşcu , Mikkel Thorup, Time-space trade-offs for predecessor search, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132551]
• 12: M. Pǎtraşcu and M. Thorup. Randomization does not help searching predecessors. In Proc. 18th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 555--564, 2007.
• 13: A.C.-C. Yao. On the complexity of maintaining partial sums. SIAM Journal on Computing, 14:277--288, 1985.

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

General Terms:
Algorithms, Performance, Theory

Keywords:
cell-probe complexity, lower bounds, orthogonal range queries