SYSTEMS AND METHODS FOR PROVIDING AN ADAPTIVE ATTENTION-BASED BLOOM FILTER FOR TREE-BASED INFORMATION REPOSITORIES

摘要

A system described herein may use a Bloom filter to reduce unnecessary accesses to memory. The filter may provide constant search time through hashing and use a relatively small amount of space. The filter may utilize hashing functions to generate a key associated with each data item of a set of data items, where the bit length of the key may be calibrated and tuned for selection of a minimum key length (in number of bits) versus a desired false positive rate. Such keys may be combined to form the filter. The resulting filter may be compared to various request keys that are generated using the same hashing functions in order to determine whether a requested item is present in the associated memory. The keys may be compared to the filter by comparing each bit in the key to each bit of the filter at the same location.