論文 "BitFunnel: Revisiting Signatures for Search" を読んだメモ
- まとめると
- 気になりポイント
- 1. Introduction
- 2. Background and prior work
- 2.1 Inverted Indexes
- 2.2 Bit-String Signatures
- 2.3 Bit-Sliced Signatures
- 2.4 Bit-Sliced Blocked Signatures
- 3. THE BITFUNNEL SYSTEM
- 3.1 Architectural Overview
- 3.2 The Cost of False Positives
- 4. BITFUNNEL INNOVATIONS
- 4.1 Higher Rank Rows
- 4.2 Frequency Conscious Signatures
- 4.3 Sharding by Document Length
- 5. PERFORMANCE MODEL AND OPTIMIZATION
- 5.1 Prerequisites
- 5.5 Choosing Term Configurations
- 6. EXPERIMENATAL EVALUATION
- 6.1 Match Time vs. Quadwords
- 6.2 Impact of Frequency Conscious Signatures and Higher Rank Rows
- 6.3 Comparison with Contemporary Indexes
まとめると
- Bing で採用された BitFunnel アルゴリズムについての論文
- シグネチャファイルという(転置インデックスではない)方式での検索
- 索引を使った検索エンジンのアルゴリズムには何種類かある
- シグネチャーファイルはいくつかの制約があってメジャーではなかったが、それらの制約を克服する方法を MS が開発した
- 旧来の検索エンジンを超える高い QPS を実現 (Table 3)
- 比較対象は PEG, MG4J, Lucene
- 5 つの実験設定(文書長により分類)すべてで最も高い QPS (Query Per Second)
- 容量効率は悪い(インデックスサイズが大きい)
- ただし文書長が大きくなるほど QPS も容量効率も向上していく
- 今回の実験では false positive は 1.62% ~ 4.32%
- SIGIR 2017 の Best Paper
気になりポイント
- false positive をどうやって抑えるのか
- シグネチャファイルでは単語の頻度を考慮に入れられないけど、スコアリングどうするのか
- AND クエリ以外、たとえば OR クエリの処理はどうするのか
1. Introduction
- これまでの商用の検索エンジンは伝統的に転置インデックスが採用されている
- これまでは転置インデックスがほとんどの条件でシグネチャファイルを上回ると思われていた
- シグネチャーファイルによる検索には、4つの技術的課題がある
- これらの課題を克服するために以下のテクニックを開発し、Bing で採用した
- Higher rank rows: クエリを速くするために導入(計算量が文書数によらない?)
- Frequency-conscious signatures: メモリ使用量を減らすために採用(シグネチャの大きさを TF によって調整する?)
- Sharding by document length: 文書長のばらつきを減らして圧縮率や速度を上げるために、文書長ごとに文書集合 (Corpus) を分割したインデックス(シャード)をつくる
- システムのパフォーマンスのコストモデル(= たぶん損失関数のこと)をつくった
- これにより、(Bloom filter のハッシュ関数などの)パラメータの最適化を行った
- 以上の技術は、 Bing の検索エンジンで実際に 4 年間使われていて、数千台のサーバの上で動作している
- 十分にスケールしている
- Bing はこれまで転置インデックスベースのエンジンを使っていたが、BitFunnel にリプレースして query capacity が 10 倍に向上した(!)
2. Background and prior work
集合の定義
C: コーパス。文書の集合 D: 文書。タームの集合 Q: クエリ。タームの集合 M: クエリ Q にマッチする文書の集合 M': false positive を許す、クエリ Q にマッチする文書の集合 F: false positive の文書の集合
2.1 Inverted Indexes
自明なので省略
2.2 Bit-String Signatures
ハッシュ関数 H(n, t)
- n: Bloom filter のビットの位置
シグネチャの定義
s_t: ターム t のシグネチャ (n bits) s_D: 文書 D のシグネチャ。文書 D に表れるすべてのターム t のシグネチャ s_t の論理和 s_Q: クエリ Q のシグネチャ。クエリ Q に表れるすべてのターム t のシグネチャ s_t の論理和
- M' に含まれる文書 D では以下が成り立つ
s_Q & s_D == s_Q
- https://www.youtube.com/watch?v=1-Xoy5w5ydM#t=3m35s
- つまり、M' は上の式が成り立つすべての文書 D の集合
- 文書集合(コーパス) C のすべての文書をなめれば M' が計算できる
2.3 Bit-Sliced Signatures
- bit-string signatures の方法は効率が悪い
- すべてのビットを読む必要があった
- クエリ Q のシグネチャ s_Q で 1 が立っているビットだけ調べればよい
- 全文書のシグネチャ(ベクトル)を転置する
- Figure 1: A..P が文書、0..15 はシグネチャのビット位置。縦のビットベクトルがクエリもしくは文書のシグネチャを表す
- https://www.youtube.com/watch?v=1-Xoy5w5ydM#t=4m59s
- ビットが立っているデータだけ読めばよくなる
- Figure 1 でグレーがかっている行(スライス)だけ読めばよい
- https://www.youtube.com/watch?v=1-Xoy5w5ydM#t=5m30s
- マッチする文書集合 M' を求めるには、スライスから縦がすべて 1 になっている文書を探す
- Figure 2: クエリ Q で立っているビット 2, 5, 9 のスライス。この中では文書 B, F がマッチ
- 2, 5, 9 の横のベクトル(スライス)の論理積をとれば、ビット演算だけで M' が計算できる
2.4 Bit-Sliced Blocked Signatures
- bit-sliced signatures は bit-string signatures よりもかなりよくなったが、依然効率は悪い
- レアな(TFが小さい)タームにおいては、スライスのほとんどのビットが 0 (文書がそのタームを含んでいない)にもかかわらず読まないといけない
- blocked signatures: 複数の文書で 1 つの列を「シェアする」ことで、もっと短い行ベクトルにする
- 複数の文書で 1 つの列を共有
- bit-sliced signatures では 1 文書につき 1 列が一対一対応だった
- blocking factor: 1 つの列を共有する文書数
- この方法 (blocked signatures) は、 false positive の確率を上げてしまう
- たとえば、同じ列に 2 つの文書("dog" のみを含む文書と "cat" のみを含む文書)が対応づけられていたとする
- クエリ Q が {"dog", "cat"} だとすると、この 2 つの文書が両方マッチしてしまう
- 4.1 の Higher Rank Rows という手法によりこの問題を解決する
3. THE BITFUNNEL SYSTEM
- 4年前から BitFunnel が Bing 検索のバックグラウンドとして稼働している
- 数千台のマシン、いくつかのデータセンターに分散して配置
- このシステムで Bing にくるすべてのクエリを処理している
3.1 Architectural Overview
- Bing のインデックスは複数の BitFunnel ノードにシャーディングされている
- Figure 3: BitFunnel クラスタの図
- (分散検索の仕組みは Elasticsearch/Solr とかとだいたい同じ)
クエリは以下のように実行される:
- クエリをパースして実行計画をつくる
- 実行計画にしたがって、(コンパイルした)クエリを複数のノードに投げる
- 各ノードでクエリを実行し、実行計画をつくったノードに結果を返す
- 結果をアグリゲーション
- スコアリングやスニペット (caption) 作成のため、別のシステムにマッチした文書集合 (M') を渡す
3.2 The Cost of False Positives
- exact match が欲しい場合には、false positive を除外する必要がある
- Web 検索の場合には、このコストは無視できる程度に小さい
- なぜなら、Web 検索のゴールはユーザのクエリにマッチする文書を見つけることではなく、ユーザの意図 (intent) に最も合う文書を見つけることだから
- Bing では、ランキングのためのシステム (Oracle) は別にある
- ランキングシステム
- 文書とクエリからスコアを計算する
- 文書がどれだけユーザの意図にマッチしているかを、単なるキーワードだけでなく、様々なシグナルから計算している
- 機械学習が使われていて、内部の動作は外からはわからない
- BitFunnel は(ランキングシステムがスコアが低いと判定するであろう文書を通さない)「フィルター」としての役割
- end-to-end で考えた場合、ランキングシステムが(BitFunnel による)false positive をスコアリングする時間を考慮する必要がある
- ランキングシステムが十分に速い場合、BitFunnel が false positive を発生させることによるコストは小さいと考えることができる
4. BITFUNNEL INNOVATIONS
- bit-string signatures と bit-sliced signatures の速度とサイズの問題を改善する 3 つのテクニックを紹介
- Higher Rank Rows
- Frequency Conscious Signatures
- Sharding by Document Length
4.1 Higher Rank Rows
- bit-sliced blocked signatures の応用
- 異なる blocking factor (1 つの列を共有する文書数) のビット列(タームごとにそれぞれ長さが異なるビット列)に対してもクエリを実行できる
- Higher rank row では、blocking factor を 2 の累乗とする
- bit-sliced signatures では、文書数が多い時、たくさんのビットを読まないといけなかった
- Higher rank row では、文書の数だけあったビットを「折りたたむ」
- https://www.youtube.com/watch?v=1-Xoy5w5ydM#t=6m37s
- 半分の長さのビット列に分割し、それらの論理和 (OR) をとる
- もとのビット列を Rank 0 とよび、折りたたんだあとのビット列を Rank 1 とよぶ
- 同様にさらに半分にして論理和をとったものを Rank 2, Rank 3, ... とよぶ
- Rank が高くなるにつれて false positive が起こりやすくなる
- 1つのビットに対応する文書の数が多くなっていくため
- たとえば 3 つのタームからなるクエリで検索することを考える
- Rank 0, Rank 1, Rank 2 のそれぞれ異なるランクのビット列を仮定する
- https://www.youtube.com/watch?v=1-Xoy5w5ydM#t=7m41s
- それぞれ長さは異なるが、ビット演算は可能
- https://www.youtube.com/watch?v=1-Xoy5w5ydM#t=8m14s
- もとのビット列を復元すればよい
- (もともと 0 だったか 1 だったかは完全にはわからないので、情報量は落ちている)
- ファイル(メモリ)から読み込むビットは減っているのでクエリは速くなる
- その代償としてfalse positive の確率が上がる
4.2 Frequency Conscious Signatures
- シグナルの定義について
- 定数 k: Bloom filter で使用するハッシュ関数の数
one-size-fits-all k
問題- すべてのタームに対して同じ k を使うのは無駄が多い
- タームのレア度に応じて最適な k は異なるはず
- シグナルノイズ比を導入することで false positive の量を考えることができる
- Bloom filter を、タームのハッシュをとったときに、高々 k 個のビットが立つように設定する
- こうすることでシグナルノイズ比が計算できる
- シグナル s: 「ターム t が実際に文書 D に含まれている確率」と定義
- これは単にコーパスに表れるタームの "frequency" に一致する
- (ここでは frequency という言葉は、TF のことではなく、DF (を文書数で割ったもの)のことを言ってそう)
- ("picture" の frequency が 0.1、みたいな記述がある)
- ノイズ α: 「Bloom filter が誤ってターム t を文書 D に入っていると答えてしまう確率」と定義
- 平均ビット密度 d: Bloom filter で立っているビットの期待値の逆数
- Bloom filter の出力は平均ビット密度 d になるように設定されているとする
- ノイズ α は (1 - f) * dk
- シグナルノイズ比 ϕ は s/α なので、 ϕ = s / (1 - s) * dk と表せる
- これを k について解くと k = log_d( s / (1 - s) * ϕ)
- 目指すシグナルノイズ比 ϕ に対して、タームの頻度(= s)ごとにどれくらいの k が必要かが計算できる
- シグナルノイズ比 ϕ を 10 以上にするためには
- frequency 0.1 のターム "picture" に対しては k = 2 でよい
- frequency 0.0001 のターム "rotisserie" に対しては、シグナルノイズ比を 10 にするために k = 5 が必要
- 古典的な Bloom filter では、もっともレアな(s が小さい)タームに対して許容できる false positive から設定を行う必要があった
- BitFunnel では各タームごとにどれくらいの行数(ビット列の数)が必要かを決定するのにこの方法を使っている
4.3 Sharding by Document Length
- bit-sliced signatures はシグネチャのビット数が決め打ち
- 文書長が違っても固定のビット数、同じハッシュ関数を使わないといけない
- 実際に、文書長は非常に多様
- Wikipedia では、10個に満たないタームの文書もあるし、数千個のタームからなる文書もある
- このような場合には、bit-sliced signatures は容量効率が悪い
- 近い長さの文書をまとめるシャーディングが 90 年代後半に提案された
- が、1台のマシンで動かすときには効率が悪い
- シャード数に比例してディスクのシーク(ランダムアクセス)が発生してしまう
- 当時はメモリが高価で容量が小さく、SSD が普及していなかった
- 現代のマシンでは影響は小さい
- BitFunnel では1つのインスタンスごとに1つの(近い文書長でわけた)シャードを管理し、クラスタ構成を組んでいる
- ランダムアクセスの問題が起こりにくい
5. PERFORMANCE MODEL AND OPTIMIZATION
- シグネチャを使う方法はパラメータが多くて最適化が難しかった
- この章ではほしいシグナルノイズ比を達成する最適化のアルゴリズムを紹介
- 指定されたシグナルノイズ比を下限とする制約付きの最適化
- 最適化対象のコスト関数は DQ (コーパスサイズ(の小ささ) D と QPS Q の積) を表す(そのものではない)
- あとで定義する
5.1 Prerequisites
- row のランクのビット密度・ノイズについて議論
- rank-0 equivalent rows のノイズには2種類ある
- 5.2, 5.3, 5.4 で議論する
5.1.1 Signal in a Higher Rank Row
s_0
: rank-0 の行のシグナルs_r
: rank-r の行のシグナルs_r
はs_0
の関数として書き下せてs_r = 1 - (1 - s_0)^(2^r)
- rank-r のビットがシグナルであるためには、対応する rank-0 のビット(
2^r
個ある)の少なくとも1つがシグナルである必要がある
5.1.3 Correlated and Uncorrelated Noise
U
: Uncorrelated noiseC
: Correlated noisen_r
: rank-r の行R
のノイズn_0
: そのR
に対応する rank-0 の行のノイズn_0
はr
s_0
n_r
の関数として書ける(?)- ...
n_0
は以下の式で計算できるn_0 = n_r + s_r - s_0
- 変形すると
n_0 - n_r = s_r - s_0
- 5.1.1 のより
s_r = 1 − (1 − s_0)^(2^r)
なのでn_0 - n_r = 1 − (1 − s_0)^(2^r) - s_0
5.5 Choosing Term Configurations
- ここまでの結果を使って、最適な設定を求める
- 求めるべきなのは、各ランク(Rank 0 - Rank 6 の7段階で十分)に必要な行数 k(0 - 9 の10段階で十分)の最適値
- たとえば、ターム
movies
に対しては、Rank 1
* 3 +Rank 5
* 1(ランク1の行を3つ、ランク5の行を1つ)など
- それぞれのタームの IDF に対して求めればよい
- 最適な設定を決めるために、制約付き最適化を行う
- DQ は 5.3 で求めた (5) 式と 5.4 で求めた (6) 式を使って書ける
- D は (6) に反比例
- Q は (5) に反比例
- (7) 式の右辺を最大化するパラメータを求めればよい
- ランクと k の取りうる値はそれぞれ7通りと10通り
- つまり、パラメータ空間は 107
- グリッドサーチによる全探索でも十分に速く計算できる
- タームの IDF は実数パラメータだが、実用上は各タームごとに厳密に計算する必要はない
- IDF が 0.1 から 10.0 まで、0.1 刻みで 100 個のバケットをつくり、それぞれごとに最適値(ランクと k の組)を予め計算しておく
- 最近のマルチコア CPU なら数秒で完了する
- (単語の IDF が計算できたら、バケットからそれに対応する最適設定を取り出して、シグネチャをつくればよい)
6. EXPERIMENATAL EVALUATION
- コーパス
- TREC の Gov2 コーパスを使用
- 前処理
- Apache Tika でタームの抽出
- 小文字に変換
- ステミングはしない
- テストに使った BitFunnel のシャード
- A ~ E の 5つのシャードを使う
- A: ターム数がもっとも少ないシャード (64 - 127)
- E: ターム数がもっとも多いシャード (2,048 - 4,095)
- Table 1: インデキシング後の各シャードの統計情報
- クエリログ(検索のテストに使用)
- TREC 2006 Efficiency Topics を使用
- クエリから句読点を除去
- そのあと、コーパスに出てこないタームを含むクエリは除去
- 計算機環境
- BitFunnel の設定(FC, FC+HRR 共通)
- シグナルノイズ比の下限 ϕ を 10 に設定
6.1 Match Time vs. Quadwords
- 5.3 でつくったコストモデルの予測性能を検証
- Figure 11: 散布図
6.2 Impact of Frequency Conscious Signatures and Higher Rank Rows
- 比較した手法
BSS
: Bit-Sliced SignaturesBSS-FC
: Bit-Sliced Signatures + Frequency Conscious SignaturesBTFNL
: Bit-Sliced Signatures + Frequency Conscious Signatures + Higher Ranked Rows
BSS-FC
でストレージ効率は3.2倍(46.7 -> 14.7 bits/postings)に、クエリ速度は2.6倍(9.1 -> 21.4 kQPS)に (d = 0.15)- Frequency Conscious Signatures はストレージ効率とクエリ速度、どちらも向上させる
BTFNL
でBSS-FC
のさらに2.4倍(24.0 -> 57.0 kQPS)に (d = 0.15)- Higher Ranked Rows はクエリ速度に対する効果が大きい
- 逆にストレージ効率は
BSS-FC
単体より少し上がっただけ(bits/posting が減った)
6.3 Comparison with Contemporary Indexes
- BitFunnel と他の全文検索ライブラリとの比較
- Bing で動いているプロダクション版の BitFunnel では、BM25F のランキングのためにターム頻度 (TF) を順方向のインデックスとして持っている
- (なんかよくわからないけど)このランキングのコードが使えなかったので、実験は AND 検索 (conjunctive boolean matching) でだけ行った
- (実務の全文検索では OR 検索してスコアリングしたい場面が多いので、やや不公平感がある)
- 比較対象
- 設定
- インデックスファイルはメモリマップドファイルとして開く
- タームのポジション(位置情報)は持たない
- スコアリングしない
- スコアリングしないので、ターム頻度の情報はインデックスファイルには不要
- PEF と MG4J はターム頻度 (TF) は別ファイルになるので、今回の実験設定ではペナルティがない
- Lucene はポスティングリストと同じファイルにターム頻度も保存されるが、ターム頻度の情報を読み飛ばすコストは不明である
- (実際に TF のデータ読込みは行われるのでそれなりに不利だと思う)
- 実験の方法
- 1 プロセス 8 スレッドで実行
- 98,000 のクエリログを 2 回走らせて 2 回目の計測を記録
- クエリに関連するインデックスがページインされた状態のパフォーマンスを調べるため
- プロダクション環境下での負荷に近いはず
- Table 3: 実験結果
- BitFunnel は 5 つのシャードすべてで非常に高い QPS を達成している
- ポスティングあたりに必要なビット (bits-per-posting) は大きい
- = インデックスサイズが大きい
- Lucene の結果が書かれてないのは、必ずターム頻度 (TF) も一緒に保存してしまうから?
- 5 でシステムの利用効率の指標として導入した DQ (QPS と bits-per-posting の比) でも PEF にやや勝ってる?
- シャード C, D, E で勝ち
- とくに文書長の大きいシャード E では 4.2 倍の DQ
- (本文では触れられていないが数%くらい false positive が発生している)
- 文書長が大きい文書が多いコーパスでは BitFunnel が有利という結果