分散環境におけるL_1距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価

摘要

Locality-Sensitive Hashing（LSH）は高次元データに対する近似最近接点探索アルゴリズムである．LSH は高速な反面，ハッシュテーブルを複数個使用するため空間計算量が非常に大きい．そのため，大規模なデータに適用するには，LSHを複数計算機に分散して実現する技術が必要になる．LSHを分散環境で実現する場合，単純には各ノードにハッシュテーブルを均等に固定数ずつ配置する手法が考えられる．しかし，この方法では検索時に全ハッシュテーブルへアクセスする際に多数のリモートアクセスが発生し，通信がボトルネックとなる分散環境では応答時間が長くなる．本研究ではハッシュバケツの配置を工夫し，同じデータを含む異なるハッシュテーブル上のハッシュバケツをなるべく同じノード上に配置する方式を提案する．提案方式ではクエリ処理時に1回のリモートアクセスで複数のハッシュバケツへアクセスできるので，リモートアクセス回数が削減される．