按年被提到
20232024 · 4 次2026
算法与数据结构›经典算法与数据结构·arXiv:2301.10191 · cs.DS

Distinct Elements in Streams: An Algorithm for the (Text) Book

数据流中的不同元素计数:一个教科书级的算法
Sourav Chakraborty, N. V. Vinodchandran, Kuldeep S. Meel · 2023

简单的基于采样的数据流不同元素计数算法

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 6 人首次 2023-11-28 · 最近 2025-02-11
6不同的人
3活跃月份
4讨论串
10被引(OpenAlex)

针对数据流中估计不同元素个数的问题,现有最优算法依赖成对独立性和通用哈希,超出本科教材的范围。论文给出一个简单直观、基于采样且节省空间的算法,其描述与证明只需基础概率论知识即可理解。

HN 为什么提它

它被当作一个简单到几行代码就能实现的计数算法而被推荐和转引,Knuth 也曾改写过它,不过也有评论指出其中一个界的条件与论文所述不符。

方法难度 2 / 5约 25 分钟经得起时间
读之前最好知道
1基础概率论
2数据流算法(streaming algorithms)
3期望与 Chernoff 界
4哈希(hashing)基础

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐usgroup · 2024-05

“I found the paper took about as long to read as the blog post and is more informative:”

推荐读论文,读起来和博客一样快,信息更多,算法简单可直接写成代码
Computer scientists invent an efficient new way to count原评论 ↗
批评vitus · 2024-05

“In particular, that bound is only guaranteed to hold for delta >= 0 (not beta = 1 + delta > 0 as asserted in the paper)”

Computer scientists invent an efficient new way to count原评论 ↗
引用svat · 2023-11

“explaining (and generalizing/correcting) in his own style, the algorithm from a recent paper”

指出 Knuth 用自己的风格讲解并推广修正的,就是这篇论文里的算法
Ask HN: Is Knuth's TAOCP worth the time and effort? (2023)原评论 ↗
引用kuldeepmeel · 2024-05

“I thought I would link to some relevant resources.”

贴出作者自己的这篇论文,介绍简单的数据流不同元素计数算法
Computer scientists invent an efficient new way to count原评论 ↗
引用abetusk · 2025-02

“This very much reminds me of the "Distinct Elements in Streams" idea by Chakraborty, Vinodchandran and Meel[2].”

觉得与这篇数据流不同元素的思路很像,用它做对比
Undergraduate shows that searches within hash tables can be much faster原评论 ↗
被提交为 story · 1 次