HyperMinHash is a probabilistic data structure for cardinality estimation and set similarity that extends HyperLogLog with intersection and similarity capabilities.
The tool solves the problem of estimating both the size of set intersections and the similarity between large datasets without storing the full datasets in memory. It implements a modified HyperLogLog using 16-bit registers instead of the standard 6 bits, with the additional 10 bits allocated to b-bit signatures. This design enables the estimation of Jaccard indices between sets, which represent the proportion of shared elements. The intersection cardinality is computed by applying the Jaccard index to the union of the sets.
The tool suits projects that need memory-efficient approximate answers about set overlap and similarity at scale. It is particularly valuable when working with streaming data or distributed systems where exact computation is infeasible. The implementation demonstrates accuracy around 5% for Jaccard index estimation on set cardinalities in the billions, as shown in the provided test results across cardinalities ranging from thousands to tens of millions.
The project maintains a straightforward, focused implementation with no external dependencies beyond Go's standard library. Development activity shows consistent attention to the core algorithm with empirical validation through comprehensive test tables demonstrating performance across multiple cardinality scales. The codebase remains compact and readable, reflecting a deliberate choice to keep the implementation simple rather than add auxiliary features.
