kuldeepmeel

7 ms·

1.
by kuldeepmeel 2y ago
Unfortunately, not, and that's an interesting open problem as other count-distinct algorithms don't work for "structured sets", while this one does. https://dl.acm.org/doi/10.1145/3452021.345833
2.
by kuldeepmeel 2y ago
I agree with zero_k on everything he said about Knuth and strongly disagree with his own (extremely modest) characterization of himself.
3.
by kuldeepmeel 2y ago
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/c
4.
by kuldeepmeel 2y ago
The Chernoff bound needed in this work can be derived from Binomial distribution (with Stirling's approximation); I have worked on pairwise independent hash functions for a decade and every time I introduce such a function, it feels li
5.
by kuldeepmeel 2y ago
I fully agree with you and this is indeed one of my criticisms of modern academic writing -- we tend to write papers that are just very hard for anyone to read. So delta refers to the confidence, i.e., how often are you willing to be wrong,
6.
by kuldeepmeel 2y ago
You are indeed right; while has the added advantage of making the estimator unbiased -- i.e., not only strongly (epsilon,delta)-guarantees but also having an expectation of being correct). It wasn't easy to see that loop would have add
7.
by kuldeepmeel 2y ago
Yes, there is an error in the Quanta article [at the same time, I must add that writing popular science articles is very hard, so it would be wrong to blame them] Your fix is indeed correct; we may want to have either while loop instead of
8.
by kuldeepmeel 2y ago
The following is also not correct. if k not in mem: mem += [k] if k in mem: # not the same than "else" here if np.random.rand() > p: mem.remove(k) Your final solution is indeed corr
9.
by kuldeepmeel 2y ago
[I am one of the authors]. We have a follow-up work (admittedly, more technical) that can remove reliance on m completely: https://www.cs.toronto.edu/~meel/Papers/pods22.pdf But yes, our theorems can be reworked t
10.
A Charming Algorithm for Count-Distinct(justinjaffray.com)
3 points by kuldeepmeel 4y ago|0 comments