| 講演名 | 2009-07-28 マージン最大化によるメトリック空間分割手法(一般,「ユビキタス,センサ環境におけるデータベース」,及び一般) 倉沢 央, 深川 大路, 高須 淳宏, 安達 淳, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | メトリック空間を対象とした類似検索索引では,検索処理の枝刈りのために空間を効果的に分割することが求められる.本稿は,最大マージン化によるメトリック空間分割手法,Maximal Metric Margin Partitioning(MMMP)を提案する.MMMPではデータの分布,特にクラスタ形状にもとづいて空間を分割する.クラスタの境界間の距離が最大になる分割面となるように工夫されている点が本手法の特徴である.本稿はさらに,MMMPを用いた類似検索索引の一例としてMMMP-Indexも提案する.実験により,MMMP-IndexはMMMPの枝刈り効果により検索処理コストを削減できることを示した.特にクラスタ化したデータに対して効果を発揮し,比較手法の3分の2程度にまで距離計算コストを削減できた. |
| 抄録(英) | A fundamental issue that confronts the development of an index for similarity searches in metric spaces is how to divide the data effectively for search pruning. We propose Maximal Metric Margin Partitioning (MMMP), a partitioning scheme for similarity search indexes. MMMP divides the data space based on its distribution patterns, especially the boundaries of clusters. A partitioning surface created by MMMP is at maximum distances from the two cluster boundaries. MMMP is the first similarity search index approach to focus on the partitioning surfaces and data distribution patterns. We also present an indexing scheme, named the MMMP-Index, that uses MMMP and pivot filtering. The MMMP-Index discards many objects that are not relevant to a query by MMMP, and it reduces the query execution cost. Experimental results show that MMMP effectively indexes clustered data and reduces the search cost. For clustered vector data, the MMMP-Index reduces the computational cost to less than two thirds that of the compared schemes. |
| キーワード(和) | 類似検索 / 検索索引 / メトリック空間 / マージン |
| キーワード(英) | Similarity Search / Index / Metric Space / Margin |
| 資料番号 | DE2009-3 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2009/7/21(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | マージン最大化によるメトリック空間分割手法(一般,「ユビキタス,センサ環境におけるデータベース」,及び一般) |
| サブタイトル（和） | |
| タイトル（英） | Maximal Metric Margin Partitioning for Similarity Search Index |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 類似検索 / Similarity Search |
| キーワード(2)（和/英） | 検索索引 / Index |
| キーワード(3)（和/英） | メトリック空間 / Metric Space |
| キーワード(4)（和/英） | マージン / Margin |
| 第 1 著者 氏名（和/英） | 倉沢 央 / Hisashi KURASAWA |
| 第 1 著者 所属（和/英） | 東京大学大学院 The University of Tokyo |
| 第 2 著者 氏名（和/英） | 深川 大路 / Daiji FUKAGAWA |
| 第 2 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 第 3 著者 氏名（和/英） | 高須 淳宏 / Atsuhiro TAKASU |
| 第 3 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 第 4 著者 氏名（和/英） | 安達 淳 / Jun ADACHI |
| 第 4 著者 所属（和/英） | 国立情報学研究所 National Institute of Informatics |
| 発表年月日 | 2009-07-28 |
| 資料番号 | DE2009-3 |
| 巻番号（vol） | vol.109 |
| 号番号（no） | 153 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |