NAISTAR
Advanced Search
Japanese | English

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=100033380&oldid=60183
Fulltext: http://library.naist.jp/mylimedio/dllimedio/show.cgi?bookid=100033380&oldid=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.

 

Copyright (c) 2007-2012 Nara Institute of Science and Technology All Rights Reserved.
DSpace Software Copyright © 2002-2010  Duraspace - Feedback