I/O-efficient data structures for colored range and prefix reporting
Kasper Green Larsen, Rasmus Pagh · 2012
Motivated by information retrieval applications, we consider the one-dimensional colored range reporting problem in rank space. The goal is to build a static data structure for sets C1,..., Cm ⊆ {1,..., σ} that supports queries of the kind: Given indices a, b, report the set ⋃ a≤i≤b Ci. We study the problem in the I/O model, and show that there exists an optimal linear-space data structure that answers queries in O(1 + k/B) I/Os, where k denotes the output size and B the disk block size in words. In fact, we obtain the same bound for the harder problem of three-sided orthogonal range reporting. In this problem, we are to preprocess a set of n two-dimensional points in rank space, such that all points inside a query rectangle of the form [x1, x2]×(−∞, y] can be reported. The best previous bounds for this problem is either O(n lg 2 B n) space and O(1 + k/B) query I/Os, or O(n) space and O(lg (h) B n + k/B) query I/Os, where lg(h)