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. Efficient estimation ...
Conference paper

Efficient estimation of the cardinality of large data sets

Philippe Chassaing (1), Lucas Gerin ORCID (1)
(1) Institut Élie Cartan de Nancy
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2005
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities
Proceedings
DOI
10.46298/dmtcs.3492
License
https://about.hal.science/hal-authorisation-v1
Indicators
633
Views
594
Downloads

Efficient estimation of the cardinality of large data sets

Philippe Chassaing (1), Lucas Gerin ORCID (1)
(1) Institut Élie Cartan de Nancy
Abstract
Giroire has recently proposed an algorithm which returns the $\textit{approximate}$ number of distinct elements in a large sequence of words, under strong constraints coming from the analysis of large data bases. His estimation is based on statistical properties of uniform random variables in $[0,1]$. In this note we propose an optimal estimation, using Kullback information and estimation theory.
Keywords
  • [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
  • [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
  • [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
  • cardinality
  • large multiset
  • approximate counting
Cited by

Source: OpenCitations

  • Efficient Framework for Operating on Data Sketches

    Proceedings of the VLDB Endowment

    Authors : Jakub Lemiesz ORCID

    Journal reference : Volume 16, 2023, pp. 1967-1978

    DOI : 10.14778/3594512.3594526

  • Estimating the size of a hidden finite set: Large-sample behavior of estimators

    Statistics Surveys

    Authors : Si Cheng ORCID, Daniel J. Eck ORCID, Forrest W. Crawford ORCID

    Journal reference : Volume 14, 2020, pp.

    DOI : 10.1214/19-ss127

  • Approximating the Size of a Radio Network in Beeping Model

    Lecture notes in computer science

    Authors : Philipp Brandes, Marcin Kardas, Marek Klonowski ORCID, Dominik Pająk ORCID, Roger Wattenhofer ORCID

    Journal reference : Volume , 2016, pp. 358-373

    DOI : 10.1007/978-3-319-48314-6_23

  • A Smoothed-Bayesian Approach to Frequency Recovery from Sketched Data

    Journal of the American Statistical Association

    Authors : Mario Beraha ORCID, Stefano Favaro, Matteo Sesia ORCID

    Journal reference : Volume 120, 2025, pp. 2737-2748

    DOI : 10.1080/01621459.2025.2490302

  • 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

  • On the algebra of data sketches

    Proceedings of the VLDB Endowment

    Authors : Jakub Lemiesz ORCID

    Journal reference : Volume 14, 2021, pp. 1655-1667

    DOI : 10.14778/3461535.3461553

  • 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

  • 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

  • GDPR-Compliant Reputation System Based on Self-certifying Domain Signatures

    Lecture notes in computer science

    Authors : Mirosław Kutyłowski ORCID, Jakub Lemiesz ORCID, Marta Słowik ORCID, Marcin Słowik, Kamil Kluczniak ORCID, Maciej Gebala ORCID

    Journal reference : Volume , 2019, pp. 341-361

    DOI : 10.1007/978-3-030-34339-2_19

  • Give me some slack: Efficient network measurements

    Theoretical Computer Science

    Authors : Ran Ben Basat ORCID, Gil Einziger ORCID, Roy Friedman ORCID

    Journal reference : Volume 791, 2019, pp. 87-108

    DOI : 10.1016/j.tcs.2019.05.012
Preview
Loading PDF preview...