WEKO3
-
RootNode
アイテム
多次元データの高速近傍検索アルゴリズム
https://ipsj.ixsq.nii.ac.jp/records/48253
https://ipsj.ixsq.nii.ac.jp/records/48253a3b1584d-0aa8-4610-a951-76a3a03db6d9
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-NL03157002.pdf (193.2 kB)
|
Copyright (c) 2003 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2003-09-29 | |||||||
| タイトル | ||||||||
| タイトル | 多次元データの高速近傍検索アルゴリズム | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Fast Multidimensional Nearest Neighbor Search Algorithm | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 徳島大学高度情報化基盤センター | ||||||||
| 著者所属 | ||||||||
| 徳島大学工学部 | ||||||||
| 著者所属 | ||||||||
| 徳島大学高度情報化基盤センター | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Center for Advanced Information Technology, Tokushima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Faculty of Engineering, Tokushima University | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Center for Advanced Information Technology, Tokushima University | ||||||||
| 著者名 |
北, 研二
獅々堀正幹
大恵俊一郎
× 北, 研二 獅々堀正幹 大恵俊一郎
|
|||||||
| 著者名(英) |
Kenji, Kita
Masami, Shishibori
Shun-Ichiro, Oe
× Kenji, Kita Masami, Shishibori Shun-Ichiro, Oe
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 高次元空間における最近傍検索(nearest neighbor search)は、マルチメディア・コンテンツ検索、データ・マイニング、パターン認識等の分野における重要な研究課題の１つである。高次元空間では、ある点の最近点と最遠点との間に距離的な差が生じなくなるという現象が起こるため、効率的な多次元検索手法を設計することが極度に困難となる。本稿では、線形探索アルゴリズムにおける距離計算中の不要な演算を削減することにより、きわめて高速な最近傍検索アルゴリズムを提案する。さらに、不必要な演算を早期検出するために、要素の分散値を用いた次元ソート法、並びに主成分分析に基づくデータ変換法を提案する。実験によると、従来の SR-tree や VP-tree 等よりも 20倍?50倍高速であり、高次元の場合にも性能の劣化はほとんどない。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | Nearest neighbor search in high dimensional spaces is an interesting and important problem which is relevant for a wide variety of applications, including multimedia information retrieval, data mining, and pattern recognition. For such applications, the curse of high dimensionality tends to be a major obstacle in the development of efficient search methods. This paper addresses the problem of designing an efficient algorithm for high dimensional nearest neighbor search. The proposed algorithm is based on a simple linear search algorithm and eliminates unnecessary arithmetic operations from distance computations between multidimensional vectors. Moreover, we propose two techniques, a dimensional sorting method and a PCA-based method, to accelerate multidimensional search. Experimental results indicate that our scheme scales well even for a very large number of dimensions. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN10115061 | |||||||
| 書誌情報 |
情報処理学会研究報告自然言語処理（NL） 巻 2003, 号 98(2003-NL-157), p. 9-16, 発行日 2003-09-29 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
