- Bloom filter
- Імовірнісна структура для перевірки належності до множини: «точно ні» або «можливо так».
- m
- Розмір бітового масиву фільтра.
- n
- Кількість доданих елементів.
- k
- Кількість хеш-функцій, тобто бітів, які вмикає і перевіряє кожен елемент.
- False positive
- Хибне «так»: фільтр каже «можливо є», а елемента не додавали.
- False negative
- Хибне «ні». У звичайному фільтрі Блума його не буває, якщо нічого не видаляти.
- FPR, p
- Частка хибних «так» серед перевірок елементів, яких немає.
- Double hashing
- Отримання k позицій з двох хешів: h₁ + i·h₂.
- Counting Bloom filter
- Лічильники замість бітів, тому підтримує видалення.
- Scalable Bloom filter
- Ланцюжок фільтрів, що ростуть, для невідомого наперед n.
- Cuckoo filter
- Зберігає короткі відбитки ключів у хеш-таблиці; підтримує видалення.
- Xor / binary fuse filter
- Статичні фільтри: компактніші за Bloom, але будуються раз із готового набору.
- SSTable / LSM
- Незмінні відсортовані файли в базах на LSM-деревах; кожен має свій фільтр.
- Count-Min sketch
- Родич фільтра Блума для наближеного підрахунку частот.
- HyperLogLog
- Структура для наближеного підрахунку кількості різних елементів.