Range searching in categorical data: Colored range searching on grid

Conference Paper

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.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Govindarajan, S; Muthukrishnan, S

Published Date

  • January 1, 2002

Published In

Volume / Issue

  • 2461 /

Start / End Page

  • 17 - 28

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540441808

International Standard Book Number 13 (ISBN-13)

  • 9783540441809

Digital Object Identifier (DOI)

  • 10.1007/3-540-45749-6_6

Citation Source

  • Scopus