Displaying 1 to 8 from 8 results

BoomFilters - Probabilistic data structures for processing continuous, unbounded streams.

  •    Go

Boom Filters are probabilistic data structures for processing continuous, unbounded streams. This includes Stable Bloom Filters, Scalable Bloom Filters, Counting Bloom Filters, Inverse Bloom Filters, Cuckoo Filters, several variants of traditional Bloom filters, HyperLogLog, Count-Min Sketch, and MinHash.Classic Bloom filters generally require a priori knowledge of the data set in order to allocate an appropriately sized bit array. This works well for offline processing, but online processing typically involves unbounded data streams. With enough data, a traditional Bloom filter "fills up", after which it has a false-positive probability of 1.

cfilter - Cuckoo Filter implementation in Go, better than Bloom Filters (unmaintained, unfortunately)

  •    Go

Cuckoo filter is a Bloom filter replacement for approximated set-membership queries. Cuckoo filters support adding and removing items dynamically while achieving even higher performance than Bloom filters. For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters. Some possible use-cases that depend on approximated set-membership queries would be databases, caches, routers, and storage systems where it is used to decide if a given item is in a (usually large) set, with some small false positive probability. Alternatively, given it is designed to be a viable replacement to Bloom filters, it can also be used to reduce the space required in probabilistic routing tables, speed longest-prefix matching for IP addresses, improve network state management and monitoring, and encode multicast forwarding information in packets, among many other applications. Cuckoo filters provide the flexibility to add and remove items dynamically. A cuckoo filter is based on cuckoo hashing (and therefore named as cuckoo filter). It is essentially a cuckoo hash table storing each key's fingerprint. Cuckoo hash tables can be highly compact, thus a cuckoo filter could use less space than conventional Bloom filters, for applications that require low false positive rates (< 3%).

cuckoofilter - An implementation of Cuckoo Filters in Go

  •    Go

This is an implementation of a data structure known as a cuckoo filter. The data structure is described in a paper called Cuckoo Filter: Practically Better Than Bloom by Bin Fan, David G. Andersen, Michael Kaminsky and Michael D. Mitzenmacher. Cuckoo filters, like Bloom filters, are probabilistic data structures useful for determining whether a piece of data is present in a set. Like Bloom filters, cuckoo filters do not store the key being looked up, or the value of the data, so they are appropriate only for checking whether the primary data source should be queried.

cuckoo-filter - Cuckoo Filter: Practically better than bloom filter

  •    Go

Practically better than Bloom Filter. Cuckoo filters support adding and removing items dynamically while achieving even higher performance than Bloom filters. For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters. It is a compact variant of a cuckoo hashtable that stores only fingerprints—a bit string derived from the item using a hash function—for each item inserted, instead of key-value pairs. The filter is densely filled with fingerprints (e.g., 95% entries occupied), which confers high space efficiency. Paper can be found here.




cuckooc - A service to manage your Cuckoo filters

  •    Go

Cuckoo Cluster manages all of your Cuckoo Filters. Cuckoo filter, Practically better than Bloom Filter, support adding and removing items dynamically while achieving even higher performance than Bloom filters. For applications that store many items and target moderately low false positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters. It is a compact variant of a cuckoo hash table that stores only fingerprints —a bit string derived from the item using a hash function— for each item inserted, instead of key-value pairs. The filter is densely filled with fingerprints (e.g., 95% entries occupied), which confers high space efficiency. Installation assumes that you have Go environment configured.

cuckoo - :bird: Cuckoo Filters in Elixir

  •    Elixir

Cuckoo is a pure Elixir implementation of a Cuckoo Filter. Add Cuckoo as a dependency in your mix.exs file.

CuckooFilter - Substitute for bloom filter.

  •    C

A key-value filter using cuckoo hashing, substituting for bloom filter. Define CUCKOO_DBG in cuckoo_filter.h to open debug logging.

bloom-filters - JS implementation of probabilistic data structures: Bloom Filter (and its derived), HyperLogLog, Count-Min Sketch, Top-K and MinHash

  •    Javascript

A Bloom filter is a space-efficient probabilistic data structure, conceived by Burton Howard Bloom in 1970, that is used to test whether an element is a member of a set. False positive matches are possible, but false negatives are not. A Partitioned Bloom Filter is a variation of a classic Bloom Filter.