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