TY - GEN
T1 - Range searching in categorical data
T2 - 10th Annual European Symposium on Algorithms, ESA 2002
AU - Agarwal, Pankaj K.
AU - Govindarajan, Sathish
AU - Muthukrishnan, S.
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2002.
PY - 2002
Y1 - 2002
N2 - 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 × U grid. Our data structures use near- linear space and answer a query in 0(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.
AB - 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 × U grid. Our data structures use near- linear space and answer a query in 0(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.
UR - http://www.scopus.com/inward/record.url?scp=84938097887&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84938097887&partnerID=8YFLogxK
U2 - 10.1007/3-540-45749-6_6
DO - 10.1007/3-540-45749-6_6
M3 - Conference contribution
AN - SCOPUS:84938097887
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 17
EP - 28
BT - Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
A2 - Möhring, Rolf
A2 - Raman, Rajeev
PB - Springer Verlag
Y2 - 17 September 2002 through 21 September 2002
ER -