Count-distinct problem: Difference between revisions

Revision as of 20:41, 28 May 2024

Revision as of 21:00, 28 May 2024

Line 52:

=== CVM Algorithm ===

Compared to other approximation algorithms for the count-distinct problem the CVM Algorithm<ref>{{Cite journal |last=Chakraborty |first=Sourav |last2=Vinodchandran |first2=N. V. |last3=Meel |first3=Kuldeep S. |date=2022 |title=Distinct Elements in Streams: An Algorithm for the (Text) Book |url=http://arxiv.org/abs/2301.10191 |pages=6 pages, 727571 bytes |doi=10.4230/LIPIcs.ESA.2022.34 |issn=1868-8969}}</ref> (named by [[Donald Knuth]] after the initials of Sourav Chakraborty, N. V. Vinodchandran, and Kuldeep S. Meel) uses sampling instead of hashing. The CVM Algorithm provides an unbiased estimator for the number of distinct elements in a stream,<ref name=":0" /> in addition to the standard (ε-δ) guarantees. Below is the modification of CVM algorithm, proposedincluding the slight modification by Donald Knuth, that maintainsadds the while loop ato bufferensure ofB maximumisis sizereduced. s<ref name=":0">{{cite journal |last1=Knuth |first1=Donald |date=May 2023 |title=The CVM Algorithm for Estimating Distinct Elements in Streams |url=https://cs.stanford.edu/~knuth/papers/cvm-note.pdf |journal=}}</ref>

{{nowrap|Initialize <math> p \leftarrow 1 </math>}}