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 continuation). Если у слота i стоит этот бит, то хранящийся в нем остаток принадлежит тому же отрезку, что и остаток, хранящийся в предыдущем слоте i — 1.
    3. бит смещения(is shifted). Если он выставлен, это значит, что хранящийся в слоте i остаток не принадлежит группе i, а просто был смещен.

    Если бит смещения = 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. Ответ — элемент возможно принадлежит множеству.

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


    По такому же алгоритму, что и поиск элемента, ищем слот для fr. Найдя слот, вставляем/удаляем fr и смещаем элементы, если необходимо. Потом выставляем (для вставки) или убираем(для удаления и если удаляемый элемент был единственным с частным = fq) бит занятости для слота A[fq].
    При смещении элементов бит занятости не меняется. Если остаток был вставлен в начало отрезка, то остаток, занимавший этот слот, смещается и становится продолжением отрезка, поэтому выставляется бит продолжения. Для каждого остатка, который был смещен, ставим бит смещения.

    Пример(взят из [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 — отличная статья на Википедии

    Об ошибках и неточностях пишите — с радостью исправлю.
    Поделиться публикацией

    Комментарии 16

      +2
      Спасибо, даешь больше такого хардкора на Хабре!

      1.
      Давайте разберемся, что делают дополнительные 3 бита, хранящиеся с каждым остатком
      … дальше биты перечислены в одном порядке, а потом на диаграммах везде они в другом. Сбивает.

      2.
      Проверяем слот fq в массиве. Если он пустой — элемент не содержится в фильтре.

      Скорее «Если бит is_occupied не выставлен»?

      3.
      Сначала мы выставляем(для вставки, для удаления наоборот убираем) бит занятости для слота A[fq]

      Удалять скорее надо в конце, только если удаланный хеш был единственным в таблице с этим fq.

      4. (Мысли вслух) Чтобы работа с таблицей не была совсем адом, слот должен занимать целое число байт, т. е. 8, 16, 24, 32, 40, 48, 56 или 64 бита (больше вряд ли имеет смысл, нереализуемо на языках без интринсиков и т. д.). Значит, остаток будет 5, 13, 21, 29, 37, 45, 53 или 61 бит. Значит, модуль (размер таблицы) должен быть 2^19 или 2^11 (при 32- или 64-битном хеше), 2^27 или 2^35 при 64-битном. Размер 2^3 (8 слотов) или 2^43 и больше — едва ли имеют практический смысл. 2^27 при 32-битном хеше — проще, наверное, просто битсет сделать на 2^32 элемента.

      Выбор невелик. Может имеет смысл поменять местами остаток и частное, тогда выбор вариантов вариантов увеличится? Или нет?

      5. (Мысли вслух) Не знаю насчет вероятностной структуры данных, замены фильтра Блума и прочих пафосных формулировок, по-моему это просто хеш-таблица целых чисел, где выигрывается ((log 2 от размера таблицы) — 3) бита на слот для хранения информации, за счет серьезного усложнения операций. Имеет ли это какой-то смысл — большой вопрос. Чтобы выигрыш был более-менее заметным, модуль должен быть большим, то есть скорее только 2^27 и 2^35 при 64-битном хеше (выигрыш 24 и 32 бита соответственно, 37,5% и 50%), и только 2^19 при 32 битном хеше (выигрыш 16 бит, 50%).

      Вывод: эта структура имеет смысл (в первую очередь, или вообще только), если у вас ~ 2^18 элементов = 250 тысяч при 32-битном хеше, ~ 2^26 = 32 миллиона или 2^34 = 16 миллиардов элементов, при 64-битном хеше.
        0
        Хотя, по сути дела, кроме 32 бит на слот будет ад даже при целом числе байт на слот, но зато только одно чтение из памяти для получения первого слота (который, по задумке, должно быть чаще всего единственным полученным слотом на операцию, если нет коллизий и кластеров).
          0
          Огромное спасибо за замечания!
          1, 2 и 3 вроде исправил.

          4. Жаль, я потерял линк на реализацию на С от авторов. В других реализациях(например github.com/vedantk/quotient-filter) используются 64-битные хэши.
          Может имеет смысл поменять местами остаток и частное

          Как я уже писал, размеры частного и остатка можно менять, всё зависит от ситуации, данных и их количества.

          5. Авторы проводят тесты с миллионами элементов, так что структуру действительно нет смысла использовать на очень маленьких выборках. При большом количестве элементов, когда коэффициент заполнения(load factor) становится высоким, можно организовать каскад фильтров. Это описано в [1], стр. 6
            +1
            4. Я имел ввиду хранить в таблице частное, а индексировать слоты остатком. Хотя нет никакой разницы, наверное. Просто это было бы более натурально с точки зрения обычных хеш-таблиц, где индексируют именно остатком: index = hash % table_size, а что там в качестве операции модуля, целочисленное деление или битовая маска, это вопрос второй. По смыслу, как бы, индекс = остаток это более натурально, чем индекс = частное.

            5. При большом заполнении я бы просто взял таблицу побольше. Или авторы тоже подвязываются на всего несколько фиксированных размеров таблиц, которые я перечислил, и используют их для хранения любого числа элементов путем изменения числа таблиц?
              0
              4. Не знаю, с такой точки зрения на частное — остаток я не смотрел. В принципе, можно и так сделать.
              5. Авторы предлагают держать в памяти таблицу размера q0(размер таблицы ограничен размером оперативной памяти). Когда она сильно заполняется, она сливается с таблицей размера q1 > q0, которая хранится на SSD. А таблица в оперативной памяти очищается. Если при слиянии таблица с размером q1 тоже заполнилась, то она сливается с другой таблицей с размером q2 > q1, которая тоже хранится на SSD, а затем очищается. И т. д.
              Насколько помню, размер таблиц не фиксирован.
              Вообще, этот cascade filter из quotient filters основан на другой структуре — cache-oblivious lookahead array(COLA) (подробнее здесь supertech.csail.mit.edu/papers/sbtree.pdf). Надеюсь, кто-нибудь напишет и об этом)) Я пока не изучал эту тему.
          0
          А какой фильтр компактнее, Quotient filter или bloom filter?
          (естественно, при одинаковой вероятности ошибки)
            0
            Если не ошибаюсь, то Bloom filter.
              0
              Хм, в википедии написано, что «одного порядка», но для bloom filter я знаю формулу расчёта, а для этого фильтра пока не нашёл.
                +1
                m = table_size * slot_size
                slot_size = hash_size — log2 table_size + 3
                table_size = n_hashes * 2 // (0.5 load factor)
                n_hashes = n * (1 — error_p)
                error_p = hard_collision_p = 1 — (1 — 1/ 2^hash_size) ^ n

                m = n * ((1 — 1/ 2^hash_size) ^ n) * 2 * (hash_size — (log2 n * ((1 — 1/ 2^hash_size) ^ n) * 2) + 3)
                  0
                  error_p = hard_collision_p = 1 — (1 — 1/ 2^hash_size) ^ n
                  Это неправда, шанс не получить коллизию для n ключей, если всевозможных вариантов ключей — k, равен:
                  (1 – 1/k)(1 – 2/k)...(1 – n/k)
                  а не как у вас:
                  (1 – 1/k)n

                  Если взять в качестве примера известный "парадокс дней рождения", то для n = 23 и k = 365, по вашей формуле имеем (364/365)23 ≈ 94%, а на самом деле там около 50%.
                  Если хотите, то можно оценить это произведение снизу как (1 – n/k)n
                    0
                    Я понимал, что формула неверная, точнее было лень думать, но недооценил силу эффекта.
                  –1
                  m = n * ((1 — 1/ (1/(1 — log n (1 — error_p)))) ^ n) * 2 * (log 2 (1/(1 — log n (1 — error_p))) — (log2 n * ((1 — 1/ (1/(1 — log n (1 — error_p)))) ^ n) * 2) + 3)
                    –1
                    Надо бы упростить :)
                    0
                    Порядок действительно один — O(n), где n — размер фильтра.
                    Для Bloom filter количество бит, задействованных на хранение одного элемента, <= количество хэш-функций(меньше потому, что 1 бит может быть использован для хранения сразу нескольких элементов — произошла коллизия в одной из хэш-функций). Не знаю, лично я не слышал про кол-во хэш-функций > 15.
                    Для Quotient filter количество бит, задействованных на хранение одного элемента, ~= 60.

                    Написал всё это и увидел дополнение
                    (естественно, при одинаковой вероятности ошибки)

                    В quotient filter используется только одна хэш-функция. В этом смысле Bloom filter с набором хэш-функций всегда будет впереди. При использовании в Bloom filter только одной хэш-функции получаем 1 бит на элемент, тогда как в quotient filter всё те же ~= 60 бит.
                    Правда, в quotient filter допускаются коллизии, вставляется просто еще одна копия хэша.
                    Кстати, формула вероятности ошибки для quotient filter выводится в [1], стр. 4

                    Это только моё личное мнение, я могу ошибаться.
                      0
                      количество бит на слот может быть какое угодно, в теории. От этого зависит вероятность ошибки. Выше я попробовал вывести формулу зависящую только от вероятности ошибки и кол-ва элементов
                        0
                        Согласен. Я взял примерные значения, т. к. оценить порядок с помощью формул достаточно сложно.

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое