{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T17:12:30Z","timestamp":1742922750683,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030835071"},{"type":"electronic","value":"9783030835088"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-83508-8_11","type":"book-chapter","created":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T13:05:06Z","timestamp":1627650306000},"page":"144-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Dynamic Dictionaries for Multisets and\u00a0Counting Filters with Constant Time Operations"],"prefix":"10.1007","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":[[2021,7,31]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","unstructured":"Arbitman, Y., Naor, M., Segev, G.: De-amortized cuckoo hashing: Provable worst-case performance and experimental results. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) Automata, Languages and Programming. ICALP 2009. Lecture Notes in Computer Science, vol. 5555. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_11","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"11_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":"11_CR3","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\u201324, 2020, pp. 11:1\u201311:17. T\u00f3rshavn, Faroe Islands (2020). https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2020.11, https:\/\/doi.org\/10.4230\/LIPIcs.SWAT.2020.11","DOI":"10.4230\/LIPIcs.SWAT.2020.11"},{"key":"11_CR4","unstructured":"Bercea, I.O., Even, G.: Fully-dynamic space-efficient dictionaries and filters with constant number of memory accesses. CoRR abs\/1911.05060 (2019). http:\/\/arxiv.org\/abs\/1911.05060"},{"key":"11_CR5","unstructured":"Bercea, I.O., Even, G.: A space-efficient dynamic dictionary for multisets with constant time operations. CoRR abs\/2005.02143 (2020). https:\/\/arxiv.org\/abs\/2005.02143"},{"key":"11_CR6","doi-asserted-by":"publisher","unstructured":"Blandford, D.K., Blelloch, G.E.: Compact dictionaries for variable-length keys and data with applications. ACM Trans. Algorithms 4(2) (2008). https:\/\/doi.org\/10.1145\/1361192.1361194","DOI":"10.1145\/1361192.1361194"},{"key":"11_CR7","doi-asserted-by":"publisher","unstructured":"Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., Varghese, G.: An improved construction for counting Bloom filters. In: Azar, Y., Erlebach, T. (eds.) Algorithms \u2013 ESA 2006. ESA 2006. Lecture Notes in Computer Science, vol. 4168. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11841036_61","DOI":"10.1007\/11841036_61"},{"key":"11_CR8","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. 3, pp. 1454\u20131463. IEEE (2001)","DOI":"10.1109\/INFCOM.2001.916641"},{"key":"11_CR9","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":"11_CR10","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":"11_CR11","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. Comput. 35(2), 327\u2013340 (2005)","journal-title":"SIAM J. Comput."},{"key":"11_CR12","doi-asserted-by":"publisher","unstructured":"Demaine, E.D., auf der Heide, F.M., Pagh, R., P\u0103tra\u015fcu, M.: De dictionariis dynamicis pauco spatio utentibus. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006: Theoretical Informatics. LATIN 2006. Lecture Notes in Computer Science, vol. 3887. Springer, Berlin, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11682462_34","DOI":"10.1007\/11682462_34"},{"key":"11_CR13","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., auf der Heide, F.M.: A new universal class of hash functions and dynamic hashing in real time. In: Paterson, M.S. (ed.) Automata, Languages and Programming. ICALP 1990. Lecture Notes in Computer Science, vol. 443. Springer, Berlin, Heidelberg (1990). https:\/\/doi.org\/10.1007\/BFb0032018","DOI":"10.1007\/BFb0032018"},{"key":"11_CR14","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., Rink, M.: Applications of a splitting trick. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) Automata, Languages and Programming. ICALP 2009. Lecture Notes in Computer Science, vol. 5555. Springer, Berlin, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-02927-1_30","DOI":"10.1007\/978-3-642-02927-1_30"},{"issue":"1\u20132","key":"11_CR15","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. Theoret. Comput. Sci. 380(1\u20132), 47\u201368 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"11_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 21(2), 246\u2013260 (1974)","journal-title":"J. ACM"},{"issue":"3","key":"11_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. Network. 8(3), 281\u2013293 (2000)","journal-title":"IEEE\/ACM Trans. Network."},{"key":"11_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":"11_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 Comput. Syst. 38(2), 229\u2013248 (2005)","journal-title":"Theory Comput. Syst."},{"issue":"1","key":"11_CR20","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":"11_CR21","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. 75 (2007)"},{"key":"11_CR22","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 3: Searching and sorting. Addison-Wisley, Reading MA (1973)"},{"key":"11_CR23","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":"11_CR24","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":"11_CR25","unstructured":"Pagh, A., Pagh, R., Rao, S.S.: An optimal Bloom filter replacement. In: SODA, pp. 823\u2013829. SIAM (2005)"},{"issue":"2","key":"11_CR26","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. Comput. 31(2), 353\u2013363 (2001)","journal-title":"SIAM J. Comput."},{"key":"11_CR27","doi-asserted-by":"publisher","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. In: auf der Heide, F.M. (eds.) Algorithms \u2013 ESA 2001. ESA 2001. Lecture Notes in Computer Science, vol. 2161. Springer, Berlin, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-44676-1_10","DOI":"10.1007\/3-540-44676-1_10"},{"key":"11_CR28","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":"11_CR29","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":"11_CR30","doi-asserted-by":"publisher","unstructured":"Raman, R., Rao, S.S.: Succinct dynamic dictionaries and trees. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol. 2719. Springer, Berlin, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_30","DOI":"10.1007\/3-540-45061-0_30"},{"issue":"2","key":"11_CR31","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. Discret. Math. 8(2), 223\u2013250 (1995)","journal-title":"SIAM J. Discret. Math."},{"issue":"3","key":"11_CR32","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. Comput. 33(3), 505\u2013543 (2004)","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Data Structures"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-83508-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:09:07Z","timestamp":1725541747000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-83508-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030835071","9783030835088"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-83508-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"31 July 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WADS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Workshop on Algorithms and Data Structures","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 August 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 August 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wads2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/projects.cs.dal.ca\/wads2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"123","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"38% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.1","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"13","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}