講演抄録/キーワード |
講演名 |
2011-12-16 10:45
分散環境におけるL1距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価 ○古賀久志・渡辺俊典(電通大) DE2011-40 |
抄録 |
(和) |
Locality-Sensitive Hashing (LSH) は高次元データに対する近似最近接点探索アルゴリズムである.LSHは高速な反面,ハッシュテーブルを複数個使用するため空間計算量が非常に大きい.そのため,大規模なデータに適用するには,LSHを複数計算機に分散して実現する技術が必要になる.LSHを分散環境で実現する場合,単純には各ノードにハッシュテーブルを均等に固定数ずつ配置する手法が考えられる.しかし,この方法では検索時に全ハッシュテーブルへアクセスする際に多数のリモートアクセスが発生し,通信がボトルネックとなる分散環境では応答時間が長くなる.本研究ではハッシュバケツの配置を工夫し,同じデータを含む異なるハッシュテーブル上のハッシュバケツをなるべく同じノード上に配置する方式を提案する.提案方式ではクエリ処理時に1回のリモートアクセスで複数のハッシュバケツへアクセスできるので,リモートアクセス回数が削減される. |
(英) |
Locality-Sensitive Hashing (LSH) is an approximate nearest-neighbor search algorithm for high-dimensional data. Though LSH processes a query very fast, LSH consumes much space, because it uses multiple hash tables. Therefore, in applying LSH to a large dataset, implementing LSH in distributed environments is crucial. One simple method is to have every node keep the same number of hash tables evenly. However, this method increases remote accesses, because many nodes must be accessed to access all the hash tables. Thus, this simple method suffers from the long query response time, when the communication delay is the bottleneck. This paper proposes to reduce remote accesses by assigning the hash buckets from different hash tables to the same node, if they store the same points. This strategy decreases remote accesses, since multiple hash buckets to be accessed are accessed with a single remote access. |
キーワード |
(和) |
Locality-Sensitive Hashing / ハッシュバケツ / 分散環境 / リモートアクセス / 応答時間 / / / |
(英) |
Locality-Sensitive Hashing / Hash Bucket / Remote Access / Distributed Environment / Response Time / / / |
文献情報 |
信学技報, vol. 111, no. 361, DE2011-40, pp. 1-6, 2011年12月. |
資料番号 |
DE2011-40 |
発行日 |
2011-12-09 (DE) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
DE2011-40 |