BitFunnel

BitFunnel представляет собой алгоритм индексации поисковой системы и набор компонентов, используемых в поисковой системе Bing, которая была сделана с открытым исходным кодом в 2016 году. BitFunnel использует битовые подписи вместо инвертированный индекс в попытке снизить стоимость операций.

• 1 История
• 2 Компоненты
• 3 Алгоритм
  • 3.1 Исходная проблема и обзор решения
  • 3.2 Теоретическая реализация Bit- Строковые сигнатуры
  • 3.3 Псевдокод для бит-строковых сигнатур
• 4 ссылки
• 5 Внешние ссылки

Прогресс в реализации BitFunnel был обнародован в начале 2016 года, и ожидалось, что в том же году будет полезная реализация. В сентябре 2016 года исходный код был доступен через GitHub. Документ, в котором обсуждается алгоритм и реализация BitFunnel, был выпущен Специальной группой по поиску информации Ассоциации вычислительной техники в 2017 году и получил награду за лучшую работу.

BitFunnel состоит из трех основных компонентов:

• BitFunnel - сама система текстового поиска / поиска
• WorkBench - инструмент для подготовки текста для использования в BitFunnel
• NativeJIT - программный компонент, который принимает выражения, использующие C структуры данных, и преобразует их в высокооптимизированный ассемблерный код

Обзор исходной проблемы и решения

В документе BitFunnel описывается «проблема соответствия», которая возникает, когда алгоритм должен идентифицировать документы с помощью ключевых слов. Задача задачи - определить набор соответствий, заданный корпусом для поиска, и запросом ключевых слов для сопоставления. Эта проблема обычно решается с помощью инвертированного индекса es, где каждый доступный для поиска элемент поддерживается с помощью map ключевых слов.

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

Теоретическая реализация сигнатур битовых строк

Подпись документа (D) может быть описана как логическое или его термина подписи:

$SD\; \to \; =\; \bigcup \; t\; \in \; DS\; t\; \to \; \{\backslash \; displaystyle\; \{\backslash \; overrightarrow\; \{S\_\; \{D\}\}\}\; =\; \backslash \; bigcup\; \backslash \; limits\; \_\; \{t\; \backslash \; in\; D\}\; \{\backslash \; overrightarrow\; \{S\_\; \{t\}\}\}\}$

Аналогичным образом запрос для документа (Q) можно определить как объединение:

$SQ\; \to \; =\; \bigcup \; t\; \in \; QS\; t\; \to \; \{\backslash \; displaystyle\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\; =\; \backslash \; bigcup\; \backslash \; limits\; \_\; \{t\; \backslash \; in\; Q\}\; \{\backslash \; overrightarrow\; \{S\_\; \{t\}\}\}\}$

Кроме того, документ D является членом множества M ', если выполняется следующее условие:

$SQ\; \to \; \cap \; SD\; \to \; =\; SQ\; \to \; \{\backslash \; displaystyle\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\; \backslash \; cap\; \{\backslash \; overrightarrow\; \{S\_\; \{D\}\}\}\; =\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\}$

Затем эти знания объединяются для создания формула, где M 'идентифицируется документами, соответствующими сигнатуре запроса:

$M\; \prime \; =\; \{D\; \in \; C\; |\; SQ\; \to \; \cap \; SD\; \to \; =\; SQ\; \to \}\; \{\backslash \; displaystyle\; M\; \text{'}=\; \backslash \; \{D\; \backslash \; in\; C\; |\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\; \backslash \; cap\; \{\backslash \; overrightarrow\; \{S\_\; \{D\}\}\}\; =\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\; \backslash \}\}$

Эти шаги и их доказательства обсуждаются в статье 2017 г.

Псевдокод для подписей битовых строк

Этот алгоритм описан в статье 2017 г.

$M\; \prime \; =\; \varnothing \; для\; всех\; D\; \in \; C,\; если\; SD\; \to \; \cap \; SQ\; \to \; =\; SQ\; \to \; тогда\; M\; \prime \; =\; M\; \prime \; \cup \; \{D\}\; endif\; endfor\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{array\}\; \{l\}\; M\; \text{'}=\; \backslash \; emptyset\; \backslash \backslash \; \{\backslash \; texttt\; \{for\}\}\; \backslash \; \{\backslash \; texttt\; \{all\}\}\; \backslash \; D\; \backslash \; in\; C\; \backslash \; \{\backslash \; texttt\; \{do\}\}\; \backslash \backslash \backslash \; qquad\; \{\backslash \; texttt\; \{if\}\}\; \backslash \; \{\backslash \; overrightarrow\; \{S\_\; \{D\; \}\}\}\; \backslash \; cap\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\; =\; \{\backslash \; overrightarrow\; \{S\_\; \{Q\}\}\}\; \backslash \; \{\backslash \; texttt\; \{then\}\}\; \backslash \backslash \backslash \; qquad\; \backslash \; qquad\; M\; \text{'}=\; M\text{'}\; \backslash \; cup\; \backslash \; \{D\; \backslash \}\; \backslash \backslash \backslash \; qquad\; \{\backslash \; texttt\; \{endif\}\}\; \backslash \backslash \; \{\backslash \; texttt\; \{endfor\}\}\; \backslash \; end\; \{array\}\}\}$

• BitFunnel · GitHub
• BitFunnel · BitFunnel