Similarity-based Search over Time Series and Trajectory Data

Speaker:	Dr. Lei CHEN
		Department of Computer Science
		Hong Kong University of Science & Technology


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

Date:		Monday, 14 Nov 2005

Time:		4:00pm - 5:00pm

Venue:		Lecture Theatre F (near 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. At the end of this talk, I will present some
current research projects that I am working on.


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

Dr. Lei Chen is an assistant professor of Computer Science Department at
Hong Kong University of Science and Technology. He 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.