Range searching in categorical data: Colored range searching on grid

Pankaj K. Agarwal, Sathish Govindarajan, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 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.

    Original languageEnglish (US)
    Title of host publicationAlgorithms - ESA 2002 - 10th Annual European Symposium, Proceedings
    EditorsRolf Möhring, Rajeev Raman
    PublisherSpringer Verlag
    Pages17-28
    Number of pages12
    ISBN (Electronic)3540441808, 9783540441809
    DOIs
    StatePublished - 2002
    Event10th Annual European Symposium on Algorithms, ESA 2002 - Rome, Italy
    Duration: Sep 17 2002Sep 21 2002

    Publication series

    NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
    Volume2461
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other10th Annual European Symposium on Algorithms, ESA 2002
    CountryItaly
    CityRome
    Period9/17/029/21/02

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'Range searching in categorical data: Colored range searching on grid'. Together they form a unique fingerprint.

  • Cite this

    Agarwal, P. K., Govindarajan, S., & Muthukrishnan, S. (2002). Range searching in categorical data: Colored range searching on grid. In R. Möhring, & R. Raman (Eds.), Algorithms - ESA 2002 - 10th Annual European Symposium, Proceedings (pp. 17-28). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2461). Springer Verlag. https://doi.org/10.1007/3-540-45749-6_6