See DeepWiki analysis of this repository.
Probabilistic Data Structures (also known as sketches) sacrifice a little bit of precision to gain a huge advantage in performance, scalability, and memory usage compared to their deterministic counterparts. This article is a good introduction to the topic.
This repository hosts a number of these data structures. Implementations are optimized for clarity and readability and are aimed at educational purposes. The list currently includes the following sketches:
- Bloom filter
- Count-Min Sketch
- HyperLogLog
- Reservoir Sampling