Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

HyperLogLog: estimate unique IDs with fixed registers

Last updated: 5 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

HyperLogLog answers a cardinality question: about how many distinct incident IDs have appeared? It is not a membership test and cannot list those IDs. The program hashes a UTF-8 ID to a fixed 64-bit fingerprint, chooses a register from the high precision bits, and stores the largest leading-zero rank seen in the remaining bits. An estimate combines all registers with a harmonic mean. When the raw estimate is small and empty registers remain, it uses an empty-register correction. Two summaries with the same precision and identical hash convention can merge by taking each register's maximum. A repeated ID makes no register change. The result is approximate even if the program is otherwise deterministic.

Operational case

One region sees incident IDs numbered 47 through 146; another sees 97 through 196. There are 150 distinct IDs in the union, though each region observed 100. Merging the register arrays estimates that union without shipping an exact set of all IDs. The printed number can differ from 150. That is expected. If billing or access control requires an exact count, use a set or a verified database query instead. Mixing a different text encoding, hash method, or precision in one merge would make its estimate meaningless, so the interface rejects unequal precision and the documented program fixes the hash and encoding.

Working Python program

python
import hashlib
import math


class DistinctIncidentEstimate:
    def __init__(self, precision=6):
        if not 4 <= precision <= 16:
            raise ValueError("precision must be between 4 and 16")
        self.precision = precision
        self.registers = [0] * (1 << precision)

    def add(self, incident_id):
        digest = hashlib.sha256(incident_id.encode("utf-8")).digest()
        fingerprint = int.from_bytes(digest[:8], "big")
        remaining_bits = 64 - self.precision
        bucket = fingerprint >> remaining_bits
        suffix = fingerprint & ((1 << remaining_bits) - 1)
        rank = remaining_bits - suffix.bit_length() + 1 if suffix else remaining_bits + 1
        self.registers[bucket] = max(self.registers[bucket], rank)

    def merge(self, other):
        if self.precision != other.precision:
            raise ValueError("precision mismatch")
        self.registers = [max(left, right) for left, right in zip(self.registers, other.registers)]

    def estimate(self):
        register_count = len(self.registers)
        alpha = {16: 0.673, 32: 0.697, 64: 0.709}.get(
            register_count, 0.7213 / (1 + 1.079 / register_count))
        harmonic = sum(2.0 ** -rank for rank in self.registers)
        raw = alpha * register_count * register_count / harmonic
        empty = self.registers.count(0)
        if raw <= 2.5 * register_count and empty:
            return register_count * math.log(register_count / empty)
        return raw


east = DistinctIncidentEstimate(8)
west = DistinctIncidentEstimate(8)
for incident_number in range(47, 147):
    east.add(f"incident-{incident_number}")
for incident_number in range(97, 197):
    west.add(f"incident-{incident_number}")
east.merge(west)
print("estimate=", round(east.estimate()), "registers=", len(east.registers), sep="")

Output

Output
estimate=147registers=256

Time, space, and tradeoff

With P precision bits, the sketch uses 2^P registers. Under a fixed-width hash model, register update is O(1), estimate and merge are O(2^P), and memory is O(2^P). Hashing a string also costs O(length of the encoded ID). Higher P uses more space and generally reduces sampling error; it cannot guarantee a particular error on one observed stream. This compact lesson omits large-range bias correction and does not claim a specified confidence interval. A 64-bit fingerprint also has a finite collision domain. Deletions cannot be reversed from max registers, and a merged result cannot be split back into its component streams.

Common Mistakes

  • Do not treat an approximate cardinality as an exact unique-ID count.
  • Do not merge sketches with different precision or hash conventions.
  • Do not use register maxima to infer membership or list IDs.
  • Do not assume a duplicate can increase a register after the first identical hash.

Connected lessons

Compare its result with Misra–Gries: find frequent-item candidates in one pass, Space-Saving: ranked candidates with count bounds, Reservoir sampling: keep a uniform fixed-size sample, then complete the bounded-stream audit and contract quiz.

MinHash bands: retrieve incident candidates, then check exact overlap adds a related structure with a different operation boundary.

data structures
range-query-structures
Storage details