Theta Sketch

Every item is hashed to a pseudo-uniform value in [0, 1). The sketch retains the k smallest hashes it has ever seen, below a shrinking threshold θ (theta) that starts at 1. Once more than k distinct hashes have been admitted, the largest retained hash is evicted and θ shrinks to that evicted value: this is the "KMV" (K-Minimum-Values) or "bottom-k" sketch technique.

Since hashes are uniformly distributed over [0, 1), the retained set is really a uniform random sample of all distinct items restricted to the region below θ. That gives an unbiased cardinality estimator: estimate = |retained| / θ. Long runs of small hashes below a tiny θ imply a huge number of distinct items were needed to produce them, exactly the same style of reasoning HyperLogLog uses with leading-zero runs instead.

The key extra trick: because the retained set is just "the k smallest hashes below θ", two sketches can be combined by taking the smaller of their two thetas, restricting both retained sets to that shared region, and then doing ordinary set union/intersection/ difference on the (small) retained hash sets. No decompression back to the original items is ever needed: this is what Apache DataSketches and systems like Apache Druid use for "how many distinct users matched filter A and filter B" queries over huge datasets.