  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 C_1,...,C_m \subseteq {1,...,sigma} that
supports queries of the kind: Given indices a,b, report the set Union_{a <= i
<= b} C_i.
  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
[x_1,x_2] x (-infinity,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)_B n is the base B logarithm
iterated h times, for any constant integer h. The previous bounds are both
achieved under the indivisibility assumption, while our solution exploits the
full capabilities of the underlying machine. Breaking the indivisibility
assumption thus provides us with cleaner and optimal bounds.
  Our results also imply an optimal solution to the following colored prefix
reporting problem. Given a set S of strings, each O(1) disk blocks in length,
and a function c: S -> 2^{1,...,sigma}, support queries of the kind: Given a
string p, report the set Union_{x in S intersection p*} c(x), where p* denotes
the set of strings with prefix p. Finally, we consider the possibility of top-k
extensions of this result, and present a simple solution in a model that allows
non-blocked I/O.
