Premium
Stretching your data with taffy filters
Author(s) -
Apple Jim
Publication year - 2022
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.3129
Subject(s) - bloom filter , hash function , false positive paradox , computer science , set (abstract data type) , data structure , hash table , algorithm , lookup table , data set , theoretical computer science , arithmetic , data mining , mathematics , artificial intelligence , programming language
Popular approximate membership query structures such as Bloom filters and cuckoo filters are widely used in databases, security, and networking. These structures represent sets approximately, and support at least two operations—insert and lookup; lookup always returns true on elements in the structure; it also returns true with some probabilityε $$ \varepsilon $$ on elements not in the structure. These latter elements are called false positives. Compensatory for these false positives, filters can be much smaller than hash tables that represent the same set. However, unlike hash tables, cuckoo filters, and Bloom filters must be initialized with the intended number of maximum entries, and cannot grow larger—inserts beyond this number fail or significantly increase the false positive probability. This article presents designs and implementations of filters than can grow without inserts failing and without meaningfully increasing the false positive probability, even if the filters are created with a small initial size. The resulting code is available on GitHub under a permissive open source license.