{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:18:00Z","timestamp":1750220280633,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[],"published-print":{"date-parts":[[2022,6,9]]},"DOI":"10.1145\/3519935.3520070","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1298-1310","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["An extendable data structure for incremental stable perfect hashing"],"prefix":"10.1145","author":[{"given":"Ioana Oriana","family":"Bercea","sequence":"first","affiliation":[{"name":"IT University of Copenhagen, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Yuriy Arbitman Moni Naor and Gil Segev. 2009. De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In International Colloquium on Automata Languages and Programming. 107\u2013118.  Yuriy Arbitman Moni Naor and Gil Segev. 2009. De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In International Colloquium on Automata Languages and Programming. 107\u2013118.","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_66"},{"key":"e_1_3_2_1_4_1","volume-title":"Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. CoRR, abs\/1911.05060","author":"Bercea Ioana Oriana","year":"2019","unstructured":"Ioana Oriana Bercea and Guy Even . 2019. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. CoRR, abs\/1911.05060 ( 2019 ), arxiv:1911.05060. arxiv:1911.05060 Ioana Oriana Bercea and Guy Even. 2019. Fully-Dynamic Space-Efficient Dictionaries and Filters with Constant Number of Memory Accesses. CoRR, abs\/1911.05060 (2019), arxiv:1911.05060. arxiv:1911.05060"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2012.06.002"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 30\u201339","author":"Chazelle Bernard","year":"2004","unstructured":"Bernard Chazelle , Joe Kilian , Ronitt Rubinfeld , and Ayellet Tal . 2004 . The Bloomier filter: an efficient data structure for static support lookup tables . In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 30\u201339 . Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, and Ayellet Tal. 2004. The Bloomier filter: an efficient data structure for static support lookup tables. In Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. 30\u201339."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00146-6"},{"volume-title":"Latin American Symposium on Theoretical Informatics. 349\u2013361","author":"Demaine Erik D","key":"e_1_3_2_1_8_1","unstructured":"Erik D Demaine , Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai P\u0103tra\u015fcu. 2006. De dictionariis dynamicis pauco spatio utentibus . In Latin American Symposium on Theoretical Informatics. 349\u2013361 . Erik D Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai P\u0103tra\u015fcu. 2006. De dictionariis dynamicis pauco spatio utentibus. In Latin American Symposium on Theoretical Informatics. 349\u2013361."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. 1990. A new universal class of hash functions and dynamic hashing in real time. In International Colloquium on Automata Languages and Programming. 6\u201319.  Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. 1990. A new universal class of hash functions and dynamic hashing in real time. In International Colloquium on Automata Languages and Programming. 6\u201319.","DOI":"10.1007\/BFb0032018"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger Joseph Gil Yossi Matias and Nicholas Pippenger. 1992. Polynomial hash functions are reliable. In International Colloquium on Automata Languages and Programming. 235\u2013246.  Martin Dietzfelbinger Joseph Gil Yossi Matias and Nicholas Pippenger. 1992. Polynomial hash functions are reliable. In International Colloquium on Automata Languages and Programming. 235\u2013246.","DOI":"10.1007\/3-540-55719-9_77"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger and Rasmus Pagh. 2008. Succinct data structures for retrieval and approximate membership. In International Colloquium on Automata Languages and Programming. 385\u2013396.  Martin Dietzfelbinger and Rasmus Pagh. 2008. Succinct data structures for retrieval and approximate membership. In International Colloquium on Automata Languages and Programming. 385\u2013396.","DOI":"10.1007\/978-3-540-70575-8_32"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Martin Dietzfelbinger and Michael Rink. 2009. Applications of a splitting trick. In International Colloquium on Automata Languages and Programming. 354\u2013365.  Martin Dietzfelbinger and Michael Rink. 2009. Applications of a splitting trick. In International Colloquium on Automata Languages and Programming. 354\u2013365.","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2019.24"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_1_16_1","volume-title":"Fast Succinct Retrieval and Approximate Membership using Ribbon. CoRR, abs\/2109.01892","author":"Dillinger Peter C.","year":"2021","unstructured":"Peter C. Dillinger , Lorenz H\u00fcbschle-Schneider , Peter Sanders , and Stefan Walzer . 2021. Fast Succinct Retrieval and Approximate Membership using Ribbon. CoRR, abs\/2109.01892 ( 2021 ), arXiv:2109.01892. arxiv:2109.01892 Peter C. Dillinger, Lorenz H\u00fcbschle-Schneider, Peter Sanders, and Stefan Walzer. 2021. Fast Succinct Retrieval and Approximate Membership using Ribbon. CoRR, abs\/2109.01892 (2021), arXiv:2109.01892. arxiv:2109.01892"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/320083.320092"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-004-1195-x"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0605009"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382752"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/100216.100217"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028575"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45471-3_1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44693-1_28"},{"key":"e_1_3_2_1_25_1","volume-title":"18th International Symposium on Experimental Algorithms (SEA","author":"K\u00f6ppl Dominik","year":"2020","unstructured":"Dominik K\u00f6ppl , Simon J Puglisi , and Rajeev Raman . 2020 . Fast and simple compact hashing via bucketing . In 18th International Symposium on Experimental Algorithms (SEA 2020). Dominik K\u00f6ppl, Simon J Puglisi, and Rajeev Raman. 2020. Fast and simple compact hashing via bucketing. In 18th International Symposium on Experimental Algorithms (SEA 2020)."},{"key":"e_1_3_2_1_26_1","first-page":"224","article-title":"Linear hashing with partial expansions","volume":"6","author":"Larson Per-\u00c5ke","year":"1980","unstructured":"Per-\u00c5ke Larson . 1980 . Linear hashing with partial expansions . In VLDB. 6 , 224 \u2013 232 . Per-\u00c5ke Larson. 1980. Linear hashing with partial expansions. In VLDB. 6, 224\u2013232.","journal-title":"VLDB."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/42404.42410"},{"key":"e_1_3_2_1_28_1","first-page":"1","article-title":"Linear Hashing: a new tool for file and table addressing","volume":"80","author":"Litwin Witold","year":"1980","unstructured":"Witold Litwin . 1980 . Linear Hashing: a new tool for file and table addressing .. In VLDB. 80 , 1 \u2013 3 . Witold Litwin. 1980. Linear Hashing: a new tool for file and table addressing.. In VLDB. 80, 1\u20133.","journal-title":"VLDB."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.79"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.6.547"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02522825"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060606"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/28.3.330"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48447-7_5"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070549"},{"key":"e_1_3_2_1_39_1","volume-title":"Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 305\u2013313","author":"P\u0103tra\u015fcu Mihai","year":"2008","unstructured":"Mihai P\u0103tra\u015fcu . 2008 . Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 305\u2013313 . Mihai P\u0103tra\u015fcu. 2008. Succincter. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science. 305\u2013313."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03351-3_25"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Rajeev Raman and Satti Srinivasa Rao. 2003. Succinct dynamic dictionaries and trees. In International Colloquium on Automata Languages and Programming. 357\u2013368.  Rajeev Raman and Satti Srinivasa Rao. 2003. Succinct dynamic dictionaries and trees. In International Colloquium on Automata Languages and Programming. 357\u2013368.","DOI":"10.1007\/3-540-45061-0_30"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/98457.98523"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/313559.313797"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384274"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Rome Italy","acronym":"STOC '22"},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520070","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3520070","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:31:16Z","timestamp":1750188676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3520070"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":45,"alternative-id":["10.1145\/3519935.3520070","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3520070","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}