Probabilistic Counting Algorithms for Data Base Applications Export

@article{flajolet-martin-jcss85, abstract = {This paper introduces a class of probabilistic counting lgorithms 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 con- struction totally insensitive to the...}, author = {Flajolet, Philippe and Martin, Nigel G.}, citeulike-article-id = {493560}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7100}, journal = {Journal of Computer and System Sciences}, keywords = {aggregation, sketches}, number = {2}, pages = {182--209}, posted-at = {2008-09-04 23:00:00}, priority = {2}, title = {Probabilistic Counting Algorithms for Data Base Applications}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7100}, volume = {31}, year = {1985} }

TY - JOUR ID - flajolet-martin-jcss85 L3 - citeulike-article-id:493560 N2 - This paper introduces a class of probabilistic counting lgorithms 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 con- struction totally insensitive to the... IS - 2 JF - Journal of Computer and System Sciences EP - 209 TI - Probabilistic Counting Algorithms for Data Base Applications VL - 31 SP - 182 KW - aggregation KW - sketches AU - Flajolet, Philippe AU - Martin, Nigel PY - 1985/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.12.7100 ER -