Nikunj C. Oza's Publications

Sorted by DateClassified by Publication TypeClassified by Research Category

Fast and Flexible Multivariate Time Series Subsequence Search

Fast and Flexible Multivariate Time Series Subsequence Search. Kanishka Bhaduri, Qiang Zhu, Nikunj C. Oza, and Ashok N. Srivastava. In IEEE International Conference on Data Mining (ICDM-2010), December 2010.

Download

[PDF]437.7kB  

Abstract

Multivariate Time-Series (MTS) are ubiquitous, and are generated in areas as disparate as sensor recordings in aerospace systems, music and video streams, medical monitoring, and Þnancial systems. Domain experts are often interested in searching for interesting multivariate patterns from these MTS databases which can contain up to several gigabytes of data. Surprisingly, research on MTS search is very limited. Most existing work only supports queries with the same length of data, or queries on a Þxed set of variables. In this paper, we propose an efÞcient and ßexible subsequence search framework for massive MTS databases, that, for the Þrst time, enables querying on any subset of variables with arbitrary time delays between them. We propose two provably correct algorithms to solve this problem Ñ (1) an R? -tree Based Search (RBS) which uses Minimum Bounding Rectangles (MBR) to organize the subsequences, and (2) a List Based Search (LBS) algorithm which uses sorted lists for indexing. We demonstrate the performance of these algorithms using two large MTS databases from the aviation domain, each containing several millions of observations. Both these tests show that our algorithms have very high prune rates (>95\%) thus needing actual disk access for only less than 5\% of the observations. To the best of our knowledge, this is the Þrst ßexible MTS search algorithm capable of subsequence search on any subset of variables. Moreover, MTS subsequence search has never been attempted on datasets of the size we have used in this paper.

BibTeX Entry

@inproceedings{bhzh10,
	author = {Kanishka Bhaduri, Qiang Zhu, Nikunj C. Oza, and Ashok N. Srivastava},
	title = {Fast and Flexible Multivariate Time Series Subsequence Search},
	booktitle = {IEEE International Conference on Data Mining (ICDM-2010)},
	month = {December},
	abstract = {Multivariate Time-Series (MTS) are ubiquitous, and are generated in areas as disparate as sensor recordings in aerospace systems, music and video streams, medical monitoring, and Þnancial systems. Domain experts are often interested in searching for interesting multivariate patterns from these MTS databases which can contain up to several gigabytes of data. Surprisingly, research on MTS search is very limited. Most existing work only supports queries with the same length of data, or queries on a Þxed set of variables. In this paper, we propose an efÞcient and ßexible subsequence search framework for massive MTS databases, that, for the Þrst time, enables querying on any subset of variables with arbitrary time delays between them. We propose two provably correct algorithms to solve this problem Ñ (1) an R? -tree Based Search (RBS) which uses Minimum Bounding Rectangles (MBR) to organize the subsequences, and (2) a List Based Search (LBS) algorithm which uses sorted lists for indexing. We demonstrate the performance of these algorithms using two large MTS databases from the aviation domain, each containing several millions of observations. Both these tests show that our algorithms have very high prune rates (>95\%) thus needing actual disk access for only less than 5\% of the observations. To the best of our knowledge, this is the Þrst ßexible MTS search algorithm capable of subsequence search on any subset of variables. Moreover, MTS subsequence search has never been attempted on datasets of the size we have used in this paper.},
	bib2html_pubtype = {Refereed Conference},
	bib2html_rescat = {Anomaly Detection},
	year = {2010}
}

Generated by bib2html.pl (written by Patrick Riley ) on Sun Mar 20, 2011 23:51:43