推荐usgroup · 2024-05
“I found the paper took about as long to read as the blog post and is more informative:”
推荐读论文,读起来和博客一样快,信息更多,算法简单可直接写成代码
简单的基于采样的数据流不同元素计数算法
针对数据流中估计不同元素个数的问题,现有最优算法依赖成对独立性和通用哈希,超出本科教材的范围。论文给出一个简单直观、基于采样且节省空间的算法,其描述与证明只需基础概率论知识即可理解。
它被当作一个简单到几行代码就能实现的计数算法而被推荐和转引,Knuth 也曾改写过它,不过也有评论指出其中一个界的条件与论文所述不符。
“I found the paper took about as long to read as the blog post and is more informative:”
“In particular, that bound is only guaranteed to hold for delta >= 0 (not beta = 1 + delta > 0 as asserted in the paper)”
“explaining (and generalizing/correcting) in his own style, the algorithm from a recent paper”
“I thought I would link to some relevant resources.”
“This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2].”