ビットファンネル

ビットファンネル
ビットファンネル
開発者	マイクロソフト
初回リリース	2016年; 9年前
リポジトリ	github.com/BitFunnel
書かれた	C++
プラットフォーム	Windows、macOS、Ubuntu
タイプ	検索エンジンのインデックスアルゴリズム
ライセンス	MITライセンス
Webサイト	ビットファンネル

BitFunnelは、検索エンジンのインデックスアルゴリズムと、 Bing検索エンジンで使用されるコンポーネントのセットであり、^[1] 2016年にオープンソース化されました。^[2] BitFunnelは、運用コストを削減するために、転置インデックスの代わりにビットスライス署名を使用します。 ^[3]

歴史

BitFunnelの実装の進捗状況は2016年初頭に公開され、同年後半には実用的な実装が実現すると期待されていました。^{[4] 2016年9月には、}GitHubを通じてソースコードが公開されました。^{[5] BitFunnelのアルゴリズムと実装について議論した論文が、2017年に米国}計算機学会の情報検索に関する特別利益団体から発表され、最優秀論文賞を受賞しました。^[3]^[6]

コンポーネント

BitFunnelは3つの主要コンポーネントで構成されています。^[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}}$

参考文献

^ ab Yegulalp, Serdar (2016年9月6日). 「Microsoft、高速コードコンパイル向けBingコンポーネントをオープンソース化」InfoWorld .
^ Verma, Arpit (2016年9月7日). 「MicrosoftがBing検索エンジンの主要コンポーネントをオープンソース化、その重要性とは」. Fossbytes . 2020年6月12日閲覧。
^ abcdef ボブ・グッドウィン、マイケル・ホップクロフト、ダン・ルー、アレックス・クレマー、ミハエラ・カーメイ、サメ・エルニケティ、ユキシオン・ヘ (2017年8月7日). 「BitFunnel」.第40回国際ACM SIGIR情報検索研究開発会議議事録. ニューヨーク、ニューヨーク州、米国: ACM. pp. 605– 614. doi : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8。
^ 「BitFunnelはいつ使えるようになるのか？ · BitFunnel」. bitfunnel.org . 2020年6月12日閲覧。
^ BitFunnel/BitFunnel、BitFunnel、2020年5月12日、 2020年6月12日閲覧
^ 「SIGIR Best Paper Awards」. ACM . 2020年7月8日閲覧。

外部リンク

BitFunnel · GitHub
ビットファネル · ビットファネル

[InfoWorld-1] Yegulalp, Serdar (2016年9月6日). 「Microsoft、高速コードコンパイル向けBingコンポーネントをオープンソース化」InfoWorld .

[2] Verma, Arpit (2016年9月7日). 「MicrosoftがBing検索エンジンの主要コンポーネントをオープンソース化、その重要性とは」. Fossbytes . 2020年6月12日閲覧。

[:0-3] ボブ・グッドウィン、マイケル・ホップクロフト、ダン・ルー、アレックス・クレマー、ミハエラ・カーメイ、サメ・エルニケティ、ユキシオン・ヘ (2017年8月7日). 「BitFunnel」.第40回国際ACM SIGIR情報検索研究開発会議議事録. ニューヨーク、ニューヨーク州、米国: ACM. pp. 605– 614. doi : 10.1145/3077136.3080789 . ISBN 978-1-4503-5022-8。

[4] 「BitFunnelはいつ使えるようになるのか？ · BitFunnel」. bitfunnel.org . 2020年6月12日閲覧。

[5] BitFunnel/BitFunnel、BitFunnel、2020年5月12日、 2020年6月12日閲覧

[6] 「SIGIR Best Paper Awards」. ACM . 2020年7月8日閲覧。