Quotient filter

Quotient filter — це імовірнісна структура даних, що дозволяє перевірити належність елемента множині. Вона описана в 2011 р. як заміна фільтру Блума. Відповідь може бути:
— елемент точно не належить множині;
— елемент можливо належить множині.



Структура


У структурі зберігаються хеші елементів, які належать множині S:

F = h(S) = {h(x) | x in S}

Саме тому структура імовірнісна.
Припустимо, ми шукаємо елемент A. Обчислюємо його хеш і шукаємо в структурі.
Ситуація 1: хеш елемента не був знайдений. Відповідь — елемент точно не належить множині.
Ситуація 2: при пошуку знайдений хеш, але не можна сказати точно, чи належить він елементу A. Іноді буває, що хеші двох різних елементів збігаються(це збіг називається повною колізією — hard collision). Тому не можна сказати точно, чи знайшли ми хеш елемента A або це була колізія. Відповідь — елемент можливо належить множині.

Фільтр можна представити у вигляді хеш-таблиці T з m = 2 ^ q групами хешей. Для розподілу хешей по групах використовується метод «quotienting»(звідси і назва фільтру). Метод був запропонований Батогом(The Art of Computer Programming:Searching and Sorting, volume 3. Section 6.4, exercise 13).
Хеш розбивається на 2 частини:
приватне(quotient) fq = f / (2 ^ r)
залишок(remainder) fr = f mod (2 ^ r)
У результаті додавання хеша f у фільтр зводиться до додавання частини fr в групу T[fq]. Повний хеш відновлюється за формулою:
f = fq * (2 ^ r) + fr.

Формула(взято з [2])


Таблиця T зберігається у вигляді масиву A[0..m — 1] елементів за довжиною (r + 3) біта. Кожен слот масиву зберігає залишок від хеша і 3 біта інформації, необхідної для відновлення хеша.

Якщо у 2 хешей збігаються приватні, то це називається м'якою колізією(soft collision). Всі хеши, у яких збігаються приватні, зберігаються в масиві послідовно відрізку(run). При цьому завжди виконується умова: якщо fq1 < fq2, то fr1 знаходиться в масиві завжди перед fr2.

Інформаційні біти


Давайте розберемося, що роблять додаткові 3 біта, що зберігаються з кожним залишком.
1. біт зайнятості(is occupied). Якщо у слота i стоїть цей біт, то в масиві є хеш, у якого приватне fq = i(але воно може бути не в цьому слоті, а зміщене далі).
2. біт усунення(is shifted). Якщо він виставлений, це означає, що зберігається в слоті i залишок не належить групі i, а просто був зміщений.
3. біт продовження(is continuation). Якщо у слота i стоїть цей біт, то що зберігається в ньому залишок належить тому ж відрізку, що і залишок, який зберігається в попередньому слоті i — 1.

Якщо біт зміщення = 0, то у слоті i зберігається залишок, що належить цій слоту(fq = i). Біт продовження дозволяє зрозуміти, коли закінчується відрізок. Біт зайнятості дозволяє визначити слот, якому належить відрізок.

Добре описані комбінації у Вікіпедії([2])

is_occupied
__is_continuation
____is_shifted
0 0 0: Empty Slot
0 0 1: Slot is holding start of run that has been shifted from its canonical slot.
0 1 0: not used.
0 1 1: Slot is holding continuation of run that has been shifted from its canonical slot.
1 0 0: Slot is holding start of run that is in its canonical slot.
1 0 1: Slot is holding start of run that has been shifted from its canonical slot.
Also the run for which this is the canonical slot exists but is shifted right.
1 1 0: not used.
1 1 1: Slot is holding continuation of run that has been shifted from its canonical slot.
Also the run for which this is the canonical slot exists but is shifted right.

Група відрізків, які йдуть підряд без порожніх слотів між ними називається кластером(cluster). Перший слот кластера завжди не зміщений(біт зміщення = 0).

Приклад(взято з [1])


Зверху зображено хеш-таблиця T. У багатьох елементів збігаються приватні, наприклад у a і b. Знизу зображений масив, у якому ці елементи зберігаються.

Пошук елемента


Знаходимо хеш елемента f, який потім розбиваємо на приватне fq і залишок fr. Перевіряємо слот fq в масиві. Якщо він порожній — елемент не міститься у фільтрі.
Якщо ж слот зайнятий, то необхідно знайти початок відрізка. Початок відрізка може знаходиться в належному йому слоті, а може бути і зміщене іншим відрізком, тому шукаємо початок кластера.
Спочатку ми йдемо вліво від нашого слоти fq, поки не знайдемо початок кластера(біт зміщення = 0). Поки ми йдемо вліво, запам'ятовуємо число відрізків, яке ми проскочили. Кожен слот з виставленим бітом зайнятості — початок відрізка. З кожним таким слотом збільшуємо лічильник відрізків.
Знайшовши початок кластера, починаємо рухатися вправо. Кожен слот з невыставленным бітом продовження є початком нового відрізка, тобто попередній відрізок закінчився. З кожним таким слотом зменшуємо лічильник відрізків. Коли лічильник обнулиться — ми знайшли потрібний нам відрізок. Біжимо за ним і порівнюємо з нашим залишком fr. Якщо відрізок закінчився, а залишок не знайдено елемента точно немає у фільтрі. Якщо він був знайдений, то можливо елемент знаходиться в фільтрі.

Приклад(взято з [2])


Шукаємо елемент e. Обчислюємо його хеш, ділимо хеш на приватне eq і залишок er. eq = 4. У слоті 4 стоять біти зайнятості і зміщення (в ньому знаходиться залишок dr), отже елемент у цьому слоті є, але він був зміщений. Шукаємо початок кластера.
Рухаючись вліво запам'ятовуємо, що ми пройшли 3 відрізка(біт зайнятості = 1 для слотів 4, 2, 1). Слот 1 — початок кластера(біт зміщення = 0), рухаємося вправо. Початок кожного відрізка — слот з бітом продовження = 0. Для 1-ого відрізка — слот 1, для 2-ого відрізка — слот 4, для 3-його — слот 5. Перевіряємо кожен залишок у 3-му відрізку, починаючи з слоти 5. У 3-му відрізку всього один залишок, і він співпадає з обчисленим нами er. Відповідь — елемент можливо належить множині.

Вставка / видалення елемента


Спочатку ми виставляємо(для вставки, видалення навпаки прибираємо) біт зайнятості для слота A[fq]. Після цього за таким же алгоритмом, що і пошук елемента, шукаємо слот для fr. Знайшовши слот, вставляємо/видаляємо fr і зміщуємо елементи, якщо необхідно.
При зміщенні елементів біт зайнятості не змінюється. Якщо залишок був вставлений в початок відрізка, то залишок, який займав цей слот, зміщується і стає продовженням відрізка, тому виставляється біт продовження. Для кожного залишку, який був зміщений, ставимо біт зміщення.

Приклад(взято з [2])


Відбувається вставка елементів c і d.
bq = 1, cq = 1, br < cr, тому залишок cr вставляється в слот 2, проставляються біти продовження і зміщення у слота 2.
dq = 2, тому у слота 2 проставляється біт зайнятості. Але слот 2 вже зайнятий, тому dr потрапляє в слот 3, проставляється біт зміщення у слоти 3.

Відмінності від фільтра Блума


Навіщо взагалі вся ця складна система? Є кілька переваг:
1. Всі дані розташовані послідовно у пам'яті. Необхідно завантажити тільки потрібний кластер, який, як правило, невеликий, а не весь масив цілком. Це зменшує кількість промахів з читання з кеша даних процесора.
2. Можливість зменшувати / збільшувати розмір масиву. Для цього не треба заново хэшировать дані, достатньо один біт перенести залишку у приватне або навпаки.
3. Злиття(merge) двох фільтрів в один.

Посилання


1. vldb.org/pvldb/vol5/p1627_michaelabender_vldb2012.pdf — опис фільтра від авторів
2. en.wikipedia.org/wiki/Quotient_filter — чудова стаття на Вікіпедії

Про помилки та неточності пишіть з радістю виправлю.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.