Database Reference
In-Depth Information
CHAPTER 2
A SURVEY OF RECENT METHODS FOR EFFICIENT
RETRIEVAL OF SIMILAR TIME SEQUENCES
Magnus Lie Hetland
Norwegian University of Science and Technology
Sem Sælands vei 7-9
NO-7491 Trondheim, Norway
E-mail: magnus@hetland.org
Time sequences occur in many applications, ranging from science and
technology to business and entertainment. In many of these applica-
tions, searching through large, unstructured databases based on sample
sequences is often desirable. Such similarity-based retrieval has attracted
a great deal of attention in recent years. Although several different
approaches have appeared, most are based on the common premise of
dimensionality reduction and spatial access methods. This chapter gives
an overview of recent research and shows how the methods fit into a
general context of signature extraction.
Keywords
: Information retrieval; sequence databases; similarity search;
spatial indexing; time sequences.
1. Introduction
Time sequences arise in many applications—any applications that involve
storing sensor inputs, or sampling a value that changes over time. A problem
which has received an increasing amount of attention lately is the problem
of
similarity retrieval
in databases of time sequences, so-called “query by
example.” Some uses of this are [Agrawal
et al
. (1993)]:
•
Identifying companies with similar patterns of growth.
•
Determining products with similar selling patterns.
•
Discovering stocks with similar movement in stock prices.
23
