Approximate computing "is a computation technique which returns a possibly inaccurate result rather than a guaranteed accurate result," which "can provide disproportionate gains in performance and energy, while still achieving acceptable result accuracy."
This library is a collection of several approximate computing algorithms written in Rust. The goals are: * Ease of use. For maximum adoption, it should be straightforward to make use of AC algorithms with very little effort. * Parallelization. When possible, algorithms should be capable of being parallelized (ie, map-reduce of the core algorithm). This includes serialization of datasets. * Common dependencies. Minimize the dependency chain to reduce build times and binary sizes.
NOTE that I did not write any of these algorithms - they are all implemented by other talented Rustaceans, the repositories for which are linked below. I have, however, added some functionality (serialization/deserialization, exposing new initialization functions, etc.). All source code is MIT- or Apache-licensed.
The algorithms implemented in this library and on the roadmap fall into one of several categories:
These algorithms approxmate counting the number of items in a set within some approximate acceptable error.
rust-hyperloglogrust-count-min-sketch to serve as a frequency table of eventsThese algorithms determine if an item n exists in the set N, guaranteeing no false negatives at the cost of some false positives.
bloom_filterrust-cuckoofilter. like Bloom filter, but can delete items. Can use lower space overhead than BF.