Space-time tradeoffs for approximate spherical range counting
Sunil Arya, Theocharis Malamatos, David M. Mount · University Libraries (University of Maryland) · 2005
Abstract We present space-time tradeoffs for approximate spherical range counting queries. Given a set S of n data points in Rdalong with a positive approximation factor ffl, 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- ffl)-factor contraction ofB, but contains no points that lie outside a (1 + ffl)-factor expansion of B.In many applications of range searching it is desirable to offer a tradeoff between space and query time. Wepresent here the first such tradeoffs for approximate range counting queries. Given 0 < ffl < = 1/2 and a parameterfl, where 2 < = fl < = 1/ffl, we show how to construct a data structure of space O(nfld log(1/ffl)) that allows us toanswer ffl-approximate spherical range counting queries in time O(log(nfl) + 1/(fflfl)d-1). The data structure can be built in time O(nfld log(n/ffl) log(1/ffl)). Here n, ffl, and fl areasymptotic 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/ffl)) that can answer approximate range queries in time O(log n + (1/ffl)d-1) which, up to a factorof O(log 1/ffl) in space, matches the best known result