A Similarity Search Algorithm for Ellipsoid Queries Using Spatial Transformation

A similarity retrieval mechanism should be able to deal with not only the Euclidean distance function but also a more general ellipsoid distance function. In this paper, the authors describe the Spatial Transformation Technique (STT), which is a search technique for ellipsoid queries. The proposed technique, which is based on spatial transformation concepts, can effectively support queries based on an ellipsoid distance function. Although techniques for processing ellipsoid queries by using a multidimensional index structure have previously been proposed, these techniques require a great deal of time to compute the distance between a query point and the bounding rectangle, which results in higher CPU costs than disk access costs. The basic idea of the proposed technique is to transform a bounding rectangle located in the original space, where the distance from a query point must be calculated by using an ellipsoid distance function, to an object in a Euclidean distance space. A bounding rectangle in the original space is changed to a multidimensional polygon when it is transformed to the new space, and a great deal of CPU time is required to calculate the distance between the multidimensional polygon and query point in the multidimensional space. Therefore, instead of using the multidimensional polygon for the distance calculation, the authors use a rectangle that circumscribes that multidimensional polygon. This ensures that the STT will not lead to a false drop. The proposed technique achieves a reduction in CPU costs compared with the conventional technique due to a distance approximation based on the spatial transformation. Evaluation experiments using various query matrices showed the effectiveness of the proposed technique. © 2004 Wiley Periodicals, Inc. Syst Comp Jpn, 36(1): 88–98, 2005; Published online in Wiley InterScience (). DOI 10.1002sscj.10307