Showing cs.DSShow all
3 papers · 1 filter
cs.DS2021
Stretching Your Data With Taffy Filters
Jim Apple
Popular approximate membership query structures such as Bloom filters and cuckoo filters are widely used in databases, security, and networking. These structures represent sets app…
cs.DS2021
HalftimeHash: Modern Hashing without 64-bit Multipliers or Finite Fields
Jim Apple
HalftimeHash is a new algorithm for hashing long strings. The goals are few collisions (different inputs that produce identical output hash values) and high performance. Compared t…
cs.DS2021
Split block Bloom filters
Jim Apple
This short note describes a Bloom filter variant that takes advantage of modern SIMD instructions to increase speed by 30%-450%. This filter, the split block Bloom filter, is used…