Приблизительный фильтр запроса на членство

Фильтры запросов приблизительного членства (далее фильтры AMQ) включают группу малогабаритных вероятностных структур данных, которые поддерживают запросы приблизительного членства. Приблизительный запрос на членство отвечает на вопрос, находится ли элемент в наборе или нет, с частотой ложных срабатываний $\epsilon$ .

Фильтры Блума — наиболее известный фильтр AMQ, но существуют и другие фильтры AMQ, которые поддерживают дополнительные операции или имеют другие требования к пространству.

Фильтры AMQ имеют множество применений, в основном в распределенных системах и базах данных. Там они часто используются, чтобы избежать сетевых запросов или операций ввода-вывода, возникающих в результате запроса элементов, которые не существуют.

Приблизительная проблема запроса членства

Приблизительная задача запроса принадлежности состоит в том, чтобы хранить информацию о наборе элементов S экономичным способом. Цель состоит в том, чтобы ответить на вопросы о том, входит ли элемент x в набор S или нет, при этом ограничивая ложные срабатывания максимальной вероятностью. $\epsilon$ . Все фильтры AMQ поддерживают эту операцию поиска. Динамические фильтры AMQ допускают вставку в любое время, тогда как статические фильтры AMQ необходимо перестраивать после вставки дополнительных элементов. Некоторые фильтры AMQ поддерживают дополнительные операции, такие как удаление элементов или объединение двух фильтров.

Искать

Поиск по фильтру AMQ определит, находится ли элемент определенно в наборе или, возможно, в наборе.

Другими словами, если фильтр представляет набор S и нас интересует значение s , то функция поиска, примененная к s, ведет себя следующим образом:

если $s\in S$ : всегда возвращает истину.
если $s\notin S$ : возвращает false с вероятностью $1-\epsilon$ .

Ложное срабатывание — это поиск элемента, который не является частью набора, но поиск возвращает true. Вероятность того, что это произойдет, равна уровню ложноположительных результатов. $\epsilon$ . Ложноотрицательные значения (поиск возвращает false, хотя элемент является частью набора) не допускаются для фильтров AMQ.

Вставка

После вставки элемента поиск этого элемента должен вернуть true. Динамические фильтры AMQ поддерживают вставку элементов по одному без перестройки структуры данных. Другие фильтры AMQ необходимо перестраивать после каждой вставки. Это так называемые статические фильтры AMQ.

Ложноположительный уровень в сравнении с пространством

Существует компромисс между размером хранилища и уровнем ложных срабатываний. $\epsilon$ . Увеличение места для хранения снижает уровень ложных срабатываний. Теоретическая нижняя граница равна $log_{2}(1/\epsilon )$ бит для каждого элемента. ^[1] Динамические фильтры AMQ не могут достичь этой нижней границы. Им нужно как минимум $n\log _{2}(1/\epsilon )(1+o(1))$ биты для $n$ вставки. ^[2] Различные фильтры AMQ имеют разные диапазоны частоты ложных срабатываний и требования к пространству. Выбор лучшего фильтра AMQ зависит от приложения.

Структуры данных

Существуют разные способы решения приблизительной проблемы запроса на членство. Наиболее известной структурой данных являются фильтры Блума , но существуют и другие структуры данных, которые работают лучше при некоторых показателях ложных срабатываний и требованиях к пространству, поддерживают дополнительные операции или имеют другое время вставки и поиска. Ниже мы опишем некоторые хорошо известные фильтры AMQ.

Фильтр Блума

Фильтр Блума представляет собой битовый массив $m$ биты с $k$ хэш-функции. Каждая хеш-функция сопоставляет элемент с одним из $m$ позиции в массиве. Вначале все биты массива устанавливаются в ноль. Чтобы вставить элемент, вычисляются все хеш-функции и все соответствующие биты в массиве устанавливаются в единицу. Чтобы найти элемент, все $k$ вычисляются хеш-функции. Если все соответствующие биты установлены, true возвращается. Чтобы уменьшить количество ложных срабатываний, количество хеш-функций и $m$ может быть увеличено.

Частный фильтр

Идея фактор-фильтров заключается в хешировании элемента и разделении его отпечатка на $r$ наименее значимые биты, называемые остатком $d_{R}$ и наиболее значимые биты, называемые частными $d_{Q}$ . Частное определяет, где в хеш-таблице хранится остаток. Дополнительные три бита для каждого слота в хеш-таблице используются для разрешения мягких коллизий (то же самое частное, но разные остатки).

Пространство, используемое факторными фильтрами, сравнимо с фильтрами Блума, но частные фильтры могут быть объединены, не влияя на их частоту ложных срабатываний.

Фильтр с кукушкой

Фильтры Cuckoo основаны на хешировании cuckoo , но в хеш-таблице сохраняются только отпечатки элементов. Каждый элемент имеет два возможных местоположения. Второе местоположение рассчитывается на основе первого местоположения и отпечатка элемента. Это необходимо для возможности перемещения уже вставленных элементов, если оба возможных слота для элемента заполнены.

После достижения порога нагрузки скорость включения фильтра кукушки снижается. Возможно, вставка не удалась, и таблицу придется перехешировать. В то время как фильтры Блума всегда имеют постоянное время внедрения, но по мере увеличения коэффициента загрузки увеличивается и частота ложных срабатываний.

Фильтр-кукушка поддерживает удаление элементов в том случае, если мы точно знаем, что элемент действительно был ранее вставлен. Это преимущество перед фильтрами Блума и фактор-фильтрами, которые не поддерживают эту операцию.

Исключающий фильтр

Xor-фильтры ^[3] — это статические фильтры AMQ, основанные на фильтре Блумьера и использующие идею идеальных хэш- таблиц. Подобно фильтрам с кукушкой, они сохраняют отпечатки элементов в хеш-таблице. Идея состоит в том, что запрос элемента $x$ истинно, если xor трех заданных хэш-функций $h_{0},h_{1},h_{2}$ это отпечаток пальца $x$ . При построении хеш-таблицы каждому элементу назначается один из трех слотов таким образом, чтобы этому слоту не были назначены никакие другие элементы. После того, как все элементы назначены, мы устанавливаем для каждого элемента значение его слота, равное xor двух других (не назначенных) слотов элемента и отпечатку пальца элемента. Этот алгоритм построения может дать сбой, так что никакие динамические вставки будут невозможны без перестроения хеш-таблицы. Эту хеш-таблицу можно построить, используя только $1.23\log _{2}(1/\epsilon )$ бит на элемент.

Недостатком этого фильтра является то, что при добавлении дополнительных элементов структуру данных приходится перестраивать. Они используются в приложениях, где впоследствии не нужно добавлять элементы и где пространство имеет важное значение.

Приложение

Типичными применениями фильтров AMQ являются распределенные системы и системы баз данных. Фильтр AMQ действует как прокси для набора ключей базы данных или удаленной памяти. Прежде чем будет выполнен предположительно медленный запрос к базе данных или удаленной памяти, используется фильтр AMQ, чтобы дать приблизительный ответ о том, находится ли ключ в базе данных или в удаленной памяти. Медленный запрос выполняется только тогда, когда фильтр AMQ возвращает true. Только в случае ложного срабатывания (надеемся, редкого) выполняется ненужный ввод-вывод или удаленный доступ. Приложения многочисленны и включают маршрутизацию пакетов и ресурсов, сети P2P и распределенное кэширование. ^[4]

Фильтры AMQ часто используются в качестве структуры данных в памяти, чтобы избежать дорогостоящего доступа к диску. Одним из приложений являются деревья слияния с лог-структурой или деревья LSM. У них есть быстрый компонент в памяти и один или несколько компонентов на диске, которые сами являются деревьями. Элементы вставляются в компонент в памяти до тех пор, пока он не достигнет максимального размера, после чего компонент в памяти объединяется с компонентами диска. Чтобы ускорить поиск, многие деревья LSM реализуют фильтры AMQ, такие как фильтры Блума или фильтры частных. Эти фильтры для каждого компонента приблизительно определяют, какие элементы в нем хранятся. Деревья LSM используются в таких базах данных, как Apache AsterixDB , Bigtable , HBase , LevelDB , SQLite4 .

Сети предлагают множество применений фильтров AMQ. Они используются для аппроксимации набора данных, расположенных на разных серверах. Во многих случаях эти фильтры AMQ можно рассматривать как неизменяемые. Даже если набор на удаленном сервере меняется, фильтр AMQ часто не обновляется сразу, но некоторые ложные срабатывания допускаются. Одним из примеров этого приложения является совместное использование веб-кэша. Если у прокси-сервера произошел промах в кэше, он хочет определить, есть ли у другого прокси-сервера запрошенные данные. Следовательно, прокси-сервер должен знать или, по крайней мере, приблизительно знать, владеет ли другой прокси-сервер запрошенной веб-страницей. Это можно архивировать, периодически рассылая статический AMQ-фильтр URL-адресов веб-страниц, кэшированных прокси-сервером, вместо рассылки списков URL-адресов. При этом параметре могут возникать ложноотрицательные результаты, если кэш менялся между периодическими обновлениями.

Та же концепция может быть применена к P2P-сетям. Фильтры AMQ можно использовать для аппроксимации того, что хранится в каждом узле сети. Фильтр может быть заполнен идентификаторами или ключевыми словами реальных документов узлов. Ложные срабатывания приводят только к ненужным запросам. Фильтры AMQ имеют и другие применения в P2P-сетях, например, для поиска различий или пересечений между наборами, хранящимися на разных узлах.

См. также

Бинарная классификация

Ссылки

^ Картер; Ларри (1978). «Точные и приблизительные тестеры принадлежности» . Материалы десятого ежегодного симпозиума ACM по теории вычислений - STOC '78 . стр. 59–65. дои : 10.1145/800133.804332 . S2CID 6465743 .
^ Ловетт; Шачар (2010). «Нижняя граница для структур данных динамического приблизительного членства» . 2010 51-й ежегодный симпозиум IEEE по основам информатики . стр. 797–804. дои : 10.1109/FOCS.2010.81 . ISBN 978-1-4244-8525-3 . S2CID 7904735 .
^ Граф; Лемир (2020). «Хор-фильтры». Журнал экспериментальной алгоритмики ACM . 25 : 1–16. arXiv : 1912.08258 . дои : 10.1145/3376122 . S2CID 209405019 .
^ Бродер, Андрей; Митценмахер, Майкл (2002). «Сетевые приложения фильтров Блума: обзор». Интернет-математика : 636–646. CiteSeerX 10.1.1.20.98 .

[1] Картер; Ларри (1978). «Точные и приблизительные тестеры принадлежности» . Материалы десятого ежегодного симпозиума ACM по теории вычислений - STOC '78 . стр. 59–65. дои : 10.1145/800133.804332 . S2CID 6465743 .

[2] Ловетт; Шачар (2010). «Нижняя граница для структур данных динамического приблизительного членства» . 2010 51-й ежегодный симпозиум IEEE по основам информатики . стр. 797–804. дои : 10.1109/FOCS.2010.81 . ISBN 978-1-4244-8525-3 . S2CID 7904735 .

[3] Граф; Лемир (2020). «Хор-фильтры». Журнал экспериментальной алгоритмики ACM . 25 : 1–16. arXiv : 1912.08258 . дои : 10.1145/3376122 . S2CID 209405019 .

[4] Бродер, Андрей; Митценмахер, Майкл (2002). «Сетевые приложения фильтров Блума: обзор». Интернет-математика : 636–646. CiteSeerX 10.1.1.20.98 .

[1]

[2]

[3]

[4]