Skip to content
University of Maryland LibrariesDigital Repository at the University of Maryland
    • Login
    View Item 
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    •   DRUM
    • College of Computer, Mathematical & Natural Sciences
    • Computer Science
    • Technical Reports from UMIACS
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Space-Time Tradeoffs for Approximate Spherical Range Counting

    Thumbnail
    View/Open
    tech-rept-4842.pdf (245.1Kb)
    No. of downloads: 1057

    Date
    2006-11-13
    Author
    Arya, Sunil
    Malamatos, Theocharis
    Mount, David M.
    Metadata
    Show full item record
    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.
    URI
    http://hdl.handle.net/1903/4299
    Collections
    • Technical Reports from UMIACS
    • Technical Reports of the Computer Science Department

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility
     

     

    Browse

    All of DRUMCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister
    Pages
    About DRUMAbout Download Statistics

    DRUM is brought to you by the University of Maryland Libraries
    University of Maryland, College Park, MD 20742-7011 (301)314-1328.
    Please send us your comments.
    Web Accessibility