Estimating Cardinality for Arbitrarily Large Data Stream With Improved Memory Efficiency
Estimating Cardinality for Arbitrarily Large Data Stream With Improved Memory Efficiency
复制标题
提高内存效率的任意大数据流的基数估计
DOI：
10.1109/tnet.2020.2970860
复制
发表时间：
2020-03
期刊：
影响因子：
--
通讯作者：
Luo Junzhou
中科院分区：
文献类型：
--
作者：
Xiao Qingjun;Chen Shigang;Zhou You;Luo Junzhou
基数估计是在输入数据流只能被一次扫描的严格约束下，确定数据流中不同元素的数量（或基数）的任务。这是许多实际应用中的基本问题，例如高速网络的流量监控和Internet规模数据库的查询优化。为了解决这个问题，我们提出了一个算法名为HLL-TailCut，它实现了估计的标准误差$1.0 / \sqrt {m}$使用的内存单元的4位或3位，其成本是远远小于5位的内存单元使用HyperLogLog，以前已知的最好的基数估计。这使得HyperLogLog的内存成本降低了20%~ 45%。例如，当目标估计误差为1.1%时，最先进的HyperLogLog需要5.6 MB内存。相比之下，我们的新算法只需要3兆字节的内存消耗达到相同的精度。此外，我们的算法能够支持非常大的流基数的估计，即使在Tera和Peta规模。
Cardinality estimation is the task of determining the number of distinct elements (or the cardinality) in a data stream, under a stringent constraint that the input data stream can be scanned by just one single pass. This is a fundamental problem with many practical applications, such as traffic monitoring of high-speed networks and query optimization of Internet-scale database. To solve the problem, we propose an algorithm named HLL-TailCut, which implements the estimation standard error $1.0 / \sqrt {m}$ using the memory units of four or three bits each, whose cost is much smaller than the five-bit memory units used by HyperLogLog, the best previously known cardinality estimator. This makes it possible to reduce the memory cost of HyperLogLog by 20%~45%. For example, when the target estimation error is 1.1%, state-of-the-art HyperLogLog needs 5.6 kilobytes memory. By contrast, our new algorithm only needs 3 kilobytes memory consumption for attaining the same accuracy. Additionally, our algorithm is able to support the estimation of very large stream cardinalities, even on the Tera and Peta scale.
登录
查看更多内容
DOI：
--
发表时间：
2013-04
期刊：
--
影响因子：
--
作者：
Minlan Yu;Lavanya Jose;Rui Miao
通讯作者：
Minlan Yu;Lavanya Jose;Rui Miao
DOI：
10.1109/infcom.2010.5461921
发表时间：
2010-03
期刊：
2010 Proceedings IEEE INFOCOM
影响因子：
--
作者：
Peter Lieven;Björn Scheuermann
通讯作者：
Peter Lieven;Björn Scheuermann
影响因子：
1.6
作者：
Ashwin Lall;Vyas Sekar;Mitsunori Ogihara;Jun Xu;Hui Zhang
通讯作者：
Ashwin Lall;Vyas Sekar;Mitsunori Ogihara;Jun Xu;Hui Zhang
影响因子：
1.1
作者：
FLAJOLET, P;MARTIN, GN
通讯作者：
MARTIN, GN
影响因子：
1.8
作者：
WHANG, KY;VANDERZANDEN, BT;TAYLOR, HM
通讯作者：
TAYLOR, HM