{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:40Z","timestamp":1750694800319,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T00:00:00Z","timestamp":1670198400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T00:00:00Z","timestamp":1670198400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"DOI":"10.1007\/s00453-022-01057-0","type":"journal-article","created":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T11:03:08Z","timestamp":1670238188000},"page":"1786-1804","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Dynamic Dictionaries for Multisets and Counting Filters with Constant Time Operations"],"prefix":"10.1007","volume":"85","author":[{"given":"Ioana O.","family":"Bercea","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy","family":"Even","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,5]]},"reference":[{"key":"1057_CR1","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In: International colloquium on automata, languages and programming pp. 107\u2013118. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"1057_CR2","doi-asserted-by":"crossref","unstructured":"Arbitman, Y., Naor, M., Segev, G.: Backyard cuckoo hashing: Constant worst-case operations with a succinct representation. In: 2010 IEEE 51st Annual symposium on foundations of computer science, pp. 787\u2013796. IEEE (2010)","DOI":"10.1109\/FOCS.2010.80"},{"key":"1057_CR3","unstructured":"Bercea, I.O., Even, G.: Fully-dynamic space-efficient dictionaries and filters with constant number of memory accesses. arxiv:1911.05060 (2019)"},{"key":"1057_CR4","doi-asserted-by":"publisher","unstructured":"Bercea, I.O., Even, G.: A dynamic space-efficient filter with constant time operations. In: 17th scandinavian symposium and workshops on algorithm theory, SWAT 2020, June 22-24, 2020, T\u00f3rshavn, Faroe Islands, pp. 11:1\u201311:17 (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2020.11","DOI":"10.4230\/LIPIcs.SWAT.2020.11"},{"issue":"2","key":"1057_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1361192.1361194","volume":"4","author":"DK Blandford","year":"2008","unstructured":"Blandford, D.K., Blelloch, G.E.: Compact dictionaries for variable-length keys and data with applications. ACM Trans. Algorith. 4(2), 1\u201325 (2008). https:\/\/doi.org\/10.1145\/1361192.1361194","journal-title":"ACM Trans. Algorith."},{"key":"1057_CR6","doi-asserted-by":"crossref","unstructured":"Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., Varghese, G.: An improved construction for counting Bloom filters. In: European symposium on algorithms, pp. 684\u2013695. Springer (2006)","DOI":"10.1007\/11841036_61"},{"key":"1057_CR7","doi-asserted-by":"crossref","unstructured":"Broder, A., Mitzenmacher, M.: Using multiple hash functions to improve ip lookups. In: Proceedings IEEE INFOCOM 2001. Conference on computer communications. Twentieth annual joint conference of the IEEE computer and communications society (Cat. No. 01CH37213), vol.\u00a03, pp. 1454\u20131463. IEEE (2001)","DOI":"10.1109\/INFCOM.2001.916641"},{"key":"1057_CR8","doi-asserted-by":"crossref","unstructured":"Carter, L., Floyd, R., Gill, J., Markowsky, G., Wegman, M.: Exact and approximate membership testers. In: Proceedings of the tenth annual ACM symposium on theory of computing, pp. 59\u201365. ACM (1978)","DOI":"10.1145\/800133.804332"},{"key":"1057_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, S., Matias, Y.: Spectral Bloom filters. In: Proceedings of the 2003 ACM SIGMOD International conference on Management of data, pp. 241\u2013252 (2003)","DOI":"10.1145\/872757.872787"},{"issue":"2","key":"1057_CR10","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1137\/S0097539704443240","volume":"35","author":"K Dalal","year":"2005","unstructured":"Dalal, K., Devroye, L., Malalla, E., McLeish, E.: Two-way chaining with reassignment. SIAM J. Comp. 35(2), 327\u2013340 (2005)","journal-title":"SIAM J. Comp."},{"key":"1057_CR11","doi-asserted-by":"crossref","unstructured":"Demaine, E.D., auf\u00a0der Heide, F.M., Pagh, R., P\u0103tra\u015fcu, M.: De dictionariis dynamicis pauco spatio utentibus. In: Latin American symposium on theoretical informatics, pp. 349\u2013361. Springer (2006)","DOI":"10.1007\/11682462_34"},{"key":"1057_CR12","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., auf\u00a0der Heide, F.M.: A new universal class of hash functions and dynamic hashing in real time. In: International colloquium on automata, languages and programming, pp. 6\u201319. Springer (1990)","DOI":"10.1007\/BFb0032018"},{"key":"1057_CR13","doi-asserted-by":"crossref","unstructured":"Dietzfelbinger, M., Rink, M.: Applications of a splitting trick. In: International colloquium on automata, languages and programming, pp. 354\u2013365. Springer (2009)","DOI":"10.1007\/978-3-642-02927-1_30"},{"issue":"1\u20132","key":"1057_CR14","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/j.tcs.2007.02.054","volume":"380","author":"M Dietzfelbinger","year":"2007","unstructured":"Dietzfelbinger, M., Weidling, C.: Balanced allocation and dictionaries with tightly packed constant size bins. Theor. Comp. Sci. 380(1\u20132), 47\u201368 (2007)","journal-title":"Theor. Comp. Sci."},{"issue":"2","key":"1057_CR15","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D Dubhashi","year":"1998","unstructured":"Dubhashi, D., Ranjan, D.: Balls and bins: a study in negative dependence. Rand. Struct. & Algorith. 13(2), 99\u2013124 (1998)","journal-title":"Rand. Struct. & Algorith."},{"issue":"2","key":"1057_CR16","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM (JACM) 21(2), 246\u2013260 (1974)","journal-title":"J. ACM (JACM)"},{"issue":"3","key":"1057_CR17","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1109\/90.851975","volume":"8","author":"L Fan","year":"2000","unstructured":"Fan, L., Cao, P., Almeida, J., Broder, A.Z.: Summary cache: a scalable wide-area web cache sharing protocol. IEEE\/ACM Trans. Netw. 8(3), 281\u2013293 (2000)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"1057_CR18","unstructured":"Fano, R.M.: On the number of bits required to implement an associative memory. memorandum 61. Computer structures group, Project MAC, MIT, Cambridge, Mass. (1971)"},{"issue":"2","key":"1057_CR19","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00224-004-1195-x","volume":"38","author":"D Fotakis","year":"2005","unstructured":"Fotakis, D., Pagh, R., Sanders, P., Spirakis, P.: Space efficient hash tables with worst case constant access time. Theory Comp. Sys. 38(2), 229\u2013248 (2005)","journal-title":"Theory Comp. Sys."},{"issue":"6","key":"1057_CR20","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0020-0190(90)90214-I","volume":"33","author":"T Hagerup","year":"1990","unstructured":"Hagerup, T., R\u00fcb, C.: A guided tour of chernoff bounds. Inf. Process. Lett. 33(6), 305\u2013308 (1990)","journal-title":"Inf. Process. Lett."},{"key":"1057_CR21","doi-asserted-by":"crossref","unstructured":"Hagerup, T., Tholey, T.: Efficient minimal perfect hashing in nearly minimal space. In: Annual symposium on theoretical aspects of computer science, pp. 317\u2013326. Springer (2001)","DOI":"10.1007\/3-540-44693-1_28"},{"issue":"1","key":"1057_CR22","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00453-008-9267-y","volume":"55","author":"E Kaplan","year":"2009","unstructured":"Kaplan, E., Naor, M., Reingold, O.: Derandomized constructions of k-wise (almost) independent permutations. Algorithmica 55(1), 113\u2013133 (2009)","journal-title":"Algorithmica"},{"key":"1057_CR23","unstructured":"Kirsch, A., Mitzenmacher, M.: Using a queue to de-amortize cuckoo hashing in hardware. In: Proceedings of the forty-fifth annual allerton conference on communication, control and computing, vol.\u00a075 (2007)"},{"key":"1057_CR24","unstructured":"Knuth, D.E.: The art of computer programming, vol. 3: Searching and sorting. Reading MA: Addison-Wisley (1973)"},{"key":"1057_CR25","doi-asserted-by":"crossref","unstructured":"Lovett, S., Porat, E.: A lower bound for dynamic approximate membership data structures. In: 2010 IEEE 51st Annual symposium on foundations of computer science, pp. 797\u2013804. IEEE (2010)","DOI":"10.1109\/FOCS.2010.81"},{"issue":"1","key":"1057_CR26","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/PL00003817","volume":"12","author":"M Naor","year":"1999","unstructured":"Naor, M., Reingold, O.: On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. Cryptol. 12(1), 29\u201366 (1999)","journal-title":"J. Cryptol."},{"key":"1057_CR27","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal Bloom filter replacement. In: SODA, pp. 823\u2013829. SIAM (2005)"},{"issue":"2","key":"1057_CR28","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1137\/S0097539700369909","volume":"31","author":"R Pagh","year":"2001","unstructured":"Pagh, R.: Low redundancy in static dictionaries with constant query time. SIAM J. Comp. 31(2), 353\u2013363 (2001)","journal-title":"SIAM J. Comp."},{"key":"1057_CR29","doi-asserted-by":"crossref","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. In: European symposium on algorithms, pp. 121\u2013133. Springer (2001)","DOI":"10.1007\/3-540-44676-1_10"},{"key":"1057_CR30","unstructured":"Panigrahy, R.: Efficient hashing with lookups in two memory accesses. In: Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp. 830\u2013839. Society for industrial and applied mathematics (2005)"},{"key":"1057_CR31","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M., Thorup, M.: Dynamic integer sets with optimal rank, select, and predecessor search. In: 2014 IEEE 55th Annual symposium on foundations of computer science, pp. 166\u2013175. IEEE (2014)","DOI":"10.1109\/FOCS.2014.26"},{"key":"1057_CR32","doi-asserted-by":"crossref","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: International colloquium on automata, languages and programming, pp. 357\u2013368. Springer (2003)","DOI":"10.1007\/3-540-45061-0_30"},{"issue":"2","key":"1057_CR33","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"JP Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discr. Math. 8(2), 223\u2013250 (1995)","journal-title":"SIAM J. Discr. Math."},{"issue":"3","key":"1057_CR34","doi-asserted-by":"publisher","first-page":"505","DOI":"10.1137\/S0097539701386216","volume":"33","author":"A Siegel","year":"2004","unstructured":"Siegel, A.: On universal classes of extremely random constant-time hash functions. SIAM J. Comp. 33(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comp."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01057-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01057-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01057-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,9]],"date-time":"2024-10-09T22:49:33Z","timestamp":1728514173000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01057-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,5]]},"references-count":34,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1057"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01057-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2022,12,5]]},"assertion":[{"value":"30 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 December 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}