EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

History-Independent Dynamic Partitioning with Applications to B-Trees, Skip Lists and Fusion Trees

Michael Bender, Martin Farach-Colton, Michael Goodrich, Hanna Komlos

ACM Transactions on Database Systems · 31.03.2027 · 52 (1) · 1-30

DOI: 10.1145/3810240 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Database Systems, online erschienen am 14.11.2026. Verfasst von Michael Bender und 3 weiteren Autor:innen. Die Arbeit nennt 76 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Division of Computing and Communication Foundations, Graduate Fellowships for Science, Technology, Engineering, and Mathematics Diversity.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

A data structure is history independent if its internal representation reveals nothing about the history of operations beyond what can be determined from the current contents of the data structure. History independence is typically viewed as a security or privacy guarantee, with the intent being to minimize risks incurred by a security breach or audit. Despite widespread advances in history independence, there is an important data-structural primitive that previous work has been unable to replace with an equivalent history-independent alternative— dynamic partitioning . In dynamic partitioning, we are given a dynamic set S of ordered elements and a size-parameter B , and the objective is to maintain a partition of S into ordered groups, each of size Θ (B) . Dynamic partitioning is important throughout computer science, with applications to B-tree rebalancing, write-optimized dictionaries, log-structured merge trees, other external-memory indexes, geometric and spatial data structures, cache-oblivious data structures, and order-maintenance data structures. The lack of a history-independent dynamic-partitioning primitive has meant that designers of history-independent data structures have had to resort to complex alternatives. In this article, we achieve history-independent dynamic partitioning. Our algorithm runs asymptotically optimally against an oblivious adversary, processing each insert/delete with O(1) operations in expectation and O(B log N / loglog N) with high probability in set size N . We also use our dynamic partitioning scheme to build a history-independent B -tree, history-independent fusion tree, and external-memory skip list.

Förderung

  • Division of Computing and Communication Foundations
  • Graduate Fellowships for Science, Technology, Engineering, and Mathematics Diversity

Zitieren

APA

Bender, M., Farach-Colton, M., Goodrich, M., & Komlos, H. (2027). History-Independent Dynamic Partitioning with Applications to B-Trees, Skip Lists and Fusion Trees. ACM Transactions on Database Systems, 52(1), 1-30. https://doi.org/10.1145/3810240

Vancouver

Bender M, Farach-Colton M, Goodrich M, Komlos H. History-Independent Dynamic Partitioning with Applications to B-Trees, Skip Lists and Fusion Trees. ACM Transactions on Database Systems. 2027;52(1):1-30. doi:10.1145/3810240

BibTeX
@article{Bender2027,
  author = {Bender, Michael and Farach-Colton, Martin and Goodrich, Michael and Komlos, Hanna},
  title = {History-Independent Dynamic Partitioning with Applications to B-Trees, Skip Lists and Fusion Trees},
  journal = {ACM Transactions on Database Systems},
  year = {2027},
  volume = {52},
  number = {1},
  pages = {1--30},
  doi = {10.1145/3810240}
}
Kostenlos starten →