PROBABILISTIC COUNTING ALGORITHMS FOR DATABASE APPLICATIONS
PROBABILISTIC COUNTING ALGORITHMS FOR DATABASE APPLICATIONS
复制标题
DOI：
10.1016/0022-0000(85)90041-8
复制
发表时间：
1985-10-01
影响因子：
1.1
通讯作者：
MARTIN, GN
中科院分区：
文献类型：
--
作者：
FLAJOLET, P;MARTIN, GN
本文介绍了一类概率计数算法，它可以估计在一个大的数据集合（通常是一个大的文件存储在磁盘上）的不同元素的数量，在一个单一的通行证，使用只有一个小的额外的存储（通常小于100二进制字），只有几个操作，每个元素扫描。这些算法是基于对记录的散列值的比特进行的统计观察。它们是由建设完全不敏感的文件中的元素的复制结构，它们可以用于分布式系统的上下文中没有任何性能退化，并证明特别有用的数据库查询优化的上下文中。
This paper introduces a class of probabilistic counting algorithms with which one can estimate the number of distinct elements in a large collection of data (typically a large file stored on disk) in a single pass using only a small additional storage (typically less than a hundred binary words) and only a few operations per element scanned. The algorithms are based on statistical observations made on bits of hashed values of records. They are by construction totally insensitive to the replicative structure of elements in the file; they can be used in the context of distributed systems without any degradation of performances and prove especially useful in the context of data bases query optimisation.