BitFunnel - BitFunnel

BitFunnel
Разработчики)Microsoft
изначальный выпуск2016; 4 года назад (2016)
Репозиторийgithub.com/ BitFunnel
Написано вC ++
ПлатформаWindows, macOS, Ubuntu
ТипИндексирование поисковой системой алгоритм
ЛицензияЛицензия MIT
Интернет сайтbitfunnel.org

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

История

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

Составные части

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

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

Алгоритм

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

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

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

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

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

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

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

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

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

Псевдокод для сигнатур битовой строки

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

Рекомендации

  1. ^ а б Егулалп, Сердар (6 сентября 2016 г.). «Компоненты Microsoft Bing с открытым исходным кодом для быстрой компиляции кода». InfoWorld.
  2. ^ Верма, Арпит (07.09.2016). «Основные компоненты поисковой системы Bing с открытыми исходными кодами Microsoft, вот почему это важно». Fossbytes. Получено 2020-06-12.
  3. ^ а б c d е ж Гудвин, Боб; Хопкрофт, Майкл; Луу, Дэн; Клеммер, Алекс; Курмей, Михаэла; Эльникети, Самех; Он, Юйсюн (2017-08-07). «BitFunnel». Материалы 40-й Международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска. Нью-Йорк, Нью-Йорк, США: ACM: 605–614. Дои:10.1145/3077136.3080789. ISBN  978-1-4503-5022-8.
  4. ^ «Когда можно будет использовать BitFunnel? · BitFunnel». bitfunnel.org. Получено 2020-06-12.
  5. ^ BitFunnel / BitFunnel, BitFunnel, 12 мая 2020 г., получено 2020-06-12
  6. ^ "SIGIR Best Paper Awards". ACM. Получено 8 июля 2020.

внешняя ссылка