Union, intersection, and set cardinality in loglog space
A Java implementation of the HyperMinHash algorithm, presented by Yu and Weber. HyperMinHash allows approximating set unions, intersections, Jaccard Indices, and cardinalities of very large sets with high accuracy using only loglog space. It also supports streaming updates and merging sketches, just the same as HyperLogLog.
This repo implements two flavors of HyperMinHash:
p=14
.If you expect to be dealing with low cardinality datasets (<= 80,000 unique elements), we recommend using BetaMinHash as it has a smaller memory footprint and is more accurate than HyperLogLog in the range from 20,000-80,000, holding memory fixed. However, note that different sketch types are not interchangeable i.e: obtaining the intersection of an HMH and a BMH is not currently supported.
Both implementations are equipped with serialization/deserialization capabilities out of the box for sending sketches over the wire or persisting them to disk.
<dependency>
<groupId>com.liveramp</groupId>
<artifactId>hyperminhash</artifactId>
<version>0.2</version>
</dependency>
Set<byte[]> mySet = getMySet();
BetaMinHash sketch = new BetaMinHash();
for (byte[] element : mySet){
sketch.add(element);
}
long estimatedCardinality = sketch.cardinality();
Collection<BetaMinHash> sketches = getSketches();
SketchCombiner<BetaMinHash> combiner = BetaMinHashCombiner.getInstance();
BetaMinHash combined = combiner.union(sketches);
// to get cardinality of the union
long unionCardinality = combined.cardinality();
// using HyperMinHash instead of BetaMinHash
Collection<HyperMinHash> sketches = getSketches();
SketchCombiner<HyperMinHash> combiner = HyperMinHashCombinre.getInstance();
HyperMinHash combined = combiner.union(sketches);
BetaMinHash combined = combiner.union(sketches);
long estimatedCardinality = combined.cardinality();
Collection<BetaMinHash> sketches = getSketches();
SketchCombiner<BetaMinHash> combiner = BetaMinHashComber.getInstance();
long intersectionCardinality = combiner.intersectionCardinality(sketches);
To get a byte[] representation of a sketch, use the IntersectionSketch.SerDe
interface:
HyperMinHash sketch = getSketch();
HyperMinHashSerde serde = new HyperMinHashSerde();
byte[] serialized = serde.toBytes(sketch);
HyperMinHash deserialized = serde.fromBytes(serialized);
int sizeInBytes = serde.sizeInBytes(sketch);
Commit authorship was lost when merging code. The maintainers of the library, in alphabetical order, are:
Thanks to Seif Lotfy for implementing a Golang version of HyperMinHash. We use some of his tests in our library, and our BetaMinHash implementation references his implementation.