{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:06:33Z","timestamp":1750309593793,"version":"3.41.0"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T00:00:00Z","timestamp":1745798400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2025,4,28]]},"abstract":"<jats:p>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\u2014dynamic 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 \u03b8(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 historyindependent dynamic-partitioning primitive has meant that designers of history-independent data structures have had to resort to complex alternatives. In this paper, 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 logN\/ loglogN) with high probability in set size N.<\/jats:p>","DOI":"10.1145\/3733620.3733625","type":"journal-article","created":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:20:07Z","timestamp":1745943607000},"page":"17-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures"],"prefix":"10.1145","volume":"54","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University and RelationalAI"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"New York University"}]},{"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[{"name":"University of California, Irvine"}]},{"given":"Hanna","family":"Koml\u00f3s","sequence":"additional","affiliation":[{"name":"New York University"}]}],"member":"320","published-online":{"date-parts":[[2025,4,29]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"531","volume-title":"Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Acar U. A.","year":"2004","unstructured":"U. A. Acar, G. E. Blelloch, R. Harper, J. L. Vittes, and S. L. M. Woo. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 531--540, 2004."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.2.135"},{"key":"e_1_2_1_3_1","volume-title":"Fusion trees can be implemented with AC0 instructions only. Theoretical Computer Science, 215(1--2):337--344","author":"Andersson A.","year":"1999","unstructured":"A. Andersson, P. B. Miltersen, and M. Thorup. Fusion trees can be implemented with AC0 instructions only. Theoretical Computer Science, 215(1--2):337--344, 1999."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185430"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792241102"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1236457.1236460"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63531"},{"key":"e_1_2_1_8_1","volume-title":"The foundations of history independence. arXiv preprint arXiv:1501.06508","author":"Bajaj S.","year":"2015","unstructured":"S. Bajaj, A. Chakraborti, and R. Sion. The foundations of history independence. arXiv preprint arXiv:1501.06508, 2015."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2015.2491309"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544816"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516724"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288683"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902276"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_17"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00096"},{"key":"e_1_2_1_16_1","first-page":"399","volume-title":"Cache-oblivious B-trees. In Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Bender M. A.","year":"2000","unstructured":"M. A. Bender, E. D. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. In Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 399--409, 2000."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/10719839_9"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_19_1","volume-title":"An introduction to b-trees and write-optimization. :login","author":"Bender M. A.","year":"2015","unstructured":"M. A. Bender, M. Farach-Colton, W. Jannen, R. Johnson, B. C. Kuszmaul, D. E. Porter, J. Yuan, and Y. Zhan. An introduction to b-trees and write-optimization. :login; magazine, 40(5):22--28, Oct. 2015."},{"key":"e_1_2_1_20_1","volume-title":"Proc. of the 14th Network and Distributed System Security Symposium (NDSS)","author":"Bethencourt J.","year":"2007","unstructured":"J. Bethencourt, D. Boneh, and B. Waters. Cryptographic methods for storing ballots on a voting machine. In Proc. of the 14th Network and Distributed System Security Symposium (NDSS), 2007."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334201"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644201"},{"key":"e_1_2_1_23_1","first-page":"445","volume-title":"Advances in Cryptology","author":"Buchbinder N.","year":"2003","unstructured":"N. Buchbinder and E. Petrank. Lower and upper bounds on obtaining history independence. In Advances in Cryptology, pages 445--462, 2003."},{"key":"e_1_2_1_24_1","first-page":"281","volume-title":"26th Annual Symposium on Foundations of Computer Science (FOCS'85)","author":"Celis P.","year":"1985","unstructured":"P. Celis, P. Larson, and J. I. Munro. Robin Hood hashing (preliminary report). In 26th Annual Symposium on Foundations of Computer Science (FOCS'85), pages 281--288, Portland, Oregon, USA, 21--23 Oct. 1985."},{"key":"e_1_2_1_25_1","volume-title":"Hiflash: A history independent flash device. CoRR, abs\/1511.05180","author":"Chen B.","year":"2015","unstructured":"B. Chen and R. Sion. Hiflash: A history independent flash device. CoRR, abs\/1511.05180, 2015."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/356770.356776"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_13"},{"key":"e_1_2_1_31_1","first-page":"487","volume-title":"Proc. 36th Annual International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Golovin D.","year":"2009","unstructured":"D. Golovin. B-treaps: A uniquely represented alternative to B-trees. In Proc. 36th Annual International Colloquium on Automata, Languages, and Programming (ICALP), pages 487--499. 2009."},{"key":"e_1_2_1_32_1","volume-title":"The B-skip-list: A simpler uniquely represented alternative to B-trees. arXiv preprint arXiv:1005.0662","author":"Golovin D.","year":"2010","unstructured":"D. Golovin. The B-skip-list: A simpler uniquely represented alternative to B-trees. arXiv preprint arXiv:1005.0662, 2010."},{"key":"e_1_2_1_33_1","unstructured":"M. T. Goodrich E. M. Kornaropoulos"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/646345.689901"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1140-z"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"e_1_2_1_37_1","first-page":"229","article-title":"Forgetting footprints, shunning shadows: A critical analysis of the right to be forgotten in big data practice","volume":"8","author":"Koops B.-J.","year":"2011","unstructured":"B.-J. Koops. Forgetting footprints, shunning shadows: A critical analysis of the right to be forgotten in big data practice. SCRIPTed, 8:229, 2011.","journal-title":"SCRIPTed"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00111"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258638"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_28"},{"key":"e_1_2_1_41_1","first-page":"192","article-title":"The right to forget\/be forgotten","author":"Murata K.","year":"2011","unstructured":"K. Murata and Y. Orito. The right to forget\/be forgotten. Ethics in Interdisciplinary and Intercultural Relations, 192, 2011.","journal-title":"Ethics in Interdisciplinary and Intercultural Relations"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_51"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.26"},{"key":"e_1_2_1_46_1","volume-title":"Arx: A strongly encrypted database system. IACR Cryptol. ePrint Arch., page 591","author":"Poddar R.","year":"2016","unstructured":"R. Poddar, T. Boelter, and R. A. Popa. Arx: A strongly encrypted database system. IACR Cryptol. ePrint Arch., page 591, 2016."},{"key":"e_1_2_1_47_1","volume-title":"Cornell University","author":"Pugh W.","year":"1988","unstructured":"W. Pugh. Incremental computation and the incremental evaluation of functional programs. PhD thesis, Cornell University, 1988."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75305"},{"key":"e_1_2_1_50_1","first-page":"121","volume-title":"4th European Symposium on Algorithms (ESA)","author":"Raman R.","year":"1996","unstructured":"R. Raman. Priority queues: Small, monotone and trans-dichotomous. In 4th European Symposium on Algorithms (ESA), pages 121--137, 1996."},{"key":"e_1_2_1_51_1","volume-title":"Oblivious secure deletion with bounded history independence. arXiv preprint arXiv:1505.07391","author":"Roche D. S.","year":"2015","unstructured":"D. S. Roche, A. J. Aviv, and S. G. Choi. Oblivious secure deletion with bounded history independence. arXiv preprint arXiv:1505.07391, 2015."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.19"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453914"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90175-H"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.22"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100219"},{"key":"e_1_2_1_57_1","first-page":"699","volume-title":"14th ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Thorup M.","year":"2003","unstructured":"M. Thorup. On AC0 implementations of fusion trees and atomic heaps. In 14th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 699--707, 2003."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289142"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2245276.2245279"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"},{"key":"e_1_2_1_61_1","first-page":"257","article-title":"The right to be forgotten","volume":"64","author":"Walker R. K.","year":"2012","unstructured":"R. K. Walker. The right to be forgotten. Hastings LJ, 64:257, 2012.","journal-title":"Hastings LJ"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.5555\/337729.337809"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733620.3733625","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3733620.3733625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:56:55Z","timestamp":1750298215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3733620.3733625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,28]]},"references-count":61,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,4,28]]}},"alternative-id":["10.1145\/3733620.3733625"],"URL":"https:\/\/doi.org\/10.1145\/3733620.3733625","relation":{},"ISSN":["0163-5808"],"issn-type":[{"type":"print","value":"0163-5808"}],"subject":[],"published":{"date-parts":[[2025,4,28]]},"assertion":[{"value":"2025-04-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}