4 releases
0.2.2 | Aug 19, 2024 |
---|---|
0.2.1 | Aug 19, 2024 |
0.2.0 | Aug 15, 2024 |
0.1.0 | Aug 9, 2024 |
#259 in Algorithms
71KB
1.5K
SLoC
HyperTwoBits
is a probabilistic data structure
that estimates the number of distinct elements in a set. It has the same use case as HyperLogLog
,
but it uses less memory and is faster while achieving roughly similar accuracy. In numbers while
HyperLogLog
uses six bits per substream HyperTwoBits
uses, as the name suggests, two bits
To illustrate Tabe 4 from the linked paper page 14:
This implementation improves on the proposed algorithm in a few ways.
- It holds the entire sketch in the stack without heap allocations.
- It defaults to
ahash
for hashing, but you can use any hasher that implementsstd::hash::AHasherBuilder
. - It uses traits to remove branches from the runtime execution.
- It moves as much of the computation as possible into constants or compile-time evaluation.
- It removes float comparisons in favor of integer operations. It uses 128-bit integers to take advantage of wide registers where possible.
- It uses intrinsics to count ones instead of computing them over binary logic.
- It changes the register layout for high/low bits in the scatch to colocate the memory for each region.
- It adds micro batching functions that improve performance when two or four values can be provided at the same time.
Example
use hypertwobits::{HyperTwoBits, M512};
let mut htb = HyperTwoBits::<M512>::default();
htb.insert(&"foo");
htb.insert(&"bar");
htb.count();
Seeded Hash vs. Unseeded Hash
By default, HyperTwoBits
uses ahash
as the hasher. This hasher is not seeded with a random
value by default. This means that the same input will always produce the same output.
Unlike HashMap's the attack surface this opens up is minimal. The only way to exploit this is to craft an input that would deliberately return imprecise results. This is a non-issue for most use cases.
However, we provide the AHasherBuilder
that creates a random state that is used to seed the hasher.
The tradeoff is that this will be slower, use more memory and means sketches can no longer be merged.
Benchmarks
Based on benchmarks it is about 2 times faster than HyperLogLogPlus
and 1.5x faster than HyperBitBit
or respectively 4x and 2.5x faster when used with non-seeded hashers.
Accuracy
The accuracy of HyperTwoBits
is roughyly similar to HyperLogLog
but significantly inferior to HyperLogLogPlus
. A few measurements based on example inputs:
Shakespeare
Ulysses
War and Peace
Dependencies
~1–1.3MB
~20K SLoC