Skip to content
The methodOpen data
Back to the collection

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

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

2023 · arXiv

AlgorithmsStatistics & probability
Read the paper
HN score
0
Mentions
6
Readers
6
Months
3
What’s in a score?

From the 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.

Metadata: arXiv. Abstracts retain their original authors’ rights.

In the conversation

Original HN comments, with labels from simple text rules. A label describes the whole comment and may miss context or irony. Read the discussion to make up your own mind. About the labels

6 selected excerpts · 6 total mentions

abetusk
Neutral mention · rule
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. until you get down to a single element. Call them A0, A1, etc., so |A0| = n/m, |A1| = n/(m^2) etc., k levels in total. Try inserting into A0 c times. If it fails, try inserting into A1 c times. If it fails, go down the "funnel" until you find a free slot. Call \delta the fraction of slots that are empty (I'm unclear if this is a parameter that gets set at hash table creation or one that's…
Read the full comment
dynamically updated). Setting c = log(1/d) and k = log(1/d) to get worst case complexity O(log^2(1/d)). This circumvents Yao's result by not being greedy. Yao's result holds true for greedy insertion and search policies and the above is non-greedy, as it's cascading down the funnels. There are probably many little hairy details to work out but that's the idea, as far as I've been able to understand it. People should let me know if I'm way off base. This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2]. [0] https://news.ycombinator.com/item?id=43007860 [1] https://www.youtube.com/watch?v=ArQNyOU1hyE [2] https://arxiv.org/pdf/2301.10191
Original comment Undergraduate shows that searches within hash tables can be much faster
kuldeepmeel
Neutral mention · rule
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 Video: https://www.youtube.com/watch?v=K_ugk7OW0bI The talk also discusses the general settings where our algorithm resolved the open problem of estimation of the union of high dimensional rectangles.
Original comment Computer scientists invent an efficient new way to count
jtanderson
Neutral mention · rule
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 https://www.aeaweb.org/journals/policies/random-author-order... [0]: https://arxiv.org/pdf/2301.10191 edit: formatting
Original comment Computer scientists invent an efficient new way to count
vitus
Neutral mention · rule
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 a single parameter beta). In particular, that bound is only guaranteed to hold for delta >= 0 (not beta = 1 + delta > 0 as asserted in the paper) [0] https://arxiv.org/pdf/2301.10191 [1] https://en.wikipedia.org/wiki/Chernoff_bound#Multiplicative_... edit: to be clear: I'm not sure at all whether this breaks the proof of correctness, although I'm having a bit of difficulty following the actual details (I think I'd need to work through the intermediate steps on paper).
Original comment Computer scientists invent an efficient new way to count
usgroup
Neutral mention · rule
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 the paper. The authors are explicit about the target audience and purpose for the algorithm: undergraduates and textbooks.
Original comment Computer scientists invent an efficient new way to count
svat
Neutral mention · rule
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 (MIX) source code. (So if want source code as primary you simply won't find it… but then again, any typical algorithm textbook like CLRS also only has pseudocode). The TAOCP pseudocode is also in a unique style that's not similar to modern programming languages — e.g. here's a note that Knuth wrote just earlier this year: https://cs.stanford.edu/~knuth/papers/cvm-note.pdf explaining (and…
Read the full comment
generalizing/correcting) in his own style, the algorithm from a recent paper (https://arxiv.org/pdf/2301.10191v1.pdf): compare how the algorithm is described in Knuth (first page) vs the paper (second page): Knuth is simultaneously more high-level and more low-level (and also uses “goto” rather than “structured programming” for-loops, about which heretical preference of his I can write a long essay some other time :D). It is possible to have different opinions about which one is the best way to learn the stuff today, but clearly Knuth rewrote it in his style because he thought it was better. ;)
Original comment Ask HN: Is Knuth's TAOCP worth the time and effort? (2023)

Keep following the thread.

More in Algorithms

More from the same topics.