Lower bounds for 2-dimensional range counting

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) 2 ) per operation. This is close to the O(lg 2 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].

Authors

• Mihai Patrascu

Keywords

• cell-probe complexity
• lower bounds
• orthogonal range queries