The cell probe complexity of dynamic range counting

ABSTRACT

In this paper we develop a new technique for proving lower bounds on the update time and query time of dynamic data structures in the cell probe model. With this technique, we prove the highest lower bound to date for any explicit problem, namely a lower bound of t_q=Ω((lg n/lg(wt_u))²). Here n is the number of update operations, w the cell size, t_q the query time and t_u the update time. In the most natural setting of cell size w=Θ(lg n), this gives a lower bound of t_q=Ω((lg n/lg lg n)²) for any polylogarithmic update time. This bound is almost a quadratic improvement over the highest previous lower bound of Ω(lg n), due to Patrascu and Demaine [SICOMP'06].

We prove our lower bound for the fundamental problem of weighted orthogonal range counting. In this problem, we are to support insertions of two-dimensional points, each assigned a Θ(lg n)-bit integer weight. A query to this problem is specified by a point q=(x,y), and the goal is to report the sum of the weights assigned to the points dominated by q, where a point (x',y') is dominated by q if x' ≤ x and y' ≤ y. In addition to being the highest cell probe lower bound to date, our lower bound is also tight for data structures with update time t_u = Ω(lg^2+εn), where ε>0 is an arbitrarily small constant.

References

1. A. Fiat and A. Shamir. How to find a battleship. Networks, 19:361--371, 1989.
2. M. Fredman and M. Saks. The cell probe complexity of dynamic data structures. In Proc. 21st ACM Symposium on Theory of Computation, pages 345--354, 1989.
3. A. G. Jørgensen and K. G. Larsen. Range selection and median: Tight cell probe lower bounds and adaptive data structures. In Proc. 22nd ACM/SIAM Symposium on Discrete Algorithms, pages 805--813, 2011.
4. J. Matousek. Geometric Discrepancy. Springer, 1999.
5. R. Panigrahy, K. Talwar, and U. Wieder. Lower bounds on near neighbor search via metric expansion. In Proc. 51st IEEE Symposium on Foundations of Computer Science, pages 805--814, 2010.
6. M. Patrascu. Lower bounds for 2-dimensional range counting. In Proc. 39th ACM Symposium on Theory of Computation, pages 40--46, 2007.
7. M. Patrascu. Unifying the landscape of cell-probe lower bounds. In Proc. 49th IEEE Symposium on Foundations of Computer Science, pages 434--443, 2008.
8. M. Patrascu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd ACM Symposium on Theory of Computation, pages 603--610, 2010.
9. M. Pv atrac scu and E. D. Demaine. Logarithmic lower bounds in the cell-probe model. SIAM Journal on Computing, 35:932--963, April 2006.
10. M. Patrascu and M. Thorup. Don't rush into a union: Take time to find your roots. In Proc. 43rd ACM Symposium on Theory of Computation, 2011. To appear. See also arXiv:1102.1783.
11. A. C.-C. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proc. 18th IEEE Symposium on Foundations of Computer Science, pages 222--227, 1977.
12. A. C. C. Yao. Should tables be sorted? Journal of the ACM, 28(3):615--628, 1981.

Index Terms

• Information systems

  • Data management systems

    • Data structures

  • Information storage systems

    • Record storage systems

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management