Probabilistic counting algorithms for data base applications
type: Item
instance of: scholarly article
title: Probabilistic counting algorithms for data base applications
zbMATH Open document ID: 0583.68059
DOI: 10.1016/0022-0000(85)90041-8
author: Philippe Flajolet
author: G. Nigel Martin
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
full work available at URL: RR-0313.pdf
review text: 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.
Mathematics Subject Classification ID: 68P20
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 3934444
zbMATH Keywords: number of distinct elements in a large collection of data
Wikidata QID: Q59831137
MaRDI profile type: Publication
OpenAlex ID: W2025051251
cites work: Q5799604
cites work: Approximate counting: a detailed analysis
cites work: Q4057549
cites work: Counting large numbers of events in small registers
cites work: Sorting and Searching in Multisets
DBLP publication ID: journals/jcss/FlajoletM85
description: scientific article; zbMATH DE number 3934444