HyperMinHash: MinHash in LogLog space.
basic_science · Level V
Where this comes from
- Record sourced from PubMed, PMID 38288326.
- Also identified by DOI 10.1109/tkde.2020.2981311 and PMC identifier 10824537.
- No licence information is recorded for this record.
- Because redistribution is not established, this page shows the abstract only. Follow the links below for the full text.
Abstract
In this extended abstract, we describe and analyze a lossy compression of MinHash from buckets of size <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo>(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mspace></mspace><mi>n</mi><mo>)</mo></math> to buckets of size <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo>(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mspace></mspace><mi>l</mi><mi>o</mi><mi>g</mi><mspace></mspace><mi>n</mi><mo>)</mo></math> by encoding using floating-point notation. This new compressed sketch, which we call HyperMinHash, as we build off a HyperLogLog scaffold, can be used as a drop-in replacement of MinHash. Unlike comparable Jaccard index fingerprinting algorithms in sub-logarithmic space (such as b-bit MinHash), HyperMinHash retains MinHash's features of streaming updates, unions, and cardinality estimation. For an additive approximation error <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>ϵ</mi></math> on a Jaccard index <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>t</mi></math>, given a random oracle, HyperMinHash needs <math xmlns="http://www.w3.org/1998/Math/MathML"><mi>O</mi><mo>(</mo><mrow><msup><mrow><mi>ϵ</mi></mrow><mrow><mo>-</mo><mn>2</mn></mrow></msup><mo>(</mo><mrow><mi>l</mi><mi>o</mi><mi>g</mi><mspace></mspace><mi>l</mi><mi>o</mi><mi>g</mi><mspace></mspace><mi>n</mi><mo>+</mo><mi>l</mi><mi>o</mi><mi>g</mi><mspace></mspace><mfrac><mrow><mn>1</mn></mrow><mrow><mi>ϵ</mi></mrow></mfrac></mrow></mrow><mo>)</mo><mo>)</mo></math> space. HyperMinHash allows estimating Jaccard indices of 0.01 for set cardinalities on the order of <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mn>10</mn></mrow><mrow><mn>19</mn></mrow></msup></math> with relative error of around 10% using 2MiB of memory; MinHash can only estimate Jaccard indices for cardinalities of <math xmlns="http://www.w3.org/1998/Math/MathML"><msup><mrow><mn>10</mn></mrow><mrow><mn>10</mn></mrow></msup></math> with the same memory consumption.