WEKO3
アイテム
多次元空間での最近傍点探索アルゴリズムの実験的解析と拡張
https://ipsj.ixsq.nii.ac.jp/records/32184
https://ipsj.ixsq.nii.ac.jp/records/321847f9b56d4-0b56-4faf-a19f-fd557035d153
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL98062006.pdf (522.1 kB)
|
Copyright (c) 1998 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 1998-05-20 | |||||||
| タイトル | ||||||||
| タイトル | 多次元空間での最近傍点探索アルゴリズムの実験的解析と拡張 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Experimental Analysis and Extentions of Algorithms for Nearest Neighbor Search in High Dimensions | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
| 資源タイプ | technical report | |||||||
| 著者所属 | ||||||||
| 東京大学大学院理学系研究科情報科学 | ||||||||
| 著者所属 | ||||||||
| 東京大学大学院理学系研究科情報科学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Science, University of Tokyo | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| Department of Information Science, University of Tokyo | ||||||||
| 著者名 |
遠藤, 雅也
× 遠藤, 雅也
|
|||||||
| 著者名(英) |
Masaya, Endo
× Masaya, Endo
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 高次元空間での最近傍点検索問題には、マルチメディア情報検索、パターン認識や統計解析などの応用分野があり、問題のサイズはより大規模化しており、この問題を高速に解くことは非常に重要である。Clarksonが近接履歴グラフを逐次的に、概念的な点集合を用い近似的に構成し、近似的に検索をする方法を提案している。本論文では、Clarksonの方法を一部変更した方法を提案する。具体的には、近接履歴グラフを更新する際に、これまでの履歴構造を利用するようにした。これにより、ある条件の下、検索時間を短縮することができた。また、この方法の解析および実装をし、一様分布と頻度ベクトルデータを用い、Clarksonの方法との比較を行なう。 | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | The nearest neighbor problem for high dimensional space has applications in multimedia information retrieval, pattern recognition, and statistical data analysis. It is important to solve this problem quickly. Clarkson gives an approximate algorithm constructing a Voronoi diagram incrementally and approximately in conceptual setting. In this thesis, we modify the algorithm. Clarkson's algorithm computes strictly nearest neighbors in constructing a Voronoi diagram incrementally. However our algorithm computes approximately using a present data structure. By this modification, we reduce a query time under a specific condition. Besides, we analyze and implement our algorithm and compare it to Clarkson's one by using uniformly distributed data and data from real world. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN1009593X | |||||||
| 書誌情報 |
情報処理学会研究報告アルゴリズム（AL） 巻 1998, 号 41(1998-AL-062), p. 41-48, 発行日 1998-05-20 |
|||||||
| Notice | ||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||
| 出版者 | ||||||||
| 言語 | ja | |||||||
| 出版者 | 情報処理学会 | |||||||
