The Flajolet-Martin algorithm estimates how many distinct items appear in a stream. Learn the core idea, a worked bitmap example, and its link to HyperLogLog.
Updated August 2026
The Flajolet-Martin algorithm estimates the number of distinct items in a data stream without storing every item. It hashes each item, observes rare bit patterns in the hash values, and uses those observations to estimate cardinality. The result is approximate, but the memory savings can be substantial for large streams.
The algorithm addresses the distinct-count problem: how many unique values have appeared in a stream? Exact counting requires remembering every distinct value or maintaining a large exact set. Flajolet-Martin trades a small amount of accuracy for far less memory.
Examples include estimating unique visitors, device identifiers, search terms, or other high-volume events. The method estimates a count, not the identities of the distinct items.
First, hash every item so the output bits behave like a uniform random value. Then inspect a rare pattern, such as a long run of trailing zeros in the hash output. Seeing a rarer pattern suggests more distinct items have been observed.
One version maintains a bitmap. For each hash, it finds the position of the least significant 1 bit and marks that position. The first unmarked position gives a rough cardinality estimate after applying a correction factor. This follows the .
This content was generated with the assistance of AI. Our AI prompt chain workflow is carefully grounded and preferences .gov and .edu citations when available. All content is reviewed by a Telnyx employee to ensure accuracy, relevance, and a high standard of quality.
If hash outputs produce trailing-zero counts of 0, 1, 0, 3, and 1, the bitmap records positions 0, 1, and 3. Position 2 is the first gap. A single bitmap is noisy, so practical estimators use multiple independent sketches and combine the results.
| Stream step | Trailing-zero position | Bitmap positions marked |
|---|---|---|
| First new hash | 0 | 0 |
| Second new hash | 1 | 0, 1 |
| Later new hash | 3 | 0, 1, 3 |
For a uniform hash, a value with one trailing zero is more common than a value with five trailing zeros. As the number of distinct hashes grows, the chance of observing a long trailing-zero run rises. The longest or first-missing pattern therefore carries information about the scale of the distinct count.
The estimate is statistical. Different hash functions or different streams can produce different results, which is why error analysis and averaging matter in production use.
HyperLogLog is a later cardinality-estimation method that builds on the same probabilistic counting idea while using multiple registers to reduce error. Its original analysis gives a relative standard error of about 1.04 / √m, where m is the number of registers.
Meta published measurements from its Presto implementation. APPROX_DISTINCT had an observed standard error of about 2.3% above 256 distinct values, while APPROX_SET used 4,096 buckets and reduced the error to 1.6%. The sparse representation was exact up to 256 distinct values in that implementation.
The relationship is useful for learning: Flajolet-Martin explains the rare-bit-pattern intuition, while HyperLogLog shows how to turn that intuition into a more stable production sketch.
The algorithm gives an estimate, not an exact count. Its quality depends on a suitable hash function and enough independent observations. It also cannot tell you which items were distinct, only approximately how many there were.
Choose an exact set when exact identity or exact count is essential and the data fits the memory budget. Choose a sketch when scale makes exact storage impractical and a bounded estimation error is acceptable.
One Flajolet-Martin bitmap can vary widely because the estimate depends on random hash outcomes. A practical implementation divides the stream across multiple registers or runs several independent sketches. It then combines their observations with an aggregate such as an average or harmonic mean.
The aggregation reduces the influence of an unusually lucky or unlucky hash pattern. It does not make the estimate exact, and it does not remove the need to choose a high-quality hash function. It gives the system a more stable error profile across streams.
Define the acceptable error range and test the estimator on a stream that resembles production traffic. Vary the number of distinct values, the distribution of duplicates, and the number of partitions. Compare the estimate with an exact count while that comparison is still affordable.
Also decide what "distinct" means. Unique visitors might be counted by cookie, account, device, or an anonymized identifier. An accurate sketch applied to an inconsistent identifier is still a misleading metric.
Streaming systems often make this tradeoff because the exact state grows with the number of unique events. The bidirectional streaming guide describes the operational context of moving data continuously, while the probabilistic models guide explains the wider class of methods that represent uncertainty instead of returning only exact values.
Use HyperLogLog when you need production-grade approximate cardinality estimation and your data platform supports it. It extends the same rare-pattern idea with many registers and a well-studied error profile. The original Flajolet-Martin algorithm remains valuable as the clearest way to understand why the method works.
Use an exact set when downstream billing, compliance, or reconciliation requires an exact number. Use a probabilistic sketch when the key question is scale and a small, measured error is acceptable.
The semi-structured data guide covers data that does not fit a fixed relational schema. The entropy in machine learning explainer provides background on probability and uncertainty in algorithmic systems.
The serverless database guide covers the data layer where approximate distinct-count queries may be exposed to applications.
Flajolet-Martin style sketches help systems estimate unique users in a large stream of visits, unique devices reporting telemetry, or distinct search terms appearing in logs. The system stores a compact probabilistic summary instead of retaining every identifier it has seen.
These are measurement use cases, not identity-management use cases. A sketch can estimate that a stream contains about one million distinct devices, but it cannot return the list of those devices or determine which one appeared first.
Meta described the production tradeoff using a weekly distinct-visitor query. A traditional single-machine calculation would have required days and terabytes of memory, while its HLL-based Presto implementation completed the calculation in 12 hours with less than 1 MB of memory. Across the use cases reported in the engineering post, speed improvements ranged from 7 times to 1,000 times. These are Meta's measurements, not general guarantees for every data platform.
Use a deterministic test stream with a known exact distinct count before testing a large live stream. Confirm that duplicates leave the sketch unchanged, that hash values are handled consistently, and that register aggregation behaves as documented.
Then run a larger comparison against an exact set. The result gives a concrete error range for the data distribution you expect, which is more useful than relying on a theoretical guarantee alone.
No. Flajolet-Martin is a probabilistic algorithm that estimates the number of distinct elements. It deliberately trades exactness for low memory use. Production systems should measure its error against representative data before using it for a business-critical metric.
Cardinality estimation is the process of estimating how many distinct values appear in a data set or stream. It is common in streaming analytics, databases, and telemetry systems where storing every unique value would be expensive.
Hashing makes item values behave like evenly distributed random bit strings. The estimator relies on the expected frequency of rare bit patterns. A biased or poor hash can distort those frequencies and produce an unreliable distinct-count estimate.
