Recordinality

Hash every distinct item to a pseudo-uniform value in [0, 1). Because the hash is effectively random, hashing the whole stream this way is equivalent to drawing a uniformly random permutation of the distinct items (the "data streams as random permutations" framing from the 2012 paper). An item is a k-record if fewer than k earlier items in the permutation exceed it. The classical case k=1 is the textbook "new maximum so far" record; general k generalizes this to "one of the k largest values seen so far".

Algorithmically, a k-record is detected by keeping a small table of the k largest hash values seen: if the table isn't full yet, or the new value beats the table's current minimum, it's a record and the table mutates (an insert, or an insert-and-evict). Classical records theory says the number of records after n draws grows like k · log(n/k), so counting records and inverting that growth curve recovers an estimate of n. No leading-zero counting or minimum-value tracking is involved: the count of table mutations is the entire signal.

A pleasant side effect: because the kept table always holds the k largest hashed values seen so far, once the stream ends those items form a uniform random sample of the distinct items in the stream (the paper's "distinct sampling" result), unlike reservoir sampling, repeated items never bias which distinct values are more likely to be retained. Recordinality is also one of the few cardinality estimators with a fully characterized limit distribution (gamma-distributed), rather than just an empirical error bound.