{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T02:18:00Z","timestamp":1790734680764,"version":"4.1.0"},"publisher-location":"Cham","reference-count":31,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031439797","type":"print"},{"value":"9783031439803","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-3-031-43980-3_17","type":"book-chapter","created":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T12:02:15Z","timestamp":1695124935000},"page":"218-232","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Count-Min Sketch with\u00a0Variable Number of\u00a0Hash Functions: An Experimental Study"],"prefix":"10.1007","author":[{"given":"\u00c9ric","family":"Fusy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5899-5424","authenticated-orcid":false,"given":"Gregory","family":"Kucherov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,9,20]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Behera, S., Gayen, S., Deogun, J.S., Vinodchandran, N.: KmerEstimate: a streaming algorithm for estimating k-mer counts with optimal space usage. In: Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, pp. 438\u2013447 (2018)","DOI":"10.1145\/3233547.3233587"},{"key":"17_CR2","doi-asserted-by":"publisher","unstructured":"Ben Mazziane, Y., Alouf, S., Neglia, G.: A formal analysis of the count-min sketch with conservative updates. In: IEEE INFOCOM WNA 2022 - The second Workshop on Networking Algorithms (WNA), New York, USA (2022). https:\/\/doi.org\/10.1109\/INFOCOMWKSHPS54753.2022.9798146","DOI":"10.1109\/INFOCOMWKSHPS54753.2022.9798146"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Ben Mazziane, Y., Alouf, S., Neglia, G.: Analyzing count min sketch with conservative updates. Comput. Netw. 217, 109315 (2022). https:\/\/www.sciencedirect.com\/science\/article\/pii\/S1389128622003607","DOI":"10.1016\/j.comnet.2022.109315"},{"key":"17_CR4","unstructured":"Bercea, I.O., Houen, J.B.T., Pagh, R.: Daisy Bloom filters. CoRR abs\/2205.14894 (2022)"},{"key":"17_CR5","unstructured":"Bianchi, G., Duffy, K., Leith, D.J., Shneer, V.: Modeling conservative updates in multi-hash approximate count sketches. In: 24th International Teletraffic Congress, ITC 2012, Krak\u00f3w, Poland, 4\u20137 September 2012, pp. 1\u20138. IEEE (2012). https:\/\/ieeexplore.ieee.org\/document\/6331813\/"},{"key":"17_CR6","doi-asserted-by":"publisher","unstructured":"Bruck, J., Gao, J., Jiang, A.: Weighted Bloom filter. In: Proceedings 2006 IEEE International Symposium on Information Theory, ISIT 2006, The Westin Seattle, Seattle, Washington, USA, 9\u201314 July 2006, pp. 2304\u20132308. IEEE (2006). https:\/\/doi.org\/10.1109\/ISIT.2006.261978","DOI":"10.1109\/ISIT.2006.261978"},{"issue":"1","key":"17_CR7","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0304-3975(03)00400-6","volume":"312","author":"M Charikar","year":"2004","unstructured":"Charikar, M., Chen, K., Farach-Colton, M.: Finding frequent items in data streams. Theor. Comput. Sci. 312(1), 3\u201315 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"17_CR8","doi-asserted-by":"publisher","unstructured":"Chen, P., Wu, Y., Yang, T., Jiang, J., Liu, Z.: Precise error estimation for sketch-based flow measurement. In: Proceedings of the 21st ACM Internet Measurement Conference, IMC 2021, pp. 113\u2013121. Association for Computing Machinery, New York (2021). https:\/\/doi.org\/10.1145\/3487552.3487856","DOI":"10.1145\/3487552.3487856"},{"key":"17_CR9","doi-asserted-by":"publisher","unstructured":"Cohen, S., Matias, Y.: Spectral Bloom filters. In: Halevy, A.Y., Ives, Z.G., Doan, A. (eds.) Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, California, USA, 9\u201312 June 2003, pp. 241\u2013252. ACM (2003). https:\/\/doi.org\/10.1145\/872757.872787","DOI":"10.1145\/872757.872787"},{"key":"17_CR10","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1007\/978-1-4614-8265-9_87","volume-title":"Encyclopedia of Database Systems","author":"G Cormode","year":"2018","unstructured":"Cormode, G.: Count-min sketch. In: Liu, L., \u00d6zsu, M.T. (eds.) Encyclopedia of Database Systems, 2nd edn., pp. 653\u2013659. Springer, New York (2018). https:\/\/doi.org\/10.1007\/978-1-4614-8265-9_87","edition":"2"},{"issue":"2","key":"17_CR11","doi-asserted-by":"publisher","first-page":"1530","DOI":"10.14778\/1454159.1454225","volume":"1","author":"G Cormode","year":"2008","unstructured":"Cormode, G., Hadjieleftheriou, M.: Finding frequent items in data streams. Proc. VLDB Endow. 1(2), 1530\u20131541 (2008)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"17_CR12","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1016\/j.jalgor.2003.12.001","volume":"55","author":"G Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: An improved data stream summary: the count-min sketch and its applications. J. Algorithms 55(1), 58\u201375 (2005)","journal-title":"J. Algorithms"},{"key":"17_CR13","doi-asserted-by":"publisher","unstructured":"Cormode, G., Muthukrishnan, S.: Summarizing and mining skewed data streams. In: Kargupta, H., Srivastava, J., Kamath, C., Goodman, A. (eds.) Proceedings of the 2005 SIAM International Conference on Data Mining, SDM 2005, Newport Beach, CA, USA, 21\u201323 April 2005, pp. 44\u201355. SIAM (2005). https:\/\/doi.org\/10.1137\/1.9781611972757.5","DOI":"10.1137\/1.9781611972757.5"},{"key":"17_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1007\/978-3-642-14165-2_19","volume-title":"Automata, Languages and Programming","author":"M Dietzfelbinger","year":"2010","unstructured":"Dietzfelbinger, M., Goerdt, A., Mitzenmacher, M., Montanari, A., Pagh, R., Rink, M.: Tight thresholds for cuckoo hashing via XORSAT. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 213\u2013225. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14165-2_19"},{"key":"17_CR15","doi-asserted-by":"publisher","unstructured":"Dietzfelbinger, M., Walzer, S.: Dense peelable random uniform hypergraphs. In: Bender, M.A., Svensson, O., Herman, G. (eds.) 27th Annual European Symposium on Algorithms, ESA 2019, Munich\/Garching, Germany, 9\u201311 September 2019. LIPIcs, vol. 144, pp. 38:1\u201338:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2019.38","DOI":"10.4230\/LIPIcs.ESA.2019.38"},{"key":"17_CR16","doi-asserted-by":"publisher","unstructured":"Einziger, G., Friedman, R.: A formal analysis of conservative update based approximate counting. In: International Conference on Computing, Networking and Communications, ICNC 2015, Garden Grove, CA, USA, 16\u201319 February 2015, pp. 255\u2013259. IEEE Computer Society (2015). https:\/\/doi.org\/10.1109\/ICCNC.2015.7069350","DOI":"10.1109\/ICCNC.2015.7069350"},{"key":"17_CR17","doi-asserted-by":"publisher","unstructured":"Estan, C., Varghese, G.: New directions in traffic measurement and accounting. In: Mathis, M., Steenkiste, P., Balakrishnan, H., Paxson, V. (eds.) Proceedings of the ACM SIGCOMM 2002 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, Pittsburgh, PA, USA, 19\u201323 August 2002, pp. 323\u2013336. ACM (2002). https:\/\/doi.org\/10.1145\/633025.633056","DOI":"10.1145\/633025.633056"},{"key":"17_CR18","doi-asserted-by":"publisher","unstructured":"Fan, B., Andersen, D.G., Kaminsky, M., Mitzenmacher, M.D.: Cuckoo filter: practically better than Bloom. In: Proceedings of the 10th ACM International on Conference on Emerging Networking Experiments and Technologies, CoNEXT 2014, pp. 75\u201388. Association for Computing Machinery, New York (2014). https:\/\/doi.org\/10.1145\/2674005.2674994","DOI":"10.1145\/2674005.2674994"},{"issue":"3","key":"17_CR19","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.: Summary cache: a scalable wide-area web cache sharing protocol. IEEE\/ACM Trans. Netw. 8(3), 281\u2013293 (2000). https:\/\/doi.org\/10.1109\/90.851975","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"17_CR20","doi-asserted-by":"publisher","unstructured":"Fusy, \u00c9., Kucherov, G.: Count-min sketch with variable number of hash functions: an experimental study. CoRR abs\/2302.05245 (2023). https:\/\/doi.org\/10.48550\/arXiv.2302.05245, to appear in SPIRE\u201923","DOI":"10.48550\/arXiv.2302.05245"},{"key":"17_CR21","doi-asserted-by":"publisher","unstructured":"Fusy, \u00c9., Kucherov, G.: Phase transition in count approximation by count-min sketch with conservative updates. In: Mavronicolas, M. (ed.) CIAC 2023. LNCS, vol. 13898, pp. 232\u2013246. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30448-4_17. Full version in arxiv:2203.15496","DOI":"10.1007\/978-3-031-30448-4_17"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Invertible Bloom lookup tables. In: 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 792\u2013799. IEEE (2011)","DOI":"10.1109\/Allerton.2011.6120248"},{"issue":"1","key":"17_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-009-0267-2","volume":"26","author":"H Liu","year":"2011","unstructured":"Liu, H., Lin, Y., Han, J.: Methods for mining frequent items in data streams: an overview. Knowl. Inf. Syst. 26(1), 1\u201330 (2011)","journal-title":"Knowl. Inf. Syst."},{"issue":"6","key":"17_CR24","doi-asserted-by":"publisher","first-page":"547","DOI":"10.1093\/comjnl\/39.6.547","volume":"39","author":"BS Majewski","year":"1996","unstructured":"Majewski, B.S., Wormald, N.C., Havas, G., Czech, Z.J.: A family of perfect hashing methods. Comput. J. 39(6), 547\u2013554 (1996)","journal-title":"Comput. J."},{"issue":"9","key":"17_CR25","doi-asserted-by":"publisher","first-page":"1324","DOI":"10.1093\/bioinformatics\/btw832","volume":"33","author":"H Mohamadi","year":"2017","unstructured":"Mohamadi, H., Khan, H., Birol, I.: ntCard: a streaming algorithm for cardinality estimation in genomics data. Bioinformatics 33(9), 1324\u20131330 (2017)","journal-title":"Bioinformatics"},{"issue":"1","key":"17_CR26","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1002\/rsa.20061","volume":"27","author":"M Molloy","year":"2005","unstructured":"Molloy, M.: Cores in random hypergraphs and Boolean formulas. Random Struct. Algorithms 27(1), 124\u2013135 (2005)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"17_CR27","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.jalgor.2003.12.002","volume":"51","author":"R Pagh","year":"2004","unstructured":"Pagh, R., Rodler, F.F.: Cuckoo hashing. J. Algorithms 51(2), 122\u2013144 (2004)","journal-title":"J. Algorithms"},{"key":"17_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-642-35843-2_31","volume-title":"SOFSEM 2013: Theory and Practice of Computer Science","author":"M Rink","year":"2013","unstructured":"Rink, M.: Mixed hypergraphs for linear-time construction of denser hashing-based data structures. In: van Emde Boas, P., Groen, F.C.A., Italiano, G.F., Nawrocki, J., Sack, H. (eds.) SOFSEM 2013. LNCS, vol. 7741, pp. 356\u2013368. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-35843-2_31"},{"key":"17_CR29","doi-asserted-by":"publisher","unstructured":"Shibuya, Y., Kucherov, G.: Set-min sketch: a probabilistic map for power-law distributions with application to $$k$$-mer annotation. bioRxiv, p. 2020.11.14.382713 (2020). https:\/\/doi.org\/10.1101\/2020.11.14.382713","DOI":"10.1101\/2020.11.14.382713"},{"key":"17_CR30","unstructured":"Walzer, S.: Random hypergraphs for hashing-based data structures. Ph.D. thesis, Technische Universit\u00e4t Ilmenau, Germany (2020). https:\/\/www.db-thueringen.de\/receive\/dbt_mods_00047127"},{"key":"17_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/978-3-319-18123-3_21","volume-title":"Database Systems for Advanced Applications","author":"X Wang","year":"2015","unstructured":"Wang, X., Ji, Y., Dang, Z., Zheng, X., Zhao, B.: Improved weighted bloom filter and space lower bound analysis of algorithms for approximated membership querying. In: Renz, M., Shahabi, C., Zhou, X., Cheema, M.A. (eds.) DASFAA 2015. LNCS, vol. 9050, pp. 346\u2013362. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-18123-3_21"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-43980-3_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T12:03:38Z","timestamp":1695125018000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-43980-3_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031439797","9783031439803"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-43980-3_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"20 September 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Pisa","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 September 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"28 September 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/spire2023.isti.cnr.it\/","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":"47","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":"31","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":"66% - 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","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":"3","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)"}}]}}