論文メモ 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は、\(Q\)の中央値を\(D\)から再帰的に探索する。 Web検索エンジンのために開発された背景から、\(Q\)をクエリ、\(D\)をドキュメントととらえると考えやすくなるだろう。 次の図は再帰的な探索の様子を示す。 中央値があれば返り値に加える。 次に中央値を境に\(Q\)を2つのシーケンスに分割する。 おなじく\(D\)も、\(Q\)の中央値と比べた大小で2つのシーケンスに分割する。 そして、大小関係がおなじ\(D\)と\(Q\)の部分シーケンス2組について再帰的に中央値の探索を繰り返す。 algorithm.png

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

algorithm.png

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