Count-distinct problem: Difference between revisions

Revision as of 21:04, 5 December 2023

Revision as of 18:46, 14 December 2023

Line 52:

==CVM Algorithm==

Compared to other approximation algorithms for the count-distinct problem the CVM Algorithm uses sampling instead of hashing. The CVM Algorithm provides an unbiased estimator for the number of distinct elements in a stream, however the bound on error is not currently known. Here is the algorithm:<ref>{{cite journal |last1=Knuth |first1=Donald |title=The CVM Algorithm for Estimating Distinct Elements in Streams |date=May 2023}}</ref>:

Initialize a counter, {{mvar|t}}, to zero, {{nowrap|<math> t \leftarrow 0 </math>.}}