Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data

摘要

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.