Lecture Notes in Computer Science, 2002, Volume 2461/2002, 243-264, DOI: 10.1007/3-540-45749-6_6

Range Searching in Categorical Data: Colored Range Searching on Grid

Pankaj K. Agarwal, Sathish Govindarajan and S. Muthukrishnan

View Related Documents

Abstract

Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and spatial databases. Given a set of geometric objects, a typical range query asks for reporting all the objects that intersect a query object. However in many applications, including databases and network routing, input objects are partitioned into categories and a query asks for reporting the set of categories of objects that intersect a query object. Moreover in many such applications, objects lie on a grid. We abstract the category of an object by associating a color with each object. In this paper, we present efficient data structures for solving the colored range-searching and colored point-enclosure problem on U x U grid. Our data structures use near- linear space and answer a query in O(log log U +k) time, where k is the output size. As far as we know, this is the first result on colored range-searching for objects lying on a grid.
Research by the first two authors is supported by NSF under grants CCR-00-86013 EIA-98-70724, EIA-01-31905, and CCR-97-32787, and by a grant from the U.S.- Israel Binational Science Foundation. Part of this work was done when the second author was visiting the third author at DIMACS.

Fulltext Preview

Image of the first page of the fulltext document