Oblivious data structures

Conference Paper

We design novel, asymptotically more efficient data structures and algorithms for programs whose data access patterns exhibit some degree of predictability. To this end, we propose two novel techniques, a pointer-based technique and a locality-based technique. We show that these two techniques are powerful building blocks in making data structures and algorithms oblivious. Specifically, we apply these techniques to a broad range of commonly used data structures, including maps, sets, priority-queues, stacks, deques; and algorithms, including a memory allocator algorithm, max-flow on graphs with low doubling dimension, and shortestpath distance queries on weighted planar graphs. Our oblivious counterparts of the above outperform the best known ORAM scheme both asymptotically and in practice. Copyright is held by the owner/author(s). Publication rights licensed to ACM.

Full Text

Duke Authors

Cited Authors

  • Wang, XS; Nayak, K; Liu, C; Chan, THH; Shi, E; Stefanov, E; Huang, Y

Published Date

  • November 3, 2014

Published In

Start / End Page

  • 215 - 226

International Standard Serial Number (ISSN)

  • 1543-7221

International Standard Book Number 13 (ISBN-13)

  • 9781450329576

Digital Object Identifier (DOI)

  • 10.1145/2660267.2660314

Citation Source

  • Scopus