|
|
| |
| 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
|
Universität Bonn -> Institut für Informatik -> Abteilung V | |