|
DRUM >
College of Computer, Mathematical & Physical Sciences >
Computer Science >
Technical Reports from UMIACS >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1903/4299
|
| Title: | Space-Time Tradeoffs for Approximate Spherical Range Counting |
| Authors: | Arya, Sunil
Malamatos, Theocharis
Mount, David M. |
| Type: | Technical Report |
| Issue Date: | 13-Nov-2006 |
| Series/Report no.: | UM Computer Science Department
CS-TR-4842
UMIACS
UMIACS-TR-2006-57 |
| Abstract: | We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in real d-dimensional space along with a positive approximation factor eps, the goal is to preprocess the points so that, given any Euclidean ball B, we can return the number of points of any subset of S that contains all the points within a (1-eps)-factor contraction of B, but contains no points that lie outside a (1+eps)-factor expansion of B.
In many applications of range searching it is desirable to offer a tradeoff between space and query time. We present here the first such tradeoffs for approximate range counting queries. Given positive eps and a parameter g, where 2 <= g <= 1/eps, we show how to construct a data structure of space O(n g^d log(1/eps)) that allows us to answer eps-approximate spherical range counting queries in time O(log(ng) + 1/(eps g)^{d-1}). The data structure can be built in time O(n g^d log(n/eps) log(1/eps)). Here n, eps, and g are asymp... |
| URI: | http://hdl.handle.net/1903/4299 |
| Appears in Collections: | Technical Reports from UMIACS
Technical Reports of the Computer Science Department
|
Files in This Item:
| File |
Description |
Size | Format | No. of Downloads |
|---|
| tech-rept-4842.pdf | | 245Kb | Adobe PDF | 109 | View/Open |
|
Show full item record
All items in DRUM are protected by copyright, with all rights reserved.
|
