Time To Replace Your Filter: How Maplets Simplify System Design
By: Michael A. Bender , Alex Conway , Martín Farach-Colton and more
Potential Business Impact:
Stores data faster and uses less computer memory.
Filters such as Bloom, quotient, and cuckoo filters are fundamental building blocks providing space-efficient approximate set membership testing. However, many applications need to associate small values with keys-functionality that filters do not provide. This mismatch forces complex workarounds that degrade performance. We argue that maplets-space-efficient data structures for approximate key-value mappings-are the right abstraction. A maplet provides the same space benefits as filters while natively supporting key-value associations with one-sided error guarantees. Through detailed case studies of SplinterDB (LSM-based key-value store), Squeakr (k-mer counter), and Mantis (genomic sequence search), we identify the common patterns and demonstrate how a unified maplet abstraction can lead to simpler designs and better performance. We conclude that applications benefit from defaulting to maplets rather than filters across domains including databases, computational biology, and networking.
Similar Papers
Learned LSM-trees: Two Approaches Using Learned Bloom Filters
Data Structures and Algorithms
Makes computer storage faster and use less memory.
Smaller and More Flexible Cuckoo Filters
Data Structures and Algorithms
Makes computer memory smaller and faster.
Blocked Bloom Filters with Choices
Databases
Saves computer space, finds data faster.