  We present data-oblivious algorithms in the external-memory model for
compaction, selection, and sorting. Motivation for such problems comes from
clients who use outsourced data storage services and wish to mask their data
access patterns. We show that compaction and selection can be done
data-obliviously using $O(N/B)$ I/Os, and sorting can be done, with a high
probability of success, using $O((N/B)\log_{M/B} (N/B))$ I/Os. Our methods use
a number of new algorithmic techniques, including data-oblivious uses of
invertible Bloom lookup tables, a butterfly-like compression network,
randomized data thinning, and "shuffle-and-deal" data perturbation. In
addition, since data-oblivious sorting is the bottleneck in the "inner loop" in
existing oblivious RAM simulations, our sorting result improves the amortized
time overhead to do oblivious RAM simulation by a logarithmic factor in the
external-memory model.
