The cell probe complexity of dynamic range counting

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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} = O m e g a ((l g n / l g (w t_{u}))^{2})

. 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 = T h e t a (l g n)

, this gives a lower bound of

t_{q} = O m e g a ((l g n / l g l g n)^{2})

for any polylogarithmic update time. This bound is almost a quadratic improvement over the highest previous lower bound of

O m e g a (l g n)

, due to Pv{a}trac{s}cu and Demaine [SICOMP'06]. We prove the 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

T h e t a (l g 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^{'} l e q x

and

y^{'} l e q y

. In addition to being the highest cell probe lower bound to date, the lower bound is also tight for data structures with update time

t_{u} = O m e g a (l g^{2 + e p s} n)

, where

e p s > 0

is an arbitrarily small constant.

Recommendations

Cited in

(34)

This page was built for publication: The cell probe complexity of dynamic range counting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5415467)