hypertwobits 0.2.0

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 implements std::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.

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.

use hypertwobits::{HyperTwoBits, M512};
let mut htb = HyperTwoBits::<M512>::default();
htb.insert(&"foo");
htb.insert(&"bar");
htb.count();