| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 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 |
|
| 研究会情報 | |
| 研究会 | DE |
| 開催期間 | 2011-12-16 - 2011-12-16 |
| 開催地（和） | 京都産業大学 |
| 開催地（英） | Kyoto Sangyo University |
| テーマ（和） | e-science and Big Data, 一般 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | DE |
| 会議コード | 2011-12-DE |
| 本文の言語 | 日本語 |
| タイトル（和） | 分散環境におけるL1距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価 |
| サブタイトル（和） | |
| タイトル（英） | A Method to Reduce Remote Accesses in L1-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 |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 古賀 久志 / Hisashi Koga / コガ ヒサシ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 渡辺 俊典 / Toshinori Watanabe / ワタナベ トシノリ |
| 第2著者 所属（和/英） | 電気通信大学 (略称： 電通大) University of Electro-Communications (略称： UEC) |
| 講演者 | 第1著者 |
| 発表日時 | 2011-12-16 10:45:00 |
| 発表時間 | 25分 |
| 申込先研究会 | DE |
| 資料番号 | DE2011-40 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.361 |
| ページ範囲 | pp.1-6 |
| ページ数 | 6 |
| 発行日 | 2011-12-09 (DE) |
[研究会発表申込システムのトップページに戻る]