tag

#probabilistic

3 pages tagged

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.13 Count-Min Sketch

5.13 Count-Min Sketch Problem You need approximate frequency counts for a large stream of keys, and an exact counting map would use too much memory. A counting map stores one entry per distinct key. This is exact, but memory grows with the number of distinct keys. In a large log stream, network trace, search query stream, or telemetry pipeline, the number of distinct keys may be too large to store...
algorithms hashing probabilistic data-structures streaming May 4, 2026
Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.12 Bloom Filters

5.12 Bloom Filters Problem You need to test whether a key is in a set using very little memory, and you can tolerate occasional false positives but not false negatives. A standard hash set stores all keys explicitly. This gives exact answers but uses memory proportional to the number of keys. For large-scale or streaming data, this can be too expensive. Solution Use a Bloom filter. It is a bit...
algorithms hashing bloom-filter probabilistic data-structures May 4, 2026
Wiki › Algorithms › 02. Data Structures › 3. Specialized, Persistent, Concurrent, and External Structures ›

3.7 Probabilistic Data Structures

3.7 Probabilistic data structures, 15 index slug name 1 probabilistic-data-structure Probabilistic Data Structure 2 bloom-filter-probabilistic Bloom Filter 3 counting-bloom-filter-probabilistic Counting Bloom Filter 4 cuckoo-filter-probabilistic Cuckoo Filter 5 quotient-filter-probabilistic Quotient Filter 6 xor-filter-probabilistic XOR Filter 7 count-min-sketch Count Min Sketch 8 count-sketch Count Sketch 9 hyperloglog HyperLogLog 10 minhash MinHash 11 reservoir-sampling Reservoir Sampling 12 skip-list Skip List 13 treap-probabilistic Treap 14 randomized-meldable-heap Randomized Meldable Heap 15 probabilistic-invariant-check Probabilistic Invariant Check
algorithms data-structures probabilistic