Probabilistic Data Structure

A Probabilistic Data Structure is a data structure that ...

• Example(s):
  • Bloom Filter.
  • Locality-Sensitive Hash Function.
  • Count–Min Sketch.
  • MinHash.
  • Quotient Filter.
  • Random Binary Tree.
  • Skip List.
  • …
• Counter-Example(s):
  • a Deterministic Data Structure.
• See: Randomized Algorithm, Hash-Table.

---

---

References

• http://wikipedia.org/wiki/Category:Probabilistic_data_structures

---