Anti-Persistence on Persistent Storage: History-Independent Sparse Tables and Dictionaries
Summary: Provide history-independent (HI) cache-oblivious B-tree, external-memory skip list, and a HI packed-memory array (PMA) that prevents history leakage from on-disk layout while supporting efficient range queries. HI PMA: O(log^2 N) element moves w.h.p.; HI B-tree: O(log_B N) searches and amortized O(log_B^2 N+log_B N) updates; HI skip list: O(log_B N) I/Os — practical overhead small. (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
No non-self incoming citations found for this paper in this database.
Authors
- 1. Michael A. Bender
- 2. Jonathan W. Berry
- 3. Rob Johnson
- 4. Thomas M. Kroeger
- 5. Samuel McCauley
- 6. Cynthia A. Phillips
- 7. Bertrand Simon
- 8. Shikha Singh
- 9. David Zage
Incoming Citations (Sorted by Pagerank)
Showing 3 of 3 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,917 | Layered List Labeling | 2024 | PODS | 4.1905499e-05 |
| 10,920 | History-Independent Dynamic Partitioning: Achieving Operation-Order Privacy in Ordered Data Structures | 2024 | PODS | 4.1905499e-05 |
| 11,772 | Write-Optimized Skip Lists | 2017 | PODS | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,113 | Cache-Oblivious String B-trees | 2006 | PODS | 0.00013885755 |
| 1,747 | Good Worst-Case Algorithms for Inserting and Deleting Records in Dense Sequential Files | 1986 | SIGMOD | 0.0001068666 |
| 3,365 | An Adaptive Packed-Memory Array | 2006 | PODS | 7.1675736e-05 |
Previous
Page 1 / 1
Next