Thumbnail
Access Restriction
Subscribed

Author Keogh, E.J. ♦ Pazzani, M.J.
Source IEEE Xplore Digital Library
Content type Text
Publisher Institute of Electrical and Electronics Engineers, Inc. (IEEE)
File Format PDF
Copyright Year ©1999
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Indexing ♦ Databases ♦ Medical diagnostic imaging ♦ Extraterrestrial measurements ♦ Time measurement ♦ Shape ♦ Computer science ♦ Electronic switching systems ♦ Read only memory ♦ Telemetry
Abstract Addresses the problem of similarity searching in large time-series databases. We introduce a novel indexing algorithm that allows faster retrieval. The index is formed by creating bins that contain time series subsequences of approximately the same shape. For each bin, we can quickly calculate a lower bound on the distance between a given query and the most similar element of the bin. This bound allows us to search the bins in best-first order, and to prune some bins from the search space without having to examine the contents. Additional speedup is obtained by optimizing the data within the bins such that we can avoid having to compare the query to every item in the bin. We call our approach STB (Shape To Bit-vector) indexing, and experimentally validate it on space telemetry, medical and synthetic data, demonstrating approximately an order-of-magnitude speedup.
Description Author affiliation: Dept. of Inf. & Comput. Sci., California Univ., Irvine, CA, USA (Keogh, E.J.)
ISBN 0769500463
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research ♦ Reading
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1999-07-30
Publisher Place USA
Rights Holder Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Size (in Bytes) 207.69 kB
Page Count 12
Starting Page 56
Ending Page 67


Source: IEEE Xplore Digital Library