Computer Science – Data Structures and Algorithms
Scientific paper
2011-03-26
Computer Science
Data Structures and Algorithms
Full version of a paper appearing in 2011 ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)
Scientific paper
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.
No associations
LandOfFree
Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data-Oblivious External-Memory Algorithms for the Compaction, Selection, and Sorting of Outsourced Data will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-223684