{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T03:45:30Z","timestamp":1752983130456,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031304477"},{"type":"electronic","value":"9783031304484"}],"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-30448-4_17","type":"book-chapter","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T20:29:36Z","timestamp":1682368176000},"page":"232-246","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Phase Transition in\u00a0Count Approximation by\u00a0Count-Min Sketch with\u00a0Conservative Updates"],"prefix":"10.1007","author":[{"given":"\u00c9ric","family":"Fusy","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5899-5424","authenticated-orcid":false,"given":"Gregory","family":"Kucherov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,4,25]]},"reference":[{"key":"17_CR1","unstructured":"Aamand, A., Indyk, P., Vakilian, A.: (Learned) frequency estimation algorithms under Zipfian distribution. CoRR abs\/1908.05198 (2019)"},{"key":"17_CR2","unstructured":"Almeida, P.S.: A case for partitioned Bloom filters. CoRR abs\/2009.11789 (2020)"},{"key":"17_CR3","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 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics, pp. 438\u2013447 (2018)","DOI":"10.1145\/3233547.3233587"},{"issue":"3","key":"17_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1017\/S0963548314000017","volume":"23","author":"M Behrisch","year":"2014","unstructured":"Behrisch, M., Coja-Oghlan, A., Kang, M.: Local limit theorems for the giant component of random hypergraphs. Comb. Probab. Comput. 23(3), 331\u2013366 (2014)","journal-title":"Comb. Probab. Comput."},{"key":"17_CR5","doi-asserted-by":"publisher","first-page":"109315","DOI":"10.1016\/j.comnet.2022.109315","volume":"217","author":"Y Ben Mazziane","year":"2022","unstructured":"Ben Mazziane, Y., Alouf, S., Neglia, G.: Analyzing count min sketch with conservative updates. Comput. Netw. 217, 109315 (2022)","journal-title":"Comput. Netw."},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Ben Mazziane, Y., Alouf, S., Neglia, G.: A formal analysis of the count-min sketch with conservative updates. CoRR abs\/2203.14549 (2022)","DOI":"10.2139\/ssrn.4102693"},{"key":"17_CR7","unstructured":"Bianchi, G., Duffy, K., Leith, D.J., Shneer, V.: Modeling conservative updates in multi-hash approximate count sketches. In: Proceedings of the 24th International Teletraffic Congress, ITC 2012, Krak\u00f3w, Poland, 4\u20137 September 2012, pp. 1\u20138. IEEE (2012)"},{"issue":"1","key":"17_CR8","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. Theoret. Comput. Sci. 312(1), 3\u201315 (2004)","journal-title":"Theoret. Comput. Sci."},{"key":"17_CR9","doi-asserted-by":"crossref","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, pp. 113\u2013121 (2021)","DOI":"10.1145\/3487552.3487856"},{"key":"17_CR10","doi-asserted-by":"crossref","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, pp. 241\u2013252 (2003)","DOI":"10.1145\/872757.872787"},{"key":"17_CR11","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. Springer, Cham (2018)","edition":"2"},{"issue":"2","key":"17_CR12","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 Endowment 1(2), 1530\u20131541 (2008)","journal-title":"Proc. VLDB Endowment"},{"issue":"1","key":"17_CR13","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_CR14","doi-asserted-by":"crossref","unstructured":"Cormode, G., Muthukrishnan, S.: Summarizing and mining skewed data streams. In: Proceedings of the 2005 SIAM International Conference on Data Mining, SDM 2005, Newport Beach, CA, USA, 21\u201323 April 2005, pp. 44\u201355 (2005)","DOI":"10.1137\/1.9781611972757.5"},{"key":"17_CR15","unstructured":"Du, E., Wang, F., Mitzenmacher, M.: Putting the \u201clearning\u201d into learning-augmented algorithms for frequency estimation. In: Proceedings of the 38th International Conference on Machine Learning, ICML 2021, vol. 139, pp. 2860\u20132869 (2021)"},{"key":"17_CR16","doi-asserted-by":"crossref","unstructured":"Einziger, G., Friedman, R.: A formal analysis of conservative update based approximate counting. In: International Conference on Computing, Networking and Communications, ICNC 2015, pp. 255\u2013259 (2015)","DOI":"10.1109\/ICCNC.2015.7069350"},{"issue":"1","key":"17_CR17","first-page":"17","volume":"5","author":"P Erdos","year":"1960","unstructured":"Erdos, P., R\u00e9nyi, A., et al.: On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5(1), 17\u201360 (1960)","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"17_CR18","doi-asserted-by":"crossref","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, pp. 323\u2013336. ACM (2002)","DOI":"10.1145\/964725.633056"},{"key":"17_CR19","doi-asserted-by":"crossref","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, pp. 75\u201388 (2014)","DOI":"10.1145\/2674005.2674994"},{"issue":"3","key":"17_CR20","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. Networking 8(3), 281\u2013293 (2000)","journal-title":"IEEE\/ACM Trans. Networking"},{"key":"17_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316339831","volume-title":"Introduction to Random Graphs","author":"A Frieze","year":"2015","unstructured":"Frieze, A., Karo\u0144ski, M.: Introduction to Random Graphs. Cambridge University Press, Cambridge (2015)"},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Fusy, \u00c9., Kucherov, G.: Phase transition in count approximation by Count-Min sketch with conservative updates. CoRR abs\/2203.15496 (2022)","DOI":"10.1007\/978-3-031-30448-4_17"},{"key":"17_CR23","doi-asserted-by":"crossref","unstructured":"Fusy, \u00c9., Kucherov, G.: Count-min sketch with variable number of hash functions: an experimental study. CoRR abs\/2302.05245 (2023)","DOI":"10.1007\/978-3-031-43980-3_17"},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"Goodrich, M.T., Mitzenmacher, M.: Invertible bloom lookup tables. In: Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 792\u2013799. IEEE (2011)","DOI":"10.1109\/Allerton.2011.6120248"},{"key":"17_CR25","unstructured":"Hsu, C., Indyk, P., Katabi, D., Vakilian, A.: Learning-based frequency estimation algorithms. In: Proceedings of the 7th International Conference on Learning Representations, ICLR 2019 (2019)"},{"issue":"1","key":"17_CR26","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0377-0427(01)00464-2","volume":"142","author":"M Karo\u0144ski","year":"2002","unstructured":"Karo\u0144ski, M., \u0141uczak, T.: The phase transition in a random hypergraph. J. Comput. Appl. Math. 142(1), 125\u2013135 (2002)","journal-title":"J. Comput. Appl. Math."},{"issue":"1","key":"17_CR27","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_CR28","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_CR29","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_CR30","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_CR31","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"},{"issue":"2","key":"17_CR32","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.jctb.2004.09.005","volume":"93","author":"B Pittel","year":"2005","unstructured":"Pittel, B., Wormald, N.C.: Counting connected graphs inside-out. J. Comb. Theory, Series B 93(2), 127\u2013172 (2005)","journal-title":"J. Comb. Theory, Series B"},{"key":"17_CR33","doi-asserted-by":"crossref","unstructured":"Shibuya, Y., Kucherov, G.: Set-Min sketch: a probabilistic map for power-law distributions with application to $$k$$-mer annotation. bioRxiv (2020). https:\/\/www.biorxiv.org\/content\/10.1101\/2020.11.14.382713v1","DOI":"10.1101\/2020.11.14.382713"},{"key":"17_CR34","unstructured":"Walzer, S.: Random hypergraphs for hashing-based data structures. Ph.D. thesis, Technische Universit\u00e4t Ilmenau, Germany (2020)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-30448-4_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,11]],"date-time":"2023-12-11T10:36:49Z","timestamp":1702291009000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-30448-4_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9783031304477","9783031304484"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-30448-4_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"25 April 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CIAC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Algorithms and Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Larnaca","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Cyprus","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":"13 June 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ciac2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Open","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Easy Chair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"49","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":"25","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":"51% - 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":"6","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)"}},{"value":"3 invited papers","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}