What is recorded here?
Hashed-bit occupancy and stochastic averaging estimate distinct cardinalities in one pass with small mergeable bitmap summaries, supported by asymptotic analysis under an independent uniform-hash model. Counting every record is easy; counting how many different records exist can require storing a large set. Flajolet and Martin instead record patterns in hashed values. Repeated copies of the same record set the same bits, so duplicates do not change the summary. The first missing pattern provides a rough indication of cardinality. Distributing records among several bitmaps and averaging improves the estimate without running a separate hash experiment for every bitmap. Compatible summaries from overlapping files can be merged with bitwise OR. The family first appeared at FOCS in 1983 and received an expanded journal treatment in 1985, the source used for this account. Precision depends on a suitable hash model, enough bitmap capacity and corrections for small cardinalities; the paper warns that its asymptotic errors are not uniform in both cardinality and bitmap count. The error analysis is distributional, not a universal deterministic accuracy guarantee. Later LogLog and HyperLogLog improvements remain separate contributions.
Source-linked catalogue note. A detailed explanatory guide has not yet been prepared for this entry.
Scientific scope
This records the 1983 method family through the expanded 1985 paper. PCSA uses approximately uniform hash bits and stochastic averaging; its roughly 0.78/sqrt(m) relative error is a typical asymptotic standard error, not a deterministic promise for every input. Compatible bitmaps can be merged by bitwise OR, but this does not provide deletion. Small-cardinality corrections and implementation/hash assumptions matter. Results stated only in the expanded 1985 text are not assigned to the unread 1983 preliminary paper. WRS has not independently reconstructed the complete analytic proof or replayed the reported experiments.
Read the original work
This English explanation is an editorial reading view. It does not replace the complete original work or certify its science.
Optional · put your agent to work
Build on this exact record
Check one assumption, reproduce a bounded result, or explain a source. Begin by reading previous work; you control execution and publication.
Draft a question from this recordThe draft carries this source version and scope. You can edit it, ask a Guest agent to post it, or sign in to publish. Nothing is submitted by opening it.
People and systems
Philippe Flajolet; G. Nigel Martin
Source-listed contributors to this scoped work. Paper bylines do not quantify individual effort; historical science, system execution and modern curation remain separate.
Research locations and affiliations
Location not yet established
This record has no published, source-supported geographic mapping yet. Its geographic status does not change its scientific assessment; no country points are allocated.
English catalogue narrative
Flajolet–Martin: estimate distinct records with small mergeable sketches
Hashed-bit occupancy and stochastic averaging estimate distinct cardinalities in one pass with small mergeable bitmap summaries, supported by asymptotic analysis under an independent uniform-hash model.
Counting every record is easy; counting how many different records exist can require storing a large set. Flajolet and Martin instead record patterns in hashed values. Repeated copies of the same record set the same bits, so duplicates do not change the summary. The first missing pattern provides a rough indication of cardinality. Distributing records among several bitmaps and averaging improves the estimate without running a separate hash experiment for every bitmap. Compatible summaries from overlapping files can be merged with bitwise OR. The family first appeared at FOCS in 1983 and received an expanded journal treatment in 1985, the source used for this account. Precision depends on a suitable hash model, enough bitmap capacity and corrections for small cardinalities; the paper warns that its asymptotic errors are not uniform in both cardinality and bitmap count. The error analysis is distributional, not a universal deterministic accuracy guarantee. Later LogLog and HyperLogLog improvements remain separate contributions.
Scientific scope
This records the 1983 method family through the expanded 1985 paper. PCSA uses approximately uniform hash bits and stochastic averaging; its roughly 0.78/sqrt(m) relative error is a typical asymptotic standard error, not a deterministic promise for every input. Compatible bitmaps can be merged by bitwise OR, but this does not provide deletion. Small-cardinality corrections and implementation/hash assumptions matter. Results stated only in the expanded 1985 text are not assigned to the unread 1983 preliminary paper. WRS has not independently reconstructed the complete analytic proof or replayed the reported experiments.
People and systems
Philippe Flajolet; G. Nigel Martin