論文メモ Fast Intersection Algorithms for Sorted Sequences

April 12, 2021

ソートされたシーケンスの直積を高速に求めるアルゴリズム Double Binary Searchを示した。 2つのシーケンス\(D\), \(Q\)があり、\(\mid D\mid=n\), \(\mid Q\mid=m\), \(n >= m\)であれば、平均と最悪時間計算量が、それぞれ、\(\mathcal{O}(m\log(n/m))\), \(m\)になる。本アルゴリズムは、Web検索エンジンで大きなシーケンスの直積を高速に求めるために開発された。

Double Binary Searchは、\(D\)にある\(Q\)の中央値と同値の要素を再帰的に探索する。 Web検索エンジンのために開発された背景から、\(Q\)をクエリ、\(D\)をドキュメントととらえると考えやすくなるだろう。次の図は再帰的な探索を描く。中央値があれば返り値に加える。次に中央値を境に\(Q\)を2つのシーケンスに分割する。おなじく\(D\)も、\(Q\)の中央値を境に2つのシーケンスに分割する。そして、大小関係がおなじ\(D\)と\(Q\)の部分シーケンス2組について再帰的に中央値の探索を繰り返す。

図のDouble Binary Searchのアルゴリズムは、ソートされた直積のシーケンスを返す。

論文をこちらからダウンロードできます。