Computer Science – Data Structures and Algorithms
Scientific paper
2011-05-30
Computer Science
Data Structures and Algorithms
Scientific paper
In this paper we develop a new technique for proving dynamic cell probe lower bounds. With this technique, we achieve the highest lower bound to date for any explicit problem, namely a lower bound of $t_q=\Omega((\lg n/\lg(wt_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=\Theta(\lg n)$, this gives a lower bound of $t_q=\Omega((\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 $\Omega(\lg n)$, due to P\v{a}tra\c{s}cu 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 $\Theta(\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 $p=(x',y')$ is dominated by $q$ if $x' \leq x$ and $y' \leq y$. In addition to being the highest lower bound to date, our lower bound is also tight for update time $t_u = \lg^{2+\Omega(1)}n$.
No associations
LandOfFree
The Cell Probe Complexity of Dynamic Range Counting does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Cell Probe Complexity of Dynamic Range Counting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Cell Probe Complexity of Dynamic Range Counting will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-678125