CS Colloquium Series @ UCY
Department of Computer Science - University of Cyprus
The Department of Computer Science at the University of Cyprus holds research colloquiums and social hours approximately once weekly. All university students, faculty, and staff are invited to attend. Notifications about new and upcoming events are automatically disseminated to a variety of institutional lists.
If you don't receive these notifications, but want to get informed about upcoming colloquium announcements, you can do the following:
List
RSS
Directions
Colloquium Coordinator: Demetris Zeinalipour
Colloquium: Stepwise kNN Search on Vertically Stored Time Series, Dr. Panagiotis Karras (National University of Singapore, Singapore), Friday, June 24, 2011, 12:00-13:00 EET.
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 |
Abstract:
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.
Multimedia File Available:
Multimedia File
Sponsor: The CS Colloquium Series is supported by a generous donation from  |