|
naistar (NAIST Academic Repository) >
学術リポジトリ naistar / NAIST Academic Repository naistar >
テクニカルレポート / Technical Report >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/10061/3194
|
| Title: | Similarity search for adaptive ellipsoid queries using spatial transformation |
| Authors: | Sakurai, Yasushi
Yoshikawa, Masatoshi
Kataoka, Ryoji
Uemura, Shunsuke
サクライ, ヤスシ
ヨシカワ, マサトシ
カタオカ, リョウジ
ウエムラ, シュンスケ
櫻井, 保志
吉川, 正俊
片岡, 良治
植村, 俊亮 |
| Issue Date: | May-2002 |
| Publisher: | Nara Institute of Science and Technology |
| Series/Report no.: | Information Science Technical Report ~ TR2002009 |
| Abstract: | 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 present 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. Since bounding rectangles in the original space are transformed into multi-dimensional polygons in the new space, and thus incurring high CPU-cost for distance calculations, our proposed method approximates a polygon by the rectangle that totally encloses the polygon, and measures the distance from the query point to the rectangle instead to the polygon in the Euclidean space. It follows that the spatial transformation technique guarantees no false drops. 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. We also present the multiple spatial transformation technique as an extension of the spatial transformation technique. The multiple spatial transformation technique adjusts the tree structures to suit typical ellipsoid queries;the search algorithm utilizes the adjusted structure. This technique reduces both page accesses and CPU time for ellipsoid queries. Experiments using various matrices and index structures demonstrate the superiority of the proposed methods. |
| URI: | http://hdl.handle.net/10061/3194 |
| URI: | http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=60183 |
| Fulltext: | http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=60183 |
| ISSN: | 0919-9527 |
| Text Version: | author |
| Appears in Collections: | テクニカルレポート / Technical Report
|
Files in This Item:
There are no files associated with this item.
|
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
|
