| Presentation | 2001/7/11 A Similarity Search Technique for Ellipsoid Queries Yasushi Sakurai, Masatoshi Yoshikawa, Shunsuke Uemura, Ryoji Kataoka, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | similarity search / high-dimensional data / ellipsoid queries / STT / spatial indices |
| Paper # | DE2001-65 |
| Date of Issue |
| Conference Information | |
| Committee | DE |
|---|---|
| Conference Date | 2001/7/11(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) | A Similarity Search Technique for Ellipsoid Queries |
| Sub Title (in English) | |
| Keyword(1) | similarity search |
| Keyword(2) | high-dimensional data |
| Keyword(3) | ellipsoid queries |
| Keyword(4) | STT |
| Keyword(5) | spatial indices |
| 1st Author's Name | Yasushi Sakurai |
| 1st Author's Affiliation | NTT Cyber Space Laboratories() |
| 2nd Author's Name | Masatoshi Yoshikawa |
| 2nd Author's Affiliation | Graduate School of Information Science Nara Institute of Science and Technology |
| 3rd Author's Name | Shunsuke Uemura |
| 3rd Author's Affiliation | Graduate School of Information Science Nara Institute of Science and Technology |
| 4th Author's Name | Ryoji Kataoka |
| 4th Author's Affiliation | NTT Cyber Space Laboratories |
| Date | 2001/7/11 |
| Paper # | DE2001-65 |
| Volume (vol) | vol.101 |
| Number (no) | 192 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |