Significant-presence range queries in categorial data

M. Berg, de, H.J. Haverkort

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

6 Citations (Scopus)


In traditional colored range-searching problems, one wants to store a set of n objects with m distinct colors for the following queries: report all colors such that there is at least one object of that color intersecting the query range. Such an object, however, could be an ‘outlier’ in its color class. Therefore we consider a variant of this problem where one has to report only those colors such that at least a fraction t of the objects of that color intersects the query range, for some parameter t. Our main results are on an approximate version of this problem, where we are also allowed to report those colors for which a fraction (1 - e)t intersects the query range, for some fixed e> 0. We present efficient data structures for such queries with orthogonal query ranges in sets of colored points, and for point stabbing queries in sets of colored rectangles.
Original languageEnglish
Title of host publicationAlgorithms and Data Structures (Proceedings 8th International Workshop, WADS 2003, Ottawa, Canada, July 30-August 1, 2003)
EditorsF.K.H.A. Dehne, F.R. Sack, M.H.M. Smid
Place of PublicationBerlin
ISBN (Print)3-540-40545-3
Publication statusPublished - 2003

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Significant-presence range queries in categorial data'. Together they form a unique fingerprint.

Cite this