Maybe.NET is a lightweight library of probabilistic data structures for .NET. The library currently features Bloom Filters, Counting Bloom Filters, and Skip Lists. And more data structures are coming soon! Stop scouring the Internet and re-writing the same classes over and over -- use Maybe.NET.
Installation is super simple with NuGet! Just use this command to install from the Visual Studio Package Manager Console:
Install-Package Maybe.NET
Maybe.NET has a clear, intuitive API that is easy to pick up. You can check out the Maybe.Tests project for examples of using each method. Here are some quick examples to get you started.
The bloom filter is a handy collection to which you can add items and check if an item is contained in the collection. They are very fast and memory-efficient, but it comes at a small cost: the filter can definitely say if an item is NOT in the collection, but it can't say for sure that an item is in the collection, only that it MIGHT be. You can use the constructor to specify your targeted maximum rate of errors. (Lower error rates may use more memory)
var filter = new BloomFilter<int>(50, 0.02);
filter.Add(42);
filter.Add(27);
filter.Add(33);
filter.Contains(55); // returns false (the item is NOT in the collection)
filter.Contains(27); // returns true (the item MIGHT be in the collection)
Counting bloom filters extend regular bloom filter functionality by allowing items to be removed from the collection. This can be useful functionality, but it opens the possibility of false negatives.
var filter = new CountingBloomFilter<int>(50, 0.02);
filter.Add(42);
filter.Contains(42); // returns true
filter.Remove(42);
filter.Contains(42); // returns false
Scalable bloom filters offer the same Add and Contains operations that normal BloomFilter offers. The difference is that ScalableBloomFilter only needs to know the max error rate. The capacity of the bloom filter will grow by adding additional bloom filters internally, which allows the developer to add more items to the bloom filter without worrying about incurring too high of a false positive rate.
var filter = new ScalableBloomFilter<int>(0.02); // specifying 2% max error rate, no capacity required
filter.Add(42);
filter.Add(27);
filter.Add(33); // add as many items as needed. The scalable bloom filter will create as many filters as needed to hold data and keep error rates within tolerance.
filter.Contains(55); // returns false (the item is NOT in the collection)
filter.Contains(27); // returns true (the item MIGHT be in the collection)
Skip lists are sort of like a singly linked list, but they have additional links to other nodes further out in the list. The structure of the links is similar to building Binary Search into the Skip List. However, the Skip List uses randomness to avoid expensive balancing operations when the list is being modified. This structure allows for searching in logarithmic time on average, but doesn't incur the cost of balancing a tree that is normally incurred for fast search. See the wikipedia article for detailed information.
var list = new SkipList<int> {42, 33};
list.Contains(42); // returns true
list.Contains(91); // returns false
Count min sketch is a data structure that allows you to track the frequency of an item occurring within a large set. The count min sketch will never undercount items, but it can overcount by a controllable confidence interval. This is great for counting in very large (think big data) datasets where you can't deterministically fit everything into memory.
var sketch = new CountMinSketch<string>(5d, 0.95d, 42);
sketch.Add("test");
sketch.Add("foobar");
var estimate = sketch.EstimateCount("test"); // returns 1
Count min sketch also supports merging for parallel work. You can divide your workload and process in multiple Count Min Sketches in parallel. Then, merge the sketches from each workload at the end to see the overall result. Just make sure to initialize the sketches with the same configuration.
Contributions are always welcome! Please feel free to submit pull requests and to open issues. I prefer to have tests on all public methods if possible and where ever else makes sense.
Free to use under MIT license