Computer Science – Data Structures and Algorithms
Scientific paper
2009-06-15
Computer Science
Data Structures and Algorithms
13 pages, 1 figure
Scientific paper
We present new data structures for approximately counting the number of points in orthogonal range. There is a deterministic linear space data structure that supports updates in O(1) time and approximates the number of elements in a 1-D range up to an additive term $k^{1/c}$ in $O(\log \log U\cdot\log \log n)$ time, where $k$ is the number of elements in the answer, $U$ is the size of the universe and $c$ is an arbitrary fixed constant. We can estimate the number of points in a two-dimensional orthogonal range up to an additive term $ k^{\rho}$ in $O(\log \log U+ (1/\rho)\log\log n)$ time for any $\rho>0$. We can estimate the number of points in a three-dimensional orthogonal range up to an additive term $k^{\rho}$ in $O(\log \log U + (\log\log n)^3+ (3^v)\log\log n)$ time for $v=\log \frac{1}{\rho}/\log {3/2}+2$.
No associations
LandOfFree
Data Structures for Approximate 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 Data Structures for Approximate Range Counting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data Structures for Approximate Range Counting will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-316648