iSAX 2.0: Indexing and Mining One Billion Time Series/Database Cracking and the Path Towards Auto-tuning Database Kernels

September 6, 2011
Themis Palpanas and Stratos Idreos | University of Trento, CWI, the Dutch National Research Center for Mathematics and Computer Science

iSAX 2.0: Indexing and Mining One Billion Time Series

abstract

There is an increasingly pressing need, by several applications in diverse domains, for developing techniques able to index and mine very large collections of time series. Examples of such applications come from astronomy, biology, the web, and other domains. It is not unusual for these applications to involve numbers of time series in the order of hundreds of millions to billions.
In this paper, we describe iSAX 2.0, a data structure designed for indexing and mining truly massive collections of time series. We show that the main bottleneck in mining such massive datasets is the time taken to build the index, and we thus introduce a novel bulk loading mechanism, the first of this kind specifically tailored to a time series index.
We show how our method allows mining on datasets that would otherwise be completely untenable, including the first published experiments to index one billion time series, and experiments in mining massive data from domains as diverse as entomology, DNA and web-scale image collections.

Database Cracking and the Path Towards Auto-tuning Database Kernels

ABSTRACT:
Database cracking targets dynamic and exploratory environments where there is no sufficient workload knowledge and idle time to invest in physical design preparations and tuning. With DB cracking indexes are built incrementally, adaptively and on demand; each query is seen as an advice on how data should be stored. With each incoming query, data is reorganized on-the-fly as part of the query operators, while future queries exploit and continuously enhance this knowledge. Autonomously, adaptively and without any external human administration, the system quickly adapts to a new workload and reaches optimal performance when the workload stabilizes.

We will talk about the basics of DB cracking including selection cracking, partial and sideways cracking and updates. We will also talk about important open and on going research issues such as disk based cracking, concurrency control and integration of cracking with offline and online index analysis.

Speaker Details

Themis Palpanas is a professor of computer science at the University of Trento, Italy. He received the BS degree from the National Technical University of Athens, Greece, and the MSc and PhD degrees from the University of Toronto, Canada. Before joining the University of Trento, he worked at the IBM T.J. Watson Research Center. He has also worked for the University of California, Riverside, and visited Microsoft Research and the IBM Almaden Research Center. His interests include data management, data analysis, streaming algorithms, and business process management. His research solutions have been implemented in world-leading commercial data management products and he is the author of five US patents, three of which are part of commercial products in multi-billion dollar markets. He is the recipient of two Best Paper awards (ICDE 2010 and ADAPTIVE 2009). He is a founding member of the Event Processing Technical Society, and is serving on the Editorial Advisory Board of the Information Systems Journal and as an Associate Editor in the Journal of Intelligent Data Analysis. He is a General Co-Chair for VLDB 2013, has served on the program committees of several top database and data mining conferences, including SIGMOD, VLDB, ICDE, KDD, and ICDM, and has been a member of the IBM Academy of Technology Study on Event Processing.

Stratos holds a tenure track senior researcher position with CWI, the Dutch National Research Center for Mathematics and Computer Science. The main focus of his research is on adaptive query processing and database architectures, mainly in the context of column-stores. He also works on stream processing, distributed query processing and scientific databases. Stratos won the 2011 ACM SIGMOD Jim Gray Dissertation Award for his thesis on database cracking, while in 2010 he was named a “Distinguished Greek Scientist Excelling in Research abroad” by the Hellenic Minitry of National Defense. Stratos obtained his PhD from CWI and University of Amsterdam. In the past he has also been with the Technical University of Crete, Greece, and held research internship positions with Microsoft Research, Redmond, with EPFL, Switzerland and with IBM Almaden. In April 2011 he was also avisiting researcher with National University of Singapore. Web page: http://homepages.cwi.nl/~idreos