Talk:Count-distinct problem

[Untitled]

Hi, I created a page titled "Weighted Cardinality Estimation", I want to rename it so I created another page with the same content titled "Count-Distinct Problem".

Please delete the "Weighted Cardinality Estimation" and keep the "Count-Distinct Problem" page - this should be the page's name.

Thank you, Aviv

I've moved the page for you. Tutelary (talk) 22:39, 15 October 2014 (UTC)

CVM algorithm; initial value of "p"?

There's a seemingly clear definition of the CVM algorithm using pseudo-code. Problem: there's no apparent initial value for the variable "p" (a probability threshold). What should it be? -- Dan Griscom (talk) 22:52, 18 May 2024 (UTC)

Must be 1 according to Knuth's paper. Retimuko (talk) 20:01, 19 May 2024 (UTC)

In the CVM paper Algorithm 1, line 1, states: `Initialise p <- 1;`

Paddy (talk) 20:52, 28 May 2024 (UTC)

CVM algo: halving p

Fixed assignment to p. Needs to be outside the while loop.

Paddy (talk) 20:38, 28 May 2024 (UTC)

References

CVM algorithms: adding u to data structure

I don't think there's any need to add u to the dictionary data structure (since it never gets used by the CVM algorithm). I believe it gets used in a CVM variant presented by Knuth (that deletes only 1 element at a time using treaps). 72.82.224.191 (talk) 11:47, 21 June 2024 (UTC)

CVM algorithm: Knuth's version or not?

The text claimed to present a modification by Knuth, but reading https://www-cs-faculty.stanford.edu/~knuth/papers/cvm-note.pdf his modification resulted in algorithm D, while algorithm X was the original one with a biased estimate. I've changed the page to show algorithm D and added algorithm D' as improvement of D. — Preceding unsigned comment added by Pychron (talk • contribs) 08:22, 13 November 2024 (UTC)