A Similarity Search Method of Moving Object Databases based on Dissimilarity with respect to a Reference Data

摘要

R-trees and K-D-tress are often used to index time series data such as moving objects data for efficient similarity search which are constructed by translating the data into a frequency domain using a feature extraction function such as Fourier transformation. However, there is a problem in that one-dimensional index structures such as B-tree and B+-tree, which are widely used in traditional database management system, cannot be used because the frequency domain is multi-dimensional. In order to resolve this problem, we propose an indexing method of moving object data whose index values are scalar values. This method need to select one moving object stored in the moving object database to be a reference data, and the dissimilarities to all other moving object data are calculated so that the dissimilarity measures are attached to them as indices. Two problems happen when we employee this method: First, since this indexing does not preserve distance, it is not always true that two moving object data are similar even though index values are in neighbor. Second, it is necessary to make clear what data should be selected as the reference data in order to shorten the average time for similar search. These are addressed in this paper.