HackerPapers

arXiv:2301.10191cs.DS

Distinct Elements in Streams: An Algorithm for the (Text) Book

Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel

Abstract

Given a data stream $\mathcal{A} = \langle a_1, a_2, \ldots, a_m \rangle$ of $m$ elements where each $a_i \in [n]$, the Distinct Elements problem is to estimate the number of distinct elements in $\mathcal{A}$.Distinct Elements has been a subject of theoretical and empirical investigations over the past four decades resulting in space optimal algorithms for it.All the current state-of-the-art algorithms are, however, beyond the reach of an undergraduate textbook owing to their reliance on the usage of notions such as pairwise independence and universal hash functions. We present a simple, intuitive, sampling-based space-efficient algorithm whose description and the proof are accessible to undergraduates with the knowledge of basic probability theory.

arXiv comments
The version of the paper, as published in ESA-22, contained an error in the proof of Claim 4. The current revised version fixes the error as well as several other errors pointed by Donald E. Knuth. The main theorem and algorithm remain unchanged. The authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by \textcircled{r}
Journal reference
Apppeared in Proceedings of 30th Annual European Symposium on Algorithms (ESA 2022)
DOI
doi:10.4230/LIPIcs.ESA.2022.34
Subjects
cs.DSData Structures and Algorithms cs.DBDatabases

On Hacker News

Linked by 8 identifiable commenters in 8 comments across 3 threads, from Nov 2023 to Feb 2025. Found in 1 HN submission from May 2024 to May 2024. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. Undergraduate shows that searches within hash tables can be much faster 1 comment

    • Ok, big shout out to monort [0] for the link to the video [1]. This is just a quick overview from a single viewing of the video, but it's called "funnel hashing". The idea is to split into exponentially smaller sub arrays, so the first chunk is n/m, the second is n/(m^2), etc.…

      abetuskView on HNParent context

  2. Computer scientists invent an efficient new way to count 6 comments

    • The proof is pretty straightforward and is included in the paper https://arxiv.org/abs/2301.10191

      seanhunterView on HNParent context

    • I found the paper took about as long to read as the blog post and is more informative: https://arxiv.org/pdf/2301.10191 It is about estimating the cardinality of a set of elements derived from a stream. The algorithm is so simple, you can code it and play with it whilst you read…

      usgroupView on HNParent context

    • Link to abstract: https://arxiv.org/abs/2301.10191

      aspenmayerView on HNParent context

    • From the paper [0]: > We state the following well-known concentration bound, Chernoff bound, for completeness. Which variant of the Chernoff bound is this? This is almost the (looser variant of the) multiplicative form, but it's not quite right (per the use of 1+delta instead of…

      vitusView on HNParent context

    • Given the topic of the paper[0], the footnote is especially charming: > the authors decided to forgo the old convention of alphabetical ordering of authors in favor of a randomized ordering, denoted by r⃝. The publicly verifiable record of the randomization is available at…

      jtandersonView on HNParent context

    • We are very grateful for the interest, and I thought I would link to some relevant resources. Paper: https://arxiv.org/pdf/2301.10191 Knuth's note: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf Talk Slides: https://www.cs.toronto.edu/~meel/Slides/meel-distinct.pdf Talk…

      kuldeepmeelView on HNParent context

  3. Ask HN: Is Knuth's TAOCP worth the time and effort? 1 comment

    • Yeah as you say it's just opinion/preference, but re: > source code is the primary source of understanding a concept, and English text is just an accompanying explanation, not the other way round note that most algorithms in TAOCP are only described in English (pseudocode), no…

      svatView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.