HyperLogLog is a randomized summary of a multiset that estimates its number of distinct elements to within a relative standard error of about , using registers of bits each for a universe of hash values of size (Flajolet et al. 2007). The Count-Min sketch is a array of counters that estimates the frequency of any item in a stream with one-sided error: the estimate satisfies always, and with probability at least when and (Cormode and Muthukrishnan 2005).
Both structures hash each item and keep only an aggregate of the hash values: HyperLogLog keeps, per register, the largest number of leading zero bits seen, and Count-Min keeps, per row, the sum of the counts that hashed to each cell. Neither stores the items, so the space is independent of the stream length, and both are mergeable: the register-wise maximum of two HyperLogLog sketches is the sketch of the union of their inputs, and the cell-wise sum of two Count-Min sketches built with the same hash functions is the sketch of the concatenated streams.
The notation (, , , ) and the benchmark stream are those of the series index. All measurements below use one day of pageviews across every Wikimedia project, with the desktop and mobile sites of a project counted separately (en and en.m): 160,961,718 hourly records over 60,974,808 distinct (project, page) keys, with 445,961,446 views in total.
Distinct counting
The distinct-elements problem asks for in one pass. An exact one-pass answer requires memory proportional to the number of distinct items in the worst case, so a summary of fixed size must approximate. Kane, Nelson and Woodruff (2010) give an algorithm using bits for a approximation with constant success probability, which matches the known lower bound. HyperLogLog does not achieve that bound asymptotically, since each of its registers needs bits, but its constants are small and an update costs one hash evaluation, a count of leading zeros and a maximum.
The observable: leading zeros of a hash
Let map items to uniformly distributed bit strings, and let be the position of the leftmost 1-bit of , so , , and . Repeated occurrences of an item produce the same hash value, so the largest over a stream depends only on the set of distinct items. If , the maximum satisfies , and is close to : a set of a million distinct items is expected to contain one whose hash starts with about 20 zeros.
One such maximum estimates to within a constant, so estimates only to within a constant factor, with a standard deviation comparable to itself. HyperLogLog reduces the variance by stochastic averaging: the first bits of the hash choose one of registers, the remaining bits supply , and each register records the maximum over the items assigned to it. Each register then sees about items, and the estimate combines the registers.
update(i): x = h(i); j = first p bits of x; w = remaining bits
M[j] = max(M[j], rho(w))The raw estimator
The combination step is a normalized harmonic mean of :
Flajolet et al. give , , and for . The harmonic mean is used because has a heavy right tail, and the harmonic mean is less sensitive to a few large values than the arithmetic or geometric mean. The predecessor algorithm, LogLog (Durand and Flajolet 2003), used the geometric mean and reached a standard error of ; HyperLogLog reaches , so it attains LogLog’s accuracy with of the registers.
Where and come from. The constants follow from a short calculation in the Poisson model, in which the number of items assigned to each register is an independent Poisson variable with mean . A register is at most exactly when none of its items has , so . Summing by parts,
For large each sum is close to the integral obtained by substituting , :
So , and inverting gives . The relative variance of one term is . The sum of independent terms has relative variance , and by the delta method its reciprocal has the same relative standard deviation to first order:
The integral approximation discards a small periodic oscillation in , and the Poisson model replaces the multinomial assignment of a fixed items. Flajolet et al. treat both exactly with Mellin transforms and depoissonization. Their Theorem 1 states that with for , and that the standard error is with , , and . They also state that the estimate is approximately Gaussian, so it falls within one, two and three standard errors of in about 65%, 95% and 99% of cases.
Memory. A register stores a value of at most for an -bit hash, so 5 bits suffice for a 32-bit hash and 6 bits for a 64-bit hash. With 6-bit registers, uses 12 KiB and gives a standard error of 0.81%. The abstract of Flajolet et al. describes the 32-bit version as able to “estimate cardinalities well beyond with a typical accuracy of 2% while using a memory of only 1.5 kilobytes”.
| Memory, 6-bit registers | |||
|---|---|---|---|
| 4 | 16 | 26% | 12 B |
| 8 | 256 | 6.5% | 192 B |
| 10 | 1,024 | 3.25% | 768 B |
| 12 | 4,096 | 1.63% | 3 KiB |
| 14 | 16,384 | 0.81% | 12 KiB |
| 16 | 65,536 | 0.41% | 48 KiB |
| 18 | 262,144 | 0.20% | 192 KiB |
Small and large cardinalities
The derivation above assumes that every register has received many items. When is comparable to or smaller, many registers are still 0, each contributing to the denominator, and the raw estimator is biased upward: with no items at all, . On the pageview keys with , the mean raw estimate is about 11,800 at , 12.3 times the true value at , and still 2.7% too large at .
Flajolet et al. handle this range with linear counting (Whang et al. 1990). If registers are empty, then , and inverting gives the estimate . With , the occupancy variance and the delta method give a relative standard error of , the expression in Whang et al. That formula matches the measurement at : it predicts 0.56%, 0.58% and 0.78% at = 1000, 5012 and 29,286, and the measured RMSE over 2000 trials is 0.56%, 0.57% and 0.77%. Linear counting is more accurate than until about , where , and its error grows quickly after that.
The 2007 algorithm uses linear counting when and some register is empty, and the raw estimate otherwise. For a 32-bit hash it also applies a large-range correction, , when , intended to account for distinct items whose 32-bit hash values collide.
The switch at is visible on real data. Near the raw estimate is biased upward by about 2.7%, and the rule chooses between two estimators according to the value of one of them: trials whose raw estimate is high cross the threshold and report the biased raw value, and trials whose raw estimate is low report linear counting. The mixture has a bias of +1.04% and an RMSE of 2.20% at , , which is 2.71 times the nominal 0.81%. The raw estimator’s bias at a fixed does not shrink as grows while does, so the excess roughly doubles with each increase of 2 in :
| Worst RMSE of the 2007 algorithm, near | Ratio to | |
|---|---|---|
| 10 | 4.2% | 1.29 |
| 12 | 2.95% | 1.81 |
| 14 | 2.20% | 2.71 |
| 16 | 2.03% | 4.99 |
| 18 | 2.05% | 10.1 |
The large-range correction is not needed. The analysis treats the hash values of the distinct items as independent uniform draws. Two items whose hash values coincide are two draws that happen to be equal, and the register maxima have the same distribution whether or not this happens, up to the truncation of at . The raw estimator therefore already estimates when some hash values coincide, and the correction, which treats as a count of distinct hash values and inflates it, introduces a bias. With a 32-bit hash at on all 60,974,808 keys, the raw estimate had a mean error of (mean and its standard error over 2000 trials), and applying the correction moved it to , which equals the first-order size of the correction, . The data set is below the threshold, so the 2007 rule does not apply the correction here. Ertl (2017) reaches the same conclusion analytically and observes that the correction “makes the bias worse”.
HyperLogLog++
Heule, Nunkesser and Hall (2013) describe the changes made for Google’s production implementation.
- A 64-bit hash. Registers take 6 bits, and the large-range correction is removed, since is not truncated below .
- Empirical bias correction. The bias of the raw estimator for was measured by simulation on 5000 data sets at about 200 values of for each precision . At run time the bias is estimated by averaging the tabulated biases of the 6 nearest tabulated raw estimates and subtracted. Linear counting is used below a per-precision threshold determined experimentally (11,500 at , about ), and the bias-corrected raw estimate above it.
- A sparse representation. While few registers are nonzero, the sketch stores a sorted list of (index, ) pairs computed with a larger precision , and converts to the dense array when the list would exceed the dense array’s bits. Linear counting over buckets has a much smaller error than over : by the formula above, at the relative standard error is about against 0.61% for .
Measured at , the bias correction removes the spike of the 2007 algorithm: the RMSE of the dense HyperLogLog++ estimate stays below 0.75% for every , under the nominal 0.81%. The correction leaves a small upward bias of 0.06% to 0.12% between and , which is under 15% of the standard error but four to eight standard errors of the mean over 2000 trials, so sampling noise does not account for it. The sparse mode, simulated as linear counting on buckets until 12,107 pairs (the conversion point for in the paper’s Table 1), had an RMSE of 0.01% or less up to that point, against 0.56% to 0.6% for the dense sketch. At the dense estimate has one irregularity: at its RMSE is 0.68%, 1.67 times the nominal value, while the raw estimate’s spread at that point is 0.21% and the neighboring checkpoints are near 0.22%. One possible cause is that the interpolated bias correction changes steeply in this region.
Ertl’s estimator
Ertl derives an estimator that needs neither switching nor tables. Write for the number of registers with value , for where . The raw estimator’s denominator is , and the bias at small and large comes from the two boundary counts: , the empty registers, and , the registers whose has reached its maximum. Ertl replaces their contributions with functions derived from the Poisson model:
When no register is empty or saturated, and , and the formula reduces to the raw estimator with in place of . Ertl states that is sufficient for and that the estimate is monotone in the register values. Redis computes this estimator (the functions hllSigma and hllTau in hyperloglog.c cite Ertl) with and 6-bit registers.
On the pageview stream at the estimator tracks linear counting at small (RMSE 0.56% to 0.60% up to ) and beyond, with no spike anywhere on the 214 checkpoints. Its mean error is below 0.04% in absolute value at every checkpoint, within about two standard errors of the mean. At the replacement of by is visible: the measured bias at is at , at and at , close to the ratios = 7.2%, 1.7% and 0.43%.
The figure repeats the comparison in the browser for to , with 300 trials per curve. It plots the median relative error of the raw estimator, of the 2007 algorithm and of Ertl’s estimator against , the 5% and 95% quantiles of the 2007 algorithm (dashed) and of Ertl’s estimator (shaded), and . The curves show the raw estimator’s upward bias below about , the jump of the 2007 algorithm at , and Ertl’s estimator following without either.
At n = 32, the raw estimate's median error is 95%; linear counting and the improved estimator are within −15.8% to 20.7%. At n = 154 (5m/2), 90% of the 2007 algorithm's estimates lie in −18.5% to 20.5%, and of the improved estimator's in −14.9% to 21.2%. At n = 1,778 the improved estimator's standard error is 14.28%; the asymptotic value 1.04/√m is 13.00%.
Measured error at million
Each row is 2000 independent trials, each with a different seed for the 64-bit hash, over all 60,974,808 distinct keys of the day, using Ertl’s estimator. The bracket is a 95% bootstrap interval for the standard deviation.
| Measured sd | Within | Within | Within | ||
|---|---|---|---|---|---|
| 4 | 26.0% | 29.8% [28.4, 31.3] | 69.8% | 92.4% | 97.2% |
| 6 | 13.0% | 13.3% [12.8, 13.7] | 69.6% | 94.8% | 99.1% |
| 8 | 6.50% | 6.50% [6.28, 6.70] | 69.8% | 95.0% | 99.5% |
| 10 | 3.25% | 3.18% [3.09, 3.28] | 69.9% | 95.9% | 99.9% |
| 12 | 1.63% | 1.60% [1.55, 1.65] | 68.8% | 96.1% | 99.8% |
| 14 | 0.81% | 0.82% [0.79, 0.85] | 67.8% | 95.2% | 99.8% |
| 16 | 0.41% | 0.43% [0.41, 0.44] | 65.2% | 94.8% | 99.7% |
| 18 | 0.20% | 0.20% [0.20, 0.21] | 68.1% | 95.2% | 99.7% |
From upward the interval contains except at , where the measured value is 4.8% above it. At the measured value exceeds even , and the coverage at (97.2% against 99.7% for a Gaussian) indicates a long upper tail with only 16 registers. At the coverage at is 99.1%, still about five binomial standard errors below 99.7%. From upward the coverage figures are consistent with a Gaussian estimate.
Hash functions on real keys
The analysis assumes a uniformly random hash. Real keys are strings with long shared prefixes (en Talk:..., en.m Category:...), and a weak hash can map them to correlated values. The same 64-bit estimator at was run on each of the 24 hourly key sets and on the whole day with five hash functions, one estimate each:
| Hash | Mean error over 24 hours | Range over 24 hours | Error for the day |
|---|---|---|---|
| MurmurHash64A | +0.24% | to | |
| FNV-1a, 64-bit | to | ||
| FNV-1a, 32-bit | to | ||
| CRC-32 | to | ||
Polynomial, base 31 (Java’s String.hashCode) | to |
With a standard error of 0.81% per estimate, the first four are consistent with an unbiased estimator. The base-31 polynomial underestimates in every one of the 24 hours. Its top 14 bits, which choose the register, are far from uniform on the hour-0 keys: the statistic of the register loads is 243,389 on 16,383 degrees of freedom, against 16,168 for FNV-1a and 16,548 for CRC-32. Uneven loads bias the estimate downward because the harmonic mean of the per-register loads is smaller than their arithmetic mean ; for these loads the ratio is 0.986. Replacing only the index bits or only the bits with those of a good hash showed that both halves contribute (hour 0, one estimate each: with both from the polynomial, with only from it, with only the index from it, and with neither). Its collision count was also high, 5178 colliding keys against 3949 for FNV-1a and an expected 3975 for a random 32-bit function.
Merging, unions and intersections
The sketch of is the register-wise maximum of the sketches of and , so unions are exact operations on sketches and carry the same relative error with respect to . Intersections are not directly supported. The inclusion-exclusion estimate has an absolute error on the order of , so its relative error is larger by the factor ; for two sets whose overlap is 1% of their union, it is about 100 times the relative error of the union. MinHash, planned as a later note of the series, estimates the Jaccard similarity directly.
Frequency estimation
The point-query problem asks, after a stream of updates , for an estimate of for any . An exact answer requires a counter per distinct item. The Count-Min sketch replaces the counters with rows of shared counters and answers within an additive error proportional to .
The Count-Min sketch
Choose hash functions independently from a pairwise-independent family. The sketch is an array , initially zero.
update(i, c): for j in 1..d: count[j][h_j(i)] += c
query(i): return min over j of count[j][h_j(i)]Theorem (Cormode and Muthukrishnan, Theorem 1). With , and all , the estimate satisfies , and with probability at least , .
Proof. Each cell contains plus the counts of the other items that hash to the same cell, so with nonnegative counts every row overestimates and so does the minimum. Let be the excess in row . Pairwise independence gives for , so . By Markov’s inequality . The rows use independent hash functions, so the minimum exceeds only if every row does, which has probability at most .
The sketch stores counters and hash functions; the paper states the space as words. The base is the choice that minimizes this product for a proof of this form. If each row is made to fail with probability , Markov requires and the rows needed are , so , and is minimized at .
Updates and queries take hash evaluations. The same structure answers inner-product, range and quantile queries with errors stated in the paper. In the turnstile model, where counts may be negative, the minimum no longer bounds from below, and the first part of the theorem fails.
Skew. The bound charges every query the same , the mass of the whole stream. When the frequencies follow a Zipf law with exponent , most of that mass is in a few items, which collide with any given item only rarely. Cormode and Muthukrishnan (2005, SDM) show that point queries with error then need only space, and prove a matching lower bound for Zipf data. The pageview frequencies are skewed but with an exponent below 1 over most of the ranks (0.75 between ranks 10 and 1000, 0.72 between and ), where the improvement does not apply.
Count Sketch
Count Sketch (Charikar, Chen and Farach-Colton 2004) adds a second hash per row. An update adds to , and the query returns the median over of . Colliding items now enter with random signs, so each row’s estimate is unbiased, with variance at most . The error therefore scales with instead of . Charikar et al. state the guarantee for the top- problem: with buckets per row and rows, every estimate is within of the truth, where is computed over the items outside the largest.
For the pageview stream , but is dominated by a few pages (English Wikipedia’s Main Page alone has 4.35 million of the 446 million views). A query collides with such a page in a given row with probability , and the median over rows discards those rows, so the error of a typical query is governed by the norm of the remaining items, the quantity in which Charikar et al. state their bound. Beyond the 1000 most viewed pages that norm is .
Conservative update
Estan and Varghese (2002) proposed, for nonnegative updates, to increase only the counters that would otherwise become the minimum: “We update the smallest of the counters normally… the other counters are set to the maximum of their old value and the new value of the smallest counter.” Every counter still upper-bounds each item mapped to it, so the estimate remains an overestimate and the theorem’s bound still holds, but counters grow less. The method does not support deletions, and its result depends on the order of updates.
Measured error
Count-Min and Count Sketch were built over all 60,974,808 keys with their total daily views, for widths to and depths 1 to 8, with hash functions drawn independently for each of 8 trials. Every key was then queried. Over the 8 trials the Count-Min mean error varied by less than 0.5% and the Count Sketch mean absolute error by less than 6% (largest minus smallest, relative to the mean), so the table gives trial means. Depth is 4 () and memory counts 32-bit counters.
| Memory | CM mean error | CM median | CM 99th percentile | CS mean abs. error | CS median | CS 99th percentile | |||
|---|---|---|---|---|---|---|---|---|---|
| 16 KiB | 1,183,837 | 435,509 | 390,409 | 380,189 | 416,869 | 12,856 | 9,552 | 54,336 | |
| 64 KiB | 295,959 | 108,877 | 92,609 | 91,201 | 104,713 | 4,696 | 3,508 | 19,953 | |
| 256 KiB | 73,990 | 27,219 | 21,317 | 20,893 | 26,303 | 1,723 | 1,296 | 7,244 | |
| 1 MiB | 18,497 | 6,805 | 4,676 | 4,571 | 6,310 | 618 | 457 | 2,754 | |
| 4 MiB | 4,624 | 1,701 | 953 | 912 | 1,514 | 208 | 145 | 1,000 | |
| 16 MiB | 1,156 | 425 | 174 | 158 | 347 | 63 | 42 | 347 |
Percentiles are of the absolute error over all keys, read from a histogram with 50 bins per decade, so they are accurate to about 5%.
- The bound holds with a large margin. At depth 4 the fraction of keys whose error exceeded was at most at every width, against the guaranteed . At depth 1 it was 0.5% to 3.7%, against . Markov’s inequality is loose here because a row’s excess is a sum of many small counts and rarely reaches times its mean.
- One row’s mean error is . At depth 1 the measured mean error equals to within 0.01% at every width, as the expectation in the proof predicts.
- The minimum over rows removes collisions with heavy pages. The depth-4 mean error is 0.90 of at and 0.41 of it at , so the error falls faster than . Pages with more than views hold 2.5% of at and 32% at , and these are the collisions that the minimum can avoid. Going from depth 4 to depth 8 reduces the error only by a further 2% to 17%.
- The error does not depend on the queried count. At the mean overestimate is about 174 views for pages with one view and for pages with thousands of views alike. In relative terms the sketch is accurate for popular pages (the 100 most viewed are within 0.18% on average) and uninformative for the rest: 99.5% of all keys, including the median key with one view, receive an estimate more than twice their true count. A Count-Min sketch over keys with counters is a summary of the heavy part of the distribution.
- Count Sketch has 2.8 to 30 times smaller mean absolute error at the same width and depth, and is unbiased: its mean signed error is under 1% of its mean absolute error at depth 4. Its error is two-sided, so it can report a negative count, and its rare large errors are larger relative to its typical error (the 99th percentile is 5.6 to 8.3 times the median, against 1.1 to 2.2 for Count-Min). Its fraction of keys with error above is to .
The width needed for a given relative accuracy follows from the table: to estimate a page’s views within 10% with Count-Min at depth 4, the page needs about the mean error, about 1,700 views at . About 14,000 of the 61 million keys have that many.
Conservative update on the same stream. Fed the 161 million hourly records in file order at depth 4, conservative update reduced the mean error by a factor of 2.18 at , falling to 1.72 at and (4 trials each; at the mean overestimate fell from 174 to 101 views). Estan and Varghese report an improvement of up to an order of magnitude on their network traces. The plain Count-Min sketch computed from the same records in the same runs matched the separate run above to within 0.1%. Count Sketch still had the smaller mean absolute error at every width, by a factor of 1.6 at and 14 at .
The figure runs Count-Min in the browser on a smaller stream from the same data, the views of the 1,370,576 English Wikipedia desktop pages that were viewed in the hour ending 13:00 UTC (). It plots each page’s estimate against its true count on logarithmic axes, with the lines , and . At the default , the points form a horizontal band near for every page below a few thousand views, and only the most viewed pages lie near the diagonal.
1,024 × 4 counters (16 KB at 4 bytes each), so ε = e/w = 0.265% and δ = e−d = 1.8%. Theorem 1 allows an error above εN = 9,988 views for up to 1.8% of pages; over all 1,370,576 pages, 0.000% exceed it. A page viewed once has median estimate 2,973; 0.0% of pages are estimated exactly, and the 100 most viewed pages are overestimated by 237.89% on average.
How this was measured
The harness sources are in the
sketch-experimentsdirectory, andrun.shreproduces every number from the raw files. Large intermediate files (the 2 GB stream and the per-trial outputs) are not committed. The summaries the tables are taken from are:hll_summary.json,hashq.txt,cms_summary.jsonandcu_summary.json.
- Data. The 24 hourly pageview files dated 4 March 2026, read from a public mirror of the Wikimedia dumps. A key is the string
domain_code page_title.prep.chashes each key with MurmurHash64A (seed0x9747b28c), identifies keys by that hash in an open-addressing table, and writes the stream of (hash, hourly count) records, the distinct hashes in order of first appearance and the per-key daily totals. For 61 million keys the expected number of 64-bit collisions is about , so the hash identifies the key.- HyperLogLog.
hll.cinserts the distinct keys in order of first appearance, rehashing each 64-bit key with a per-trial seed (two rounds of the SplitMix64 finalizer), and records every estimator at 214 checkpoints from to , about 30 per decade, for . The 32-bit variants use the top 32 bits of the same hash at . HyperLogLog++ uses the bias tables and thresholds of Heule et al.’s appendix as distributed in thehyperloglog0.1.8 Python package, with 6-nearest-neighbour interpolation. The sparse mode is simulated as linear counting over buckets until 12,107 distinct bucket indices. Ertl’s estimator follows the formula above with , or for the 32-bit variant. 2000 trials take about 25 minutes on 4 cores.- Hash functions.
hashq.chashes the raw key strings with each named function, unseeded, and estimates each hour and the union of the hours with Ertl’s estimator at .coll.candsplit.ccompute collisions, register loads and the mixed-hash estimates on the hour-0 file.- Count-Min and Count Sketch.
cms.cuses 6 widths and the first of 8 rows for , with applied to the key’s 64-bit hash, and a second function of the same form whose low bit gives the Count Sketch sign. It inserts the daily totals of all keys and queries every key. 8 trials take 17 minutes on 4 cores.- Conservative update.
cu.cfeeds the 161 million hourly records in their file order, since conservative update depends on the order of updates, at depth 4.- Environment. gcc 13.3 with
-O2 -fopenmp, Python 3.13.18 with NumPy 2.5.3, on a 4-core Intel Xeon at 2.10 GHz with 15 GB of memory.- The figures. The HyperLogLog figure simulates uniformly random 64-bit hash values from a seeded generator, which is the input HyperLogLog receives from any set of distinct keys under a good hash; its estimators are tested against an independent Python implementation of the same formulas (
figure_check.py). The Count-Min figure uses the real hourly counts and a seeded hash of the page’s rank; its error statistics match a NumPy recomputation exactly.
Potentially interesting ideas
- The sparse-mode improvement reported for HyperLogLog++. Heule et al. report that the sparse representation reduces the error for small cardinalities by about a factor of 4. Simulated as linear counting over buckets, it reduced the RMSE at from about 0.56% to under 0.01% for , a factor of about 50, which is what the linear-counting formula predicts. The paper’s figure may average over a different range or include the effect of the conversion to the dense representation; the difference was not resolved.
- The irregularity of HyperLogLog++ at . Near the bias-corrected estimate has three times the spread of the raw estimate at the same point. A plausible cause is that the six nearest tabulated raw estimates change abruptly in that region, so that the subtracted bias is a steep function of the raw estimate; checking this requires plotting the interpolated correction against the tabulated points, which was not done.
- The base-31 polynomial hash. Both its index bits and its bits bias the estimate, by amounts larger than the non-uniformity of the register loads explains. The joint distribution of index and over keys with long shared prefixes may account for the rest; a test of that would measure the per-register maxima directly.
Related notes
- Probabilistic data structures, the series index, with the notation and the benchmark stream
- Expectation and concentration, for Markov’s inequality and the delta method used above
- Bloom filters, the membership counterpart of these sketches