Theoretical Analysis on Pruning Nearest Neighbor Candidates by Locality Sensitive Hashing
| 言語 | 英語 |
|---|---|
| 種類 | 国際会議等の予稿 |
| 著者 | Tomoyuki Mutoh, Masakazu Iwamura, Koichi Kise |
| 論文名 | Theoretical Analysis on Pruning Nearest Neighbor Candidates by Locality Sensitive Hashing |
| 論文誌名 | Proc. 2010 IEEE Region 10 Conference (TENCON2010) |
| ページ数 | 4 |
| 発表場所 | Fukuoka, Japan |
| 査読の有無 | 有 |
| 年月 | 2010年11月 |
| 分野 | 最近傍探索 |
| DOI | 10.1109/TENCON.2010.5686450 |
| キー | Mutoh2010_TENCON (id=1186) |
要約
Locality Sensitive Hashing (LSH) is one of the most popular methods of the approximate near neighbor search. In applications that require the nearest neighbors of queries in a short time, LSH is sometimes used in pruning of the candidates of nearest neighbors. While the pruning reduces the processing time greatly, it also reduces the chances of retrieving the exact nearest neighbors. However, the pruning of nearest neighbor candidates using LSH has not been considered theoretically. Thus in this paper, we investigate the pruning effect by deriving the formulae of retrieval accuracy and computational cost of distance calculation for uniformly distributed data. Furthermore, we make evaluations on the formulae by comparison between simulation results and the theoretical values.
関連ファイル
- …
この文献を出力
書式の定義
書式の定義の書き方
{authors} のように波括弧でフィールドを挿入します．[ ... ] で囲んだ部分は，その中のフィールドが空のとき丸ごと省略されます．使えるフィールド：
{authors}{authors_and}{authors_ja}{authors_ja_tight}{authors_en}{authors_en_and}{authors_tight}{first_author}{title}{title_ja}{title_en}{journal}{journal_ja}{journal_en}{book_title}{volume}{number}{series}{presen_id}{pages}{pp}{num_pages}{year}{month}{month_en}{month_short}{ym}{date}{date_ja}{date_en}{publisher}{address}{location}{review}{review_ja}{review_en}{reviewed_mark}{presen_type}{type}{type_label}{doi}{url}{key}{awards}