Paper Info
Title
Range Searching in Categorical Data: Colored Range Searching on Grid
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 脳 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.
Year
DOI
Venue
2002
10.1007/3-540-45749-6_6
ESA
Keywords
Field
DocType
geometric object,efficient data structure,query object,log log u,fundamental problem,u grid,categorical data,colored range searching,numerous applications area,typical range query,data structure,input object,network routing,range query,linear space,spatial database
Data structure,Combinatorics,Colored,Computer science,Linear space,Computational geometry,Range query (data structures),Range searching,Algorithm,Theoretical computer science,Spatial database,Grid
Conference
Volume
ISSN
ISBN
2461
0302-9743
3-540-44180-8
Citations 
PageRank 
References 
25
1.04
17
Authors
3
Name
Order
Citations
PageRank
Pankaj K. Agarwal15257593.81
Sathish Govindarajan211012.84
S. Muthukrishnan38025734.98