Aarhus University Seal

The Cell Probe Complexity of Dynamic Range Counting

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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 tq = ((lg n/ lg(wtu))2).
Here n is the number of update operations, w the cell size, tq
the query time and tu the update time. In the most natural
setting of cell size w = (lg n), this gives a lower bound
of tq = ((lg n/ lg lg n)2) for any polylogarithmic update
time. This bound is almost a quadratic improvement over
the highest previous lower bound of (lg n), due to Pˇatra¸scu
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 as-signed 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 (x0, y0) is dominated by q if x0 x and
y0 y. In addition to being the highest cell probe lower
bound to date, our lower bound is also tight for data struc-
tures with update time tu = (lg2+" n), where " > 0 is an
arbitrarily small constant.
Original languageEnglish
Title of host publicationSTOC’12 : Proceedings of the 44th symposium on Theory of Computing
Number of pages10
PublisherAssociation for Computing Machinery
Publication year2012
ISBN (print)978-1-4503-1245-5
Publication statusPublished - 2012
Event44th ACM Symposium on Theory of Computing - New York, NY, United States
Duration: 19 May 201222 May 2012


Conference44th ACM Symposium on Theory of Computing
LandUnited States
ByNew York, NY

See relations at Aarhus University Citationformats

ID: 48580425