Space-Time Tradeoffs for Approximate Spherical Range Counting
| dc.contributor.author | Arya, Sunil | |
| dc.contributor.author | Malamatos, Theocharis | |
| dc.contributor.author | Mount, David M. | |
| dc.date.accessioned | 2007-02-19T19:11:10Z | |
| dc.date.available | 2007-02-19T19:11:10Z | |
| dc.date.issued | 2006-11-13 | |
| dc.description.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 asymptotic quantities, and the dimension d is assumed to be a fixed constant. At one extreme (low space), this yields a data structure of space O(n log (1/eps)) that can answer approximate range queries in time O(log n + (1/eps)^{d-1}) which, up to a factor of O(log 1/eps) in space, matches the best known result for approximate spherical range counting queries. At the other extreme (high space), it yields a data structure of space O((n/eps^d) log(1/eps)) that can answer queries in time O(log n + log 1/eps). This is the fastest known query time for this problem. Our approach is broadly based on methods developed for approximate Voronoi diagrams (AVDs), but it involves a number of significant extensions from the context of nearest neighbor searching to range searching. These include generalizing AVD node-separation properties from leaves to internal nodes of the tree and constructing efficient generator sets through a radial decomposition of space. We have also developed new arguments to analyze the time and space requirements in this more general setting. | en |
| dc.format.extent | 251014 bytes | |
| dc.format.mimetype | application/pdf | |
| dc.identifier.uri | http://hdl.handle.net/1903/4299 | |
| dc.language.iso | en_US | en |
| dc.relation.ispartofseries | UM Computer Science Department | en |
| dc.relation.ispartofseries | CS-TR-4842 | en |
| dc.relation.ispartofseries | UMIACS | en |
| dc.relation.ispartofseries | UMIACS-TR-2006-57 | en |
| dc.title | Space-Time Tradeoffs for Approximate Spherical Range Counting | en |
| dc.type | Technical Report | en |