Charla: Efficient Range Reporting for Categorical Data

Yakov Nekrich
11 Abril, 2012 - 14:30
Auditorio DCC, 3er piso

In the colored (or categorical) range reporting problem the set of input  points is partitioned into categories and stored in a data structure; a  query asks for categories of points that belong to the query range. In this  paper we study two-dimensional colored range reporting in the external  memory model and present I/O-efficient data structures for this problem.


In particular, we describe data structures that answer three-sided colored  reporting queries in O(K/B) I/Os and two-dimensional colored reporting  queries in O(log2 logB N + K/B) I/Os when points lie on an N x N grid, K is the number of reported colors, and B is the block size. The  space usage of both data structures is close to optimal.