Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 2008 Copyright 2008 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V