講演抄録/キーワード |
講演名 |
2014-12-01 15:15
[ポスター講演]類似検索を行うLocality-Sensitive Hashingのスケーラブルなハードウェアアーキテクチャ ○定久紀基・山本佳生・金 多厚・福田 エリック 駿・浅井哲也・本村真人(北大) ICD2014-83 CPSY2014-95 エレソ技報アーカイブへのリンク:ICD2014-83 |
抄録 |
(和) |
Locality-Sensitive Hashing(LSH)は、従来のハッシュ法とは異なり、類似したデータが近いハッシュ値となるハッシュ法である。その特性から大量のデータを高速に分類できるため、ビックデータの処理に応用できる。またハッシュ値の計算に複雑な乗算、除算を含まないためHWに向いている。これまで、高速化のためにLSHをハードウェア実装し活用する研究はあるが、特定のアプリケーションを想定して、決まった入力データを効率良く演算するよう演算部を最適化されている。したがって、特定の形式の入力データでしか使用できず、他のデータ形式に対応することは困難である。そこで本研究では、用途によって変わる様々な次元の入力データに容易に対応できる拡張性を持つLSHアーキテクチャを提案する。LSHではハッシュ値を入力データと正規分布を持つ乱数列から選ばれたベクトルとの内積によって計算する。本アーキテクチャでは、Linear Feedback Shift Register(LFSR)によって作られた一様乱数を中心極限定理に従い足し合わせて正規分布を持つ乱数列を生成する。LFSRは長い周期を持ちそれぞれの状態が異なる値を持つため一様乱数として良く、状態遷移が確定的であるため同じ初期状態を与えてやれば同じ乱数列を作ることができる。そのため、乱数列の生成にLFSRを計算のたびに同じ初期状態にリセットすることで毎データ同じランダムベクタを用いた内積ができ、LFSRのビット幅を増やすことで様々な次元のデータに対応できる。 |
(英) |
Locality-Sensitive Hashing (LSH) is a hash function that projects similar data into memory closely. In similarity searching, LSH is useful for fast indexing and search. Additionally, its complexity does not depend on database size, so it is suitable for large-scale data processing. Some works implement LSH on wire because it is simple, powerful and suitable for hardware implementation. However their LSH module is optimized for applications, and does not have scalability. Therefore, we propose a scalable hardware architecture of LSH. LSH calculates a dot product of data and random vectors chosen from normal distribution. In order to create random vectors, our approach uses Linear Feedback Shift Register (LFSR) to generate uniform random numbers, and sums these numbers to normal distribution according to the central limit theorem. While its state transition is predictable, LFSR is a pseudo random number generator because of its very long cycle and its independent states. Moreover, LFSR can generate the same random vector by initializing it before calculation. By using LFSR, our LSH module is adaptable to correspond to input data with various dimensions by simply changing the bit width. |
キーワード |
(和) |
Locality-sensitive Hashing / 類似検索 / ハッシング / / / / / |
(英) |
Locality-sensitive Hashing / similarity search / hashing / / / / / |
文献情報 |
信学技報, vol. 114, no. 345, ICD2014-83, pp. 45-45, 2014年12月. |
資料番号 |
ICD2014-83 |
発行日 |
2014-11-24 (ICD, CPSY) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ICD2014-83 CPSY2014-95 エレソ技報アーカイブへのリンク:ICD2014-83 |
|