| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2014-12-01 15:15 ［ポスター講演］類似検索を行うLocality-Sensitive Hashingのスケーラブルなハードウェアアーキテクチャ ○定久紀基・山本佳生・金 多厚・福田 エリック 駿・浅井哲也・本村真人（北大）  ICD2014-83 CPSY2014-95 |
|
| 抄録 | （和） | 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 |
|
| 研究会情報 | |
| 研究会 | ICD CPSY |
| 開催期間 | 2014-12-01 - 2014-12-02 |
| 開催地（和） | 機械振興会館 |
| 開催地（英） | Kikai-Shinko-Kaikan Bldg. |
| テーマ（和） | 学生・若手研究会 |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | ICD |
| 会議コード | 2014-12-ICD-CPSY |
| 本文の言語 | 日本語 |
| タイトル（和） | 類似検索を行うLocality-Sensitive Hashingのスケーラブルなハードウェアアーキテクチャ |
| サブタイトル（和） | |
| タイトル（英） | A Scalable Hardware Architecture of Locality-Sesitive Hashing for similarity Search |
| サブタイトル（英） | |
| キーワード(1)（和/英） | Locality-sensitive Hashing / Locality-sensitive Hashing |
| キーワード(2)（和/英） | 類似検索 / similarity search |
| キーワード(3)（和/英） | ハッシング / hashing |
| キーワード(4)（和/英） | / |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 定久 紀基 / Tsunaki Sadahisa / |
| 第1著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 山本 佳生 / Kasho Yamamoto / |
| 第2著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 金 多厚 / Dahoo Kim / |
| 第3著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第4著者 氏名（和/英/ヨミ） | 福田 エリック 駿 / Eric S. Fukuda / |
| 第4著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第5著者 氏名（和/英/ヨミ） | 浅井 哲也 / Tetsuya Asai / |
| 第5著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 第6著者 氏名（和/英/ヨミ） | 本村 真人 / Masato Motomura / |
| 第6著者 所属（和/英） | 北海道大学 (略称： 北大) Hokkaido University (略称： Hokkaido Univ.) |
| 講演者 | 第1著者 |
| 発表日時 | 2014-12-01 15:15:00 |
| 発表時間 | 120分 |
| 申込先研究会 | ICD |
| 資料番号 | ICD2014-83, CPSY2014-95 |
| 巻番号（vol） | vol.114 |
| 号番号（no） | no.345(ICD), no.346(CPSY) |
| ページ範囲 | p.45 |
| ページ数 | 1 |
| 発行日 | 2014-11-24 (ICD, CPSY) |
[研究会発表申込システムのトップページに戻る]