HyperMinHash is a Go implementation of an extended HyperLogLog probabilistic data structure that adds intersection and similarity estimation capabilities to the standard cardinality counting algorithm. The repository is maintained by Axiom and addresses a key limitation of traditional HyperLogLog implementations, which can estimate set cardinality and union sizes but cannot directly estimate intersections or measure set similarity.
The implementation uses a modified version of LogLog-Beta that employs 16-bit registers instead of the standard 6-bit registers. The additional 10 bits are allocated for b-bit signatures, which enable the similarity and intersection estimation features. The core functionality allows users to estimate Jaccard indices, which represent the similarity between two sets as a number between 0 and 1. According to the documentation, the similarity function achieves approximately 5 percent accuracy when estimating Jaccard indices of 0.01 for set cardinalities on the order of 1 billion elements. The intersection estimation applies the Jaccard index calculation to the union of sets to return estimated intersecting set cardinality.
The implementation is based on the academic paper "HyperMinHash: Jaccard index sketching in LogLog space" by Yun William Yu and Griffin M. Weber. This foundation provides theoretical grounding for the approach and ensures the algorithm's correctness for approximate similarity estimation in streaming and distributed contexts.
The repository includes comprehensive empirical results demonstrating the accuracy of the implementation across multiple scales. Test results are provided for maximum cardinalities ranging from 1,000 to 100 million elements. At the 1,000 element scale, intersection estimates typically deviate from actual values by less than 2 percent. At larger scales like 10 million elements, accuracy remains strong, with most intersection estimates within 1 to 2 percent of actual values. Even at the largest tested scale of 100 million elements, the implementation maintains reasonable accuracy, with intersection estimates generally within 1 to 2 percent of true values, though some test cases show slightly larger deviations around 3 to 4 percent.
The repository is classified within the domains of sketching algorithms, probabilistic data structures, approximate counting, set similarity estimation, and distributed systems. These classifications reflect its utility in large-scale data processing scenarios where exact computation is infeasible. The implementation serves use cases in distributed computing environments where data streams must be processed with minimal memory overhead while maintaining the ability to estimate both cardinality and set overlap.
According to GitGenius activity data, the repository has connections to several major open-source projects through overlapping contributors, including the Rust language repository, Rust's Cargo package manager, and the Alacritty terminal emulator. This suggests the codebase benefits from contributions and review practices influenced by high-quality open-source development standards.
The repository provides a practical tool for applications requiring memory-efficient approximate similarity and intersection estimation across large datasets, making it particularly valuable for distributed systems, data stream processing, and scenarios where maintaining exact set membership information is prohibitively expensive.
