BitFunnel

BitFunnel
Разработчик(и)	Майкрософт
Первоначальный выпуск	2016 ; 8 лет назад
Репозиторий	github .с /BitFunnel
Написано в	С++
Платформа	Windows , macOS , Убунту
Тип	индексации поисковыми системами Алгоритм
Лицензия	МОЯ лицензия
Веб-сайт	битовая воронка .org

BitFunnel — алгоритм индексации поисковой системы и набор компонентов, используемых в поисковой системе Bing . ^[1] которые были сделаны открытым исходным кодом в 2016 году. ^[2] BitFunnel использует побитовые подписи вместо инвертированного индекса в попытке снизить затраты на операции. ^[3]

История

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

Компоненты

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

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

Алгоритм

Первоначальный обзор проблемы и решения

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

Напротив, BitFunnel представляет каждый элемент, доступный для поиска, через подпись. Сигнатура — это последовательность битов, которая описывает фильтр Блума доступных для поиска терминов в данном доступном для поиска элементе. Фильтр Блума создается путем хеширования нескольких битовых позиций. ^[3]

Теоретическая реализация битовых подписей

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

${\overrightarrow {S_{D}}}=\bigcup _{t\in D}{\overrightarrow {S_{t}}}$

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

${\overrightarrow {S_{Q}}}=\bigcup _{t\in Q}{\overrightarrow {S_{t}}}$

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

${\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}$

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

$M'=\left\{D\in C\mid {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}\right\}$

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

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

Этот алгоритм описан в статье 2017 года. ^[3] ${\begin{array}{l}M'=\emptyset \\{\texttt {foreach}}\ D\in C\ {\texttt {do}}\\\qquad {\texttt {if}}\ {\overrightarrow {S_{D}}}\cap {\overrightarrow {S_{Q}}}={\overrightarrow {S_{Q}}}\ {\texttt {then}}\\\qquad \qquad M'=M'\cup \{D\}\\\qquad {\texttt {endif}}\\{\texttt {endfor}}\end{array}}$

Ссылки

^ Перейти обратно: ^а ^б Егулалп, Сердар (6 сентября 2016 г.). «Компоненты Bing с открытым исходным кодом Microsoft для быстрой компиляции кода» . Инфомир .
^ Верма, Арпит (07 сентября 2016 г.). «Майкрософт открывает исходные коды основных компонентов поисковой системы Bing, вот почему это важно» . Фоссбайты . Проверено 12 июня 2020 г.
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Гудвин, Боб; Хопкрофт, Майкл; Луу, Дэн; Клеммер, Алекс; Курмей, Михаэла; Эльникети, Самех; Хэ, Юйсюн (07.08.2017). «БитФуннел». Материалы 40-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 605–614. дои : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8 .
^ «Когда BitFunnel можно будет использовать? · BitFunnel» . bitfunnel.org . Проверено 12 июня 2020 г.
^ BitFunnel/BitFunnel , BitFunnel, 12 мая 2020 г. , получено 12 июня 2020 г.
^ «Награда SIGIR за лучшую бумагу» . АКМ . Проверено 8 июля 2020 г.

Внешние ссылки

[InfoWorld-1] Перейти обратно: ^а ^б Егулалп, Сердар (6 сентября 2016 г.). «Компоненты Bing с открытым исходным кодом Microsoft для быстрой компиляции кода» . Инфомир .

[2] Верма, Арпит (07 сентября 2016 г.). «Майкрософт открывает исходные коды основных компонентов поисковой системы Bing, вот почему это важно» . Фоссбайты . Проверено 12 июня 2020 г.

[:0-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж Гудвин, Боб; Хопкрофт, Майкл; Луу, Дэн; Клеммер, Алекс; Курмей, Михаэла; Эльникети, Самех; Хэ, Юйсюн (07.08.2017). «БитФуннел». Материалы 40-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 605–614. дои : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8 .

[4] «Когда BitFunnel можно будет использовать? · BitFunnel» . bitfunnel.org . Проверено 12 июня 2020 г.

[5] BitFunnel/BitFunnel , BitFunnel, 12 мая 2020 г. , получено 12 июня 2020 г.

[6] «Награда SIGIR за лучшую бумагу» . АКМ . Проверено 8 июля 2020 г.

[1]

[2]

[3]

[4]

[5]

[6]