Similarity-based Search over Time Series and Trajectory Data

Speaker:	Dr. Lei Chen
		University of Waterloo

Title:		"Similarity-based Search over Time Series and
		 Trajectory Data"

Date:		Thursday, 12 May 2005

Time:		3:00 pm - 4:00 pm

Venue:		Room 3464 (Conference Room, via lift nos. 25/26), HKUST


ABSTRACT:

Time series data have been used in many applications, such as financial
data analysis and weather forecasting. Similarly, trajectories of moving
objects are often used to perform movement pattern analysis in
surveillance video and sensor monitoring systems. These applications
require finding, from among a large set of time series or trajectory data,
those that are similar to a query data (the similarity-based retrieval
problem). Most of this data are unclean, containing local time shifting
and noise, while most of the previous work in this area has developed
techniques that work on clean data. In this talk, I address
similarity-based retrieval of time series and trajectory data in the
presence of local time shifting and noise. In particular, I will present
two novel distance functions: a metric distance function, called Edit
distance with Real Penalty (ERP), that can support local time shifting,
and, Edit Distance on Real sequence (EDR) that can handle noise as well as
local time shifting, but is not metric. Since the proposed distance
functions are computationally expensive, I propose several indexing and
pruning methods to improve the retrieval efficiency. For ERP, a framework
is developed to index time series or trajectory data under a metric
distance function, which exploits the pruning power of lowering bounding
and triangle inequality. For EDR, three pruning techniques mean value
Q-grams, near triangle inequality, and histograms are developed to improve
the retrieval efficiency.



**********************
Biography:

Lei Chen received the BS degree in computer science from Tianjin
University, Tianjin, China, in 1994, and the MS degree in computer science
from Asian Institute of Technology, Bangkok, Thailand, in 1997. He
recently completed his PhD degree in Computer Science at University of
Waterloo, Canada, working on similarity-based retrieval, video and image
data modeling and indexing, and video segmentation. His research interests
include multimedia databases, indexing methods, data mining, machine
learning, and image and video processing. He is a member of ACM and IEEE.