{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T03:11:54Z","timestamp":1782789114742,"version":"3.54.5"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,12,1]],"date-time":"2017-12-01T00:00:00Z","timestamp":1512086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:p>Data preparation and data profiling comprise many both basic and complex tasks to analyze a dataset at hand and extract metadata, such as data distributions, key candidates, and functional dependencies. Among the most important types of metadata is the number of distinct values in a column, also known as the zeroth-frequency moment. Cardinality estimation itself has been an active research topic in the past decades due to its many applications. The aim of this paper is to review the literature of cardinality estimation and to present a detailed experimental study of twelve algorithms, scaling far beyond the original experiments.<\/jats:p>\n          <jats:p>First, we outline and classify approaches to solve the problem of cardinality estimation - we describe their main idea, error-guarantees, advantages, and disadvantages. Our experimental survey then compares the performance all twelve cardinality estimation algorithms. We evaluate the algorithms' accuracy, runtime, and memory consumption using synthetic and real-world datasets. Our results show that different algorithms excel in different in categories, and we highlight their trade-offs.<\/jats:p>","DOI":"10.1145\/3186728.3164145","type":"journal-article","created":{"date-parts":[[2019,11,20]],"date-time":"2019-11-20T10:54:54Z","timestamp":1574247294000},"page":"499-512","source":"Crossref","is-referenced-by-count":77,"title":["Cardinality estimation"],"prefix":"10.14778","volume":"11","author":[{"given":"Hazar","family":"Harmouch","sequence":"first","affiliation":[{"name":"University of Potsdam, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Felix","family":"Naumann","sequence":"additional","affiliation":[{"name":"University of Potsdam, Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0389-y"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-47534-9_9"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/646978.711822"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545464"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1562764.1562787"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247504"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335230"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-39940-9_87"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_55"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/948205.948225"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02241657"},{"key":"e_1_2_1_14_1","volume-title":"Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, AH(1):127--146","author":"Flajolet P.","year":"2008","unstructured":"P. Flajolet , \u00c9. Fusy, O. Gandouet , and F. Meunier . HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm . Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, AH(1):127--146 , 2008 . P. Flajolet, \u00c9. Fusy, O. Gandouet, and F. Meunier. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, AH(1):127--146, 2008."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90041-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-28608-0_1"},{"key":"e_1_2_1_17_1","volume-title":"Workshop on Network-Related Data Management; in cooperation with ACM Special Interest Group on Management of Data\/Principles of Database Systems","volume":"25","author":"Gibbons P.","year":"2001","unstructured":"P. Gibbons , C. Faloutsos , M. Faloutsos , C. Palmer , and G. Siganos . The connectivity and fault tolerance of the internet topology . In Workshop on Network-Related Data Management; in cooperation with ACM Special Interest Group on Management of Data\/Principles of Database Systems , volume 25 , 2001 . P. Gibbons, C. Faloutsos, M. Faloutsos, C. Palmer, and G. Siganos. The connectivity and fault tolerance of the internet topology. In Workshop on Network-Related Data Management; in cooperation with ACM Special Interest Group on Management of Data\/Principles of Database Systems, volume 25, 2001."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672351"},{"key":"e_1_2_1_19_1","volume-title":"Data Stream Management: Processing High-Speed Data Streams","author":"Gibbons P. B.","year":"2007","unstructured":"P. B. Gibbons . Data Stream Management: Processing High-Speed Data Streams , chapter Distinct-values estimation over data streams. Springer , 2007 . P. B. Gibbons. Data Stream Management: Processing High-Speed Data Streams, chapter Distinct-values estimation over data streams. Springer, 2007."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/378580.378687"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.020"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/645921.673295"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1998.10473807"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2452376.2452456"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2006.884032"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/272991.272995"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353418"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-010-7067-2"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824086"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3389\/fict.2015.00023"},{"key":"e_1_2_1_31_1","volume-title":"Mathematical correction for fingerprint similarity measures to improve chemical retrieval. Journal of chemical information and modeling, 47(3):952--964","author":"Swamidass S. J.","year":"2007","unstructured":"S. J. Swamidass and P. Baldi . Mathematical correction for fingerprint similarity measures to improve chemical retrieval. Journal of chemical information and modeling, 47(3):952--964 , 2007 . S. J. Swamidass and P. Baldi. Mathematical correction for fingerprint similarity measures to improve chemical retrieval. Journal of chemical information and modeling, 47(3):952--964, 2007."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/78922.78925"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286711.1286755"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186728.3164145","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3186728.3164145","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:07:31Z","timestamp":1750273651000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3186728.3164145"}},"subtitle":["an experimental survey"],"short-title":[],"issued":{"date-parts":[[2017,12]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["10.1145\/3186728.3164145"],"URL":"https:\/\/doi.org\/10.1145\/3186728.3164145","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2017,12]]}}}