| 講演名 | 2001/7/11 楕円体問合せのための類似探索手法の提案 櫻井 保志, 吉川 正俊, 植村 俊亮, 片岡 良治, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 類似検索メカニズムはユークリッド距離関数のみならず, より一般的な楕円体距離関数を扱える能力を持つことが望ましい.本論文では, 空間変換法(STT;Spatial Transformation Technique)と呼ぶ楕円体問合せのための新たな探索手法を提案する.提案手法は空間変換の概念に基づいており, 楕円体距離関数に基づく問合せを効率的に支援することができる.これまでにも, 多次元索引構造を用いて楕円体問合せを処理する手法が提案されているが, これらの手法は問合せ点と包囲矩形との距離の計算に多くの時間を必要とし, ディスクアクセスコストよりも高いCPUコストが生じる.提案手法の基本的なアイデアは, 問合せ点からの距離を楕円体距離関数で計算しなければならないような元の空間に位置する包囲矩形を, ユークリッド距離関数に基づく新たな空間に位置する空間オブジェクトに変換することである.従来手法と比較して, 提案手法は空間変換による距離近時によってCPUコストの低減化を達成している.評価実験では様々な問合せ行列を用い, 提案手法の有用性を示した. |
| 抄録(英) | Similarity retrieval mechanisms should utilize generalized quadratic form distance functions as well as the Euclidean distance function since ellipsoid queries parameters may vary with the user and situation. In this paper, we propose a spatial transformation technique that yields a new search method for adaptive ellipsoid queries. The technique is based on the notion of spatial transformation and efficiently supports adaptive ellipsoid queries with quadratic form distance functions. Although conventional search methods can support ellipsoid queries by using multi-dimensional index structures, these methods incur high CPU-cost for measuring distances between a query point and bounding rectangles with respect to quadratic form distance functions, which exceeds disk access cost on search processing. The basic idea is to transform the bounding rectangles in the original space, wherein distance from a query point is measured by quadratic form distance functions, into spatial objects in a new space wherein distance is measured by Euclidean distance functions. In contrast to the conventional methods, our proposed method significantly reduces CPU-cost due to the distance approximation by the spatial transformation;exact distance evaluations are avoided for most of the accessed bounding rectangles in the index structures. Experiments using various matrices demonstrate the superiority of the proposed method. |
| キーワード(和) | 類似探索 / 高次元データ / 楕円体問合せ / 空間変換法 / 空間索引 |
| キーワード(英) | similarity search / high-dimensional data / ellipsoid queries / STT / spatial indices |
| 資料番号 | DE2001-65 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2001/7/11(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 楕円体問合せのための類似探索手法の提案 |
| サブタイトル（和） | |
| タイトル（英） | A Similarity Search Technique for Ellipsoid Queries |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 類似探索 / similarity search |
| キーワード(2)（和/英） | 高次元データ / high-dimensional data |
| キーワード(3)（和/英） | 楕円体問合せ / ellipsoid queries |
| キーワード(4)（和/英） | 空間変換法 / STT |
| キーワード(5)（和/英） | 空間索引 / spatial indices |
| 第 1 著者 氏名（和/英） | 櫻井 保志 / Yasushi Sakurai |
| 第 1 著者 所属（和/英） | NTTサイバースペース研究所 NTT Cyber Space Laboratories |
| 第 2 著者 氏名（和/英） | 吉川 正俊 / Masatoshi Yoshikawa |
| 第 2 著者 所属（和/英） | 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 3 著者 氏名（和/英） | 植村 俊亮 / Shunsuke Uemura |
| 第 3 著者 所属（和/英） | 奈良先端科学技術大学院大学 情報科学研究科 Graduate School of Information Science Nara Institute of Science and Technology |
| 第 4 著者 氏名（和/英） | 片岡 良治 / Ryoji Kataoka |
| 第 4 著者 所属（和/英） | NTTサイバースペース研究所 NTT Cyber Space Laboratories |
| 発表年月日 | 2001/7/11 |
| 資料番号 | DE2001-65 |
| 巻番号（vol） | vol.101 |
| 号番号（no） | 192 |
| ページ範囲 | pp.- |
| ページ数 | 8 |
| 発行日 | |