Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries

Abstract : We present history-independent alternatives to a B-tree, the primary indexing data structure used in databases. A data structure is history independent (HI) if it is impossible to deduce any information by examining the bit representation of the data structure that is not already available through the API. We show how to build a history-independent cache-oblivious B-tree and a history-independent external-memory skip list. One of the main contributions is a data structure we build on the way—a history-independent packed-memory array (PMA). The PMA supports efficient range queries, one of the most important operations for answering database queries. Our HI PMA matches the asymptotic bounds of prior non-HI packed-memory arrays and sparse tables. Specifically, a PMA maintains a dynamic set of elements in sorted order in a linear-sized array. Inserts and deletes take an amortized O(log^2 N) element moves with high probability. Simple experiments with our implementation of HI PMAs corroborate our theoretical analysis. Comparisons to regular PMAs give preliminary indications that the practical cost of adding history-independence is not too large. Our HI cache-oblivious B-tree bounds match those of prior non-* HI cache-oblivious B-trees. Searches take O(log_B N) I/Os; inserts and deletes take O((log^2 N)/B + log_B N) amortized I/Os with high probability; and range queries returning k elements take O(log_B N + k/B) I/Os. Our HI external-memory skip list achieves optimal bounds with high probability, analogous to in-memory skip lists: O(log_B N) I/Os for point queries and amortized O(log_B N) I/Os for in-serts/deletes. Range queries returning k elements run in O(log_B N + k/B) I/Os. In contrast, the best possible high-probability bounds for inserting into the folklore B-skip list, which promotes elements with probability 1/B, is just Θ(log N) I/Os. This is no better than the bounds one gets from running an in-memory skip list in external memory.
Type de document :
Communication dans un congrès
Principle of Database Systems (PODS 2016), 2016, San Francisco, United States. Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 〈10.1145/2902251.2902276〉
Liste complète des métadonnées

Littérature citée [63 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01326312
Contributeur : Equipe Roma <>
Soumis le : vendredi 3 juin 2016 - 14:16:17
Dernière modification le : vendredi 20 avril 2018 - 15:44:27

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michael Bender, Jonathan Berry, Rob Johnson, Thomas Kroeger, Samuel Mccauley, et al.. Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries. Principle of Database Systems (PODS 2016), 2016, San Francisco, United States. Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 〈10.1145/2902251.2902276〉. 〈hal-01326312〉

Partager

Métriques

Consultations de la notice

161

Téléchargements de fichiers

166