Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. An optimal cardinali ...
Conference paper

An optimal cardinality estimation algorithm based on order statistics and its full analysis

Jérémie Lumbroso (1)
(1) Algorithmes, Programmes et Résolution
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2780
License
https://about.hal.science/hal-authorisation-v1
Indicators
1101
Views
1466
Downloads

An optimal cardinality estimation algorithm based on order statistics and its full analysis

Jérémie Lumbroso (1)
(1) Algorithmes, Programmes et Résolution
Abstract
Building on the ideas of Flajolet and Martin (1985), Alon et al. (1987), Bar-Yossef et al. (2002), Giroire (2005), we develop a new algorithm for cardinality estimation, based on order statistics which, according to Chassaing and Gerin (2006), is optimal among similar algorithms. This algorithm has a remarkably simple analysis that allows us to take its $\textit{fine-tuning}$ and the $\textit{characterization of its properties}$ further than has been done until now. We prove that, asymptotically, it is $\textit{strictly unbiased}$ (contrarily to Probabilistic Counting, Loglog, Hyperloglog), we verify that its relative precision is about $1/\sqrt{m-2}$ when $m$ words of storage are used, and we fully characterize the limit law of the estimates it provides, in terms of gamma distribution―-this is the first such algorithm for which the limit law has been established. We also develop a Poisson analysis for the pre-asymptotic regime. In this way, we are able to devise a complete algorithm, covering all cardinalities ranges from $0$ to very large.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG]
  • cardinality estimation
Cited by

Source: OpenCitations

  • A Revisit to Graph Neighborhood Cardinality Estimation

    2024 IEEE 40th International Conference on Data Engineering (ICDE)

    Authors : Pinghui Wang ORCID, Yuanming Zhang ORCID, Kuankuan Cheng, Junzhou Zhao ORCID

    Journal reference : Volume , 2024, pp. 3125-3137

    DOI : 10.1109/icde60146.2024.00242

  • Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond

    Proceedings of the 42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

    Authors : Dingyu Wang ORCID, Seth Pettie ORCID

    Journal reference : Volume , 2023, pp. 317-327

    DOI : 10.1145/3584372.3588680

  • Erasable Virtual HyperLogLog for Approximating Cumulative Distribution over Data Streams

    IEEE Transactions on Knowledge and Data Engineering

    Authors : Peng Jia ORCID, Pinghui Wang ORCID, Junzhou Zhao ORCID, Jing Tao ORCID, Ye Yuan ORCID, Xiaohong Guan ORCID

    Journal reference : Volume 34, 2022, pp. 5336-5350

    DOI : 10.1109/tkde.2021.3052938

  • Non-Mergeable Sketching for Cardinality Estimation

    DROPS (Schloss Dagstuhl – Leibniz Center for Informatics)

    Authors : Pettie, Wang, Yin

    Journal reference : Volume , 2020, pp.

    DOI : 10.4230/lipics.icalp.2021.104

  • A Minimal Variance Estimator for the Cardinality of Big Data Set Intersection

    Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

    Authors : Reuven Cohen ORCID, Liran Katzir ORCID, Aviv Yehezkel

    Journal reference : Volume , 2017, pp. 95-103

    DOI : 10.1145/3097983.3097999

  • Bit-array-based alternatives to HyperLogLog

    Theoretical Computer Science

    Authors : Svante Janson ORCID, Jérémie Lumbroso ORCID, Robert Sedgewick

    Journal reference : Volume 1054, 2025, pp. 115450

    DOI : 10.1016/j.tcs.2025.115450

  • Information theoretic limits of cardinality estimation: Fisher meets Shannon

    Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing

    Authors : Seth Pettie ORCID, Dingyu Wang ORCID

    Journal reference : Volume , 2021, pp. 556-569

    DOI : 10.1145/3406325.3451032

  • Accurately Estimating User Cardinalities and Detecting Super Spreaders Over Time

    IEEE Transactions on Knowledge and Data Engineering

    Authors : Peng Jia ORCID, Pinghui Wang ORCID, Yuchao Zhang ORCID, Xiangliang Zhang ORCID, Jing Tao ORCID, Jianwei Ding ORCID, Xiaohong Guan ORCID, Don Towsley ORCID

    Journal reference : Volume 34, 2020, pp. 92-106

    DOI : 10.1109/tkde.2020.2975625

  • On Cardinality Estimation Protocols for Wireless Sensor Networks

    Lecture notes in computer science

    Authors : Jacek Cichoń ORCID, Jakub Lemiesz ORCID, Marcin Zawada ORCID

    Journal reference : Volume , 2011, pp. 322-331

    DOI : 10.1007/978-3-642-22450-8_25
Preview
Loading PDF preview...