Quotient filter

A quotient filter is a space-efficient probabilistic data structure used to test whether an element belongs to a set, a task known as an approximate membership query. A query returns either that the element is definitely not in the set or that it is probably in the set, so there are no false negatives but a false positive rate that trades off against storage size: a larger filter lowers it, while adding more elements raises it. It supports insert and query, optionally delete, and unlike many similar filters it can be merged and resized without re-hashing the original keys, which benefits log-structured merge-trees. A typical use is as a fast proxy for the keys of a database on disk, consulted before the slower lookup.