Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 2008 Copyright 2008 Universität Bonn, Institut für Informatik, Abt. V
85290

09.05.2008

Searching for Frequent Colors in Rectangles
Marek Karpinski, Yakov Nekrich
[Download PostScript] [Download PDF]

We study a new variant of colored orthogonal range searching problem: given a query rectangle Q all colors c, such that at least a fraction τ of all points in Q are of color c, must be reported. We describe several data structures for that problem that use pseudo-linear space and answer queries in poly-logarithmic time.

Last Change: 06/09/08 at 13:44:45
 English
Universität Bonn -> Institut für Informatik -> Abteilung V