{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T22:10:11Z","timestamp":1755900611784,"version":"3.44.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2212129, CCF-2106999, CCF-2118620, CNS-1938180, CCF-2118832, CCF-2106827, CNS-1938709, CCF-2247577"],"award-info":[{"award-number":["CCF-2212129, CCF-2106999, CCF-2118620, CNS-1938180, CCF-2118832, CCF-2106827, CNS-1938709, CCF-2247577"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Graduate Fellowships for Science, Technology, Engineering, and Mathematics Diversity","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"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---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 \u0398(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 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 log N\/loglog N) with high probability in set size N.<\/jats:p>","DOI":"10.1145\/3651609","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-27","source":"Crossref","is-referenced-by-count":1,"title":["History-Independent Dynamic Partitioning: Operation-Order Privacy in Ordered Data Structures"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University and RelationalAI, Stony Brook, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8943-191X","authenticated-orcid":false,"given":"Michael T.","family":"Goodrich","sequence":"additional","affiliation":[{"name":"University of California, Irvine, Irvine, CA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5522-9193","authenticated-orcid":false,"given":"Hanna","family":"Koml\u00f3s","sequence":"additional","affiliation":[{"name":"New York University, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 531--540","author":"Acar Umut A","year":"2004","unstructured":"Umut A Acar, Guy E Blelloch, Robert Harper, Jorge L Vittes, and Shan Leung Maverick Woo. 2004. Dynamizing static algorithms, with applications to dynamic trees and history independence. In Proc. of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 531--540."},{"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","doi-asserted-by":"publisher","DOI":"10.1016\/S0304--3975(98)00172--8"},{"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 Sumeet","year":"2015","unstructured":"Sumeet Bajaj, Anrin Chakraborti, and Radu Sion. 2015. 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.1145\/1734663.1734671"},{"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","volume-title":"Cache-oblivious B-trees. In Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 399--409","author":"Bender Michael A","year":"2000","unstructured":"Michael A Bender, Erik D Demaine, and Martin Farach-Colton. 2000. Cache-oblivious B-trees. In Proc. of the 41st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 399--409."},{"key":"e_1_2_1_17_1","volume-title":"Bender and Martin Farach-Colton","author":"Michael","year":"2000","unstructured":"Michael A. Bender and Martin Farach-Colton. 2000. The LCA Problem Revisited. In Proc. Latin American Theoretical INformatics (LATIN). 88--94."},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Michael A. Bender Martin Farach-Colton Jeremy T. Fineman Yonatan R. Fogel Bradley C. Kuszmaul and Jelani Nelson. 2007. Cache-oblivious streaming B-trees. In SPAA. ACM 81--92.","DOI":"10.1145\/1248377.1248393"},{"key":"e_1_2_1_19_1","volume-title":"An Introduction to B$^\u03b5$-Trees and Write-Optimization. :login","author":"Bender Michael A.","year":"2015","unstructured":"Michael A. Bender, Martin Farach-Colton, William Jannen, Rob Johnson, Bradley C. Kuszmaul, Donald E. Porter, Jun Yuan, and Yang Zhan. 2015. An Introduction to B$^\u03b5$-Trees and Write-Optimization. :login; magazine, Vol. 40, 5 (Oct. 2015), 22--28."},{"key":"e_1_2_1_20_1","volume-title":"Proc. of the 14th Network and Distributed System Security Symposium (NDSS).","author":"Bethencourt John","year":"2007","unstructured":"John Bethencourt, Dan Boneh, and Brent Waters. 2007. Cryptographic methods for storing ballots on a voting machine. In Proc. of the 14th Network and Distributed System Security Symposium (NDSS)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.36"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/644108.644201"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Niv Buchbinder and Erez Petrank. 2003. Lower and Upper Bounds on Obtaining History Independence. In Advances in Cryptology. 445--462.","DOI":"10.1007\/978-3-540-45146-4_26"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_2_1_25_1","volume-title":"HiFlash: A History Independent Flash Device. CoRR","author":"Chen Bo","year":"2015","unstructured":"Bo Chen and Radu Sion. 2015. HiFlash: A History Independent Flash Device. CoRR , Vol. abs\/1511.05180 (2015). showeprint[arXiv]1511.05180 http:\/\/arxiv.org\/abs\/1511.05180"},{"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.1145\/800057.808675"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_13"},{"key":"e_1_2_1_31_1","volume-title":"Uniquely Represented Data Structures with Applications to Privacy. Ph.,D. Dissertation","author":"Golovin Daniel","year":"2008","unstructured":"Daniel Golovin. 2008. Uniquely Represented Data Structures with Applications to Privacy. Ph.,D. Dissertation. Carnegie Mellon University, Pittsburgh, PA, 2008."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_41"},{"key":"e_1_2_1_33_1","volume-title":"The B-skip-list: A simpler uniquely represented alternative to B-trees. arXiv preprint arXiv:1005.0662","author":"Golovin Daniel","year":"2010","unstructured":"Daniel Golovin. 2010. The B-skip-list: A simpler uniquely represented alternative to B-trees. arXiv preprint arXiv:1005.0662 (2010)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/EuroSP.2017.46"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-36136-7_21"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1140-z"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288968"},{"key":"e_1_2_1_38_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 Bert-Jaap","year":"2011","unstructured":"Bert-Jaap Koops. 2011. Forgetting footprints, shunning shadows: A critical analysis of the right to be forgotten in big data practice. SCRIPTed , Vol. 8 (2011), 229.","journal-title":"SCRIPTed"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00111"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258638"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73420-8_28"},{"key":"e_1_2_1_42_1","volume-title":"Ethics in Interdisciplinary and Intercultural Relations","volume":"192","author":"Murata Kiyosh","year":"2011","unstructured":"Kiyosh Murata and Yohki Orito. 2011. The right to forget\/be forgotten. Ethics in Interdisciplinary and Intercultural Relations , Vol. 192 (2011)."},{"volume-title":"Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP)","author":"Naor Moni","key":"e_1_2_1_43_1","unstructured":"Moni Naor, Gil Segev, and Udi Wieder. 2008. History-independent cuckoo hashing. In Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP). Springer, 631--642."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050048"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.26"},{"key":"e_1_2_1_47_1","volume-title":"Arx: A Strongly Encrypted Database System. IACR Cryptol. ePrint Arch.","author":"Poddar Rishabh","year":"2016","unstructured":"Rishabh Poddar, Tobias Boelter, and Raluca Ada Popa. 2016. Arx: A Strongly Encrypted Database System. IACR Cryptol. ePrint Arch. (2016), 591. http:\/\/eprint.iacr.org\/2016\/591"},{"volume-title":"Incremental computation and the incremental evaluation of functional programs. Ph.,D. Dissertation","author":"Pugh William","key":"e_1_2_1_48_1","unstructured":"William Pugh. 1988. Incremental computation and the incremental evaluation of functional programs. Ph.,D. Dissertation. Cornell University."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/78973.78977"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/75277.75305"},{"key":"e_1_2_1_51_1","volume-title":"Monotone and Trans-dichotomous. In 4th European Symposium on Algorithms (ESA). 121--137","author":"Raman Rajeev","year":"1996","unstructured":"Rajeev Raman. 1996. Priority Queues: Small, Monotone and Trans-dichotomous. In 4th European Symposium on Algorithms (ESA). 121--137."},{"key":"e_1_2_1_52_1","volume-title":"Oblivious Secure Deletion with Bounded History Independence. arXiv preprint arXiv:1505.07391","author":"Roche Daniel S","year":"2015","unstructured":"Daniel S Roche, Adam J Aviv, and Seung Geol Choi. 2015. Oblivious Secure Deletion with Bounded History Independence. arXiv preprint arXiv:1505.07391 (2015)."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2016.19"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453914"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90175-H"},{"key":"e_1_2_1_56_1","volume-title":"Proc. of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 142--146","author":"Snyder Lawrence","year":"1977","unstructured":"Lawrence Snyder. 1977. On uniquely represented data structures. In Proc. of the 18th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 142--146."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100219"},{"key":"e_1_2_1_58_1","volume-title":"14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 699--707","author":"Thorup Mikkel","year":"2003","unstructured":"Mikkel Thorup. 2003. On AC0 Implementations of Fusion Trees and Atomic Heaps. In 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 699--707. http:\/\/portal.acm.org\/citation.cfm?id=644108.644221"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289142"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2245276.2245279"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/358841.358852"},{"key":"e_1_2_1_62_1","first-page":"257","article-title":"The right to be forgotten","volume":"64","author":"Walker Robert Kirk","year":"2012","unstructured":"Robert Kirk Walker. 2012. The right to be forgotten. Hastings LJ, Vol. 64 (2012), 257.","journal-title":"Hastings LJ"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797322425"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651609","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:41:00Z","timestamp":1755898860000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651609"],"URL":"https:\/\/doi.org\/10.1145\/3651609","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}