| 講演名 | 2011-12-16 分散環境におけるL_1距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価(データ処理アルゴリズム,e-science and Big Data,一般) 古賀 久志, 渡辺 俊典, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 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 |
| 資料番号 | DE2011-40 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2011/12/9(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 分散環境におけるL_1距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価(データ処理アルゴリズム,e-science and Big Data,一般) |
| サブタイトル（和） | |
| タイトル（英） | A Method to Reduce Remote Accesses in L_1-Distance-based Distributed Locality-Sensitive Hashing and Its Implementation Evaluation |
| サブタイトル（和） | |
| キーワード(1)（和/英） | Locality-Sensitive Hashing / Locality-Sensitive Hashing |
| キーワード(2)（和/英） | ハッシュバケツ / Hash Bucket |
| キーワード(3)（和/英） | 分散環境 / Remote Access |
| キーワード(4)（和/英） | リモートアクセス / Distributed Environment |
| キーワード(5)（和/英） | 応答時間 / Response Time |
| 第 1 著者 氏名（和/英） | 古賀 久志 / Hisashi KOGA |
| 第 1 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, University of Electro-Communications |
| 第 2 著者 氏名（和/英） | 渡辺 俊典 / Toshinori WATANABE |
| 第 2 著者 所属（和/英） | 電気通信大学大学院情報システム学研究科 Graduate School of Information Systems, University of Electro-Communications |
| 発表年月日 | 2011-12-16 |
| 資料番号 | DE2011-40 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | 361 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |