Significant-presence range queries in categorial data

M. Berg, de, H.J. Haverkort

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

7 Citaten (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.
Originele taal-2Engels
TitelAlgorithms and Data Structures (Proceedings 8th International Workshop, WADS 2003, Ottawa, Canada, July 30-August 1, 2003)
RedacteurenF.K.H.A. Dehne, F.R. Sack, M.H.M. Smid
Plaats van productieBerlin
ISBN van geprinte versie3-540-40545-3
StatusGepubliceerd - 2003

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


Duik in de onderzoeksthema's van 'Significant-presence range queries in categorial data'. Samen vormen ze een unieke vingerafdruk.

Citeer dit