Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Quotient filter
open-in-new
<p>A quotient filter is a space-efficient <a href="/facts/Probabilistic/fgYvMhwb">probabilistic</a> <a href="/facts/Data_structure/yNsNvL1I">data structure</a> used to test whether an <a href="/facts/Element_(mathematics)/Q2mx1vHL">element</a> is a member of a <a href="/facts/Set_(computer_science)/ovoXUmF9">set</a> (an <a href="/facts/Approximate_Membership_Query_Filter/0IvoWwlK">approximate membership query filter</a>, AMQ). A query will elicit a reply specifying either that the element is definitely not in the set or that the element is probably in the set. The former result is definitive; <i>i.e.</i>, the test does not generate <a href="/facts/Type_I_and_type_II_errors/aazbF3fq">false negatives</a>. But with the latter result there is some probability, ε, of the test returning "element is in the set" when in fact the element is not present in the set (<i>i.e.</i>, a <a href="/facts/Type_I_and_type_II_errors/aazbF3fq">false positive</a>). There is a tradeoff between ε, the false positive rate, and storage size; increasing the filter's storage size reduces ε. Other AMQ operations include "insert" and "optionally delete". The more elements are added to the set, the larger the probability of false positives. </p> <p>A typical application for quotient filters, and other AMQ filters, is to serve as a proxy for the keys in a <a href="/facts/Database/VYcpkevb">database</a> on disk. As keys are added to or removed from the database, the filter is updated to reflect this. Any lookup will first consult the fast quotient filter, then look in the (presumably much slower) database only if the quotient filter reported the presence of the key. If the filter returns absence, the key is known not to be in the database without any disk accesses having been performed. </p><p>A quotient filter has the usual AMQ operations of insert and query. In addition it can also be merged and re-sized without having to re-hash the original keys (thereby avoiding the need to access those keys from secondary storage). This property benefits certain kinds of <a href="/facts/Log-structured_merge-tree/ReV5xQcr">log-structured merge-trees</a>. </p>