Efficient similarity search in sequence databases-英文文献.pdf

Ecient Similarity Search In Sequence Databases  Rakesh Agrawal and Christos Faloutsos and Arun Swami IBM Almaden Research Center 650 Harry Road, San Jose, CA 95120 fragrawal,arun@ g March 4, 1994 Abstract We prop ose an indexing metho d for time sequences for pro cessing similarity queries. We use the Discrete Fourier Transform (DFT) to map time sequences to the frequency domain, the crucial observation b eing that, for most sequences of practical interest, only the rst few frequencies are strong. Another imp ortant observation is Parsevals theorem, which sp ecies that the Fourier transform preserves the Euclidean distance in the time or frequency domain. Having thus mapp ed sequences to a lower-dimensionality space by using only the rst few Fourier co ecients, we use R-trees to index the sequences and eciently answer similarity queries. We provide exp erimental results which show that our metho d is sup erior to search based on sequential scanning. Our exp eriments show that a few co ecients (1-3) are adequate to provide go o d p erformance. The p erformance gain of our metho d increases with the numb er and length of sequences. 1 Intro duction Sequences constitute a large p ortion of data stored in computers. There have b een several eorts to mo del time-sequenced data, to design languages to query such data, and to develop access structures to eciently pro cess such que