論文メモ 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のアルゴリズムは、ソートされた直積のシーケンスを返す。
論文をこちらからダウンロードできます。