| Presentation | 2009-07-28 Maximal Metric Margin Partitioning for Similarity Search Index Hisashi KURASAWA, Daiji FUKAGAWA, Atsuhiro TAKASU, Jun ADACHI, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Similarity Search / Index / Metric Space / Margin |
| Paper # | DE2009-3 |
| Date of Issue |
| Conference Information | |
| Committee | DE |
|---|---|
| Conference Date | 2009/7/21(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Data Engineering (DE) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Maximal Metric Margin Partitioning for Similarity Search Index |
| Sub Title (in English) | |
| Keyword(1) | Similarity Search |
| Keyword(2) | Index |
| Keyword(3) | Metric Space |
| Keyword(4) | Margin |
| 1st Author's Name | Hisashi KURASAWA |
| 1st Author's Affiliation | The University of Tokyo() |
| 2nd Author's Name | Daiji FUKAGAWA |
| 2nd Author's Affiliation | National Institute of Informatics |
| 3rd Author's Name | Atsuhiro TAKASU |
| 3rd Author's Affiliation | National Institute of Informatics |
| 4th Author's Name | Jun ADACHI |
| 4th Author's Affiliation | National Institute of Informatics |
| Date | 2009-07-28 |
| Paper # | DE2009-3 |
| Volume (vol) | vol.109 |
| Number (no) | 153 |
| Page | pp.pp.- |
| #Pages | 6 |
| Date of Issue | |