Matches in DBpedia 2014 for { <http://dbpedia.org/resource/Quotient_filter> ?p ?o. }
Showing items 1 to 15 of
15
with 100 items per page.
- Quotient_filter abstract "A quotient filter, introduced by Bender, Farach-Colton, Johnson, Kuszmaul, Medjedovic, Montes, Shetty, Spillane, and Zadok in 2011, is a kind of approximate membership query (AMQ).An AMQ is a space-efficient probabilistic data structure used to test whether an element is a member of a set. 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.e., the test does not generate false negatives. 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.e., a false positive). 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 that are added to the set, the larger the probability of false positives.Each AMQ is associated with a more space-consuming set, such as a B-tree, and its contents are reflective of the associated set. As elements – key/value pairs – are added to the set, their keys are also added to the AMQ. However the AMQ stores only a few bits per key, whereas the set stores the entire key, which can be of arbitrary size; therefore, an AMQ can often be memory-resident while the associated set is stored in slower secondary storage. Thus this association can dramatically improve the performance of membership tests, because a test that results in "absent" can be resolved by the AMQ without necessitating any I/Os to access the set itself.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 log-structured merge-trees.".
- Quotient_filter thumbnail Bloom_filter_speed.svg?width=300.
- Quotient_filter wikiPageID "36476171".
- Quotient_filter wikiPageRevisionID "605195136".
- Quotient_filter hasPhotoCollection Quotient_filter.
- Quotient_filter subject Category:Hashing.
- Quotient_filter subject Category:Probabilistic_data_structures.
- Quotient_filter comment "A quotient filter, introduced by Bender, Farach-Colton, Johnson, Kuszmaul, Medjedovic, Montes, Shetty, Spillane, and Zadok in 2011, is a kind of approximate membership query (AMQ).An AMQ is a space-efficient probabilistic data structure used to test whether an element is a member of a set. 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.".
- Quotient_filter label "Quotient filter".
- Quotient_filter sameAs m.0kbgrzv.
- Quotient_filter sameAs Q7272897.
- Quotient_filter sameAs Q7272897.
- Quotient_filter wasDerivedFrom Quotient_filter?oldid=605195136.
- Quotient_filter depiction Bloom_filter_speed.svg.
- Quotient_filter isPrimaryTopicOf Quotient_filter.
