The Department of Computer Science at the University of Cyprus cordially invites you to the Colloquium entitled:

Stepwise kNN Search on Vertically Stored Time Series


Speaker: Dr. Panagiotis Karras
Affiliation: National University of Singapore, Singapore
Category: Colloquium
Location: Room 148, Faculty of Pure and Applied Sciences (FST-01), 1 University Avenue, 2109 Nicosia, Cyprus (directions)
Date: Friday, June 24, 2011
Time: 12:00-13:00 EET
Host: Demetris Zeinalipour (dzeina AT

Nearest-neighbor search over time series has received vast research attention as a basic data mining task. Still, node of the hitherto proposed methods scales well with increasing time series length. This is due to the fact that all methods encounter the curse of dimensionality. In particular, traditional methods utilize an index to search in a reduced-dimensionality feature space; however, for high timeseries length, search with such an index yields many false hits that need to be eliminated by accessing the full records. An attempt to reduce false hits by indexing more features exacerbates the curse of dimensionality, and vice versa. A recently proposed alternative, iSAX, uses symbolic approximate representations accessed by a simple file-system directory as an index. Still, iSAX also encounters false hits, which are again eliminated by accessing records in full: once a false hit is generated by the index, there is no second chance to prune it; thus, the pruning capacity iSAX provides is also one-off. This paper proposes an alternative approach to time series kNN search, following a nontraditional pruning style. Instead of navigating through candidate records via an index, we access their features, obtained by a multi-resolution transform, in a stepwise sequential-scan manner, one level of resolution at a time, over a vertical representation. Most candidates are progressively eliminated after a few of their terms are accessed, using pre-computed information and a tight double-bounding scheme (i.e., not only lower, but also upper distance bounds). Our experimental study with large-scale long time-series data confirms the advantage of our approach over both the current state-of-the-art method, iSAX, and classical index-based methods.

Short Bio:
Panagiotis Karras is an LKY Postdoctoral Fellow at the National University of Singapore. He earned a Ph.D. in Computer Science from the University of Hong Kong and an M.Eng. in Electrical and Computer Engineering from the National Technical University of Athens. In 2008, he received the Hong Kong Young Scientist Award. He has also held positions at the University of Zurich and the Technical University of Denmark. His research interests are in data mining, algorithms, data streams, spatial data management, anonymization, indexing, and similarity search. His work has been published in major database and data mining conferences and journals.

Video Online:
 Recorded Video available through vimeo

  Mailing List:

Sponsor: The CS Colloquium Series is supported by a generous donation from Microsoft