Fast Multivariate Search on Large Aviation Datasets
Kanishka Bhaduri, Qiang Zhu, Nikunj C. Oza, Ashok N. Srivastava · NASA Technical Reports Server (NASA) · 2010
AbstractMultivariate Time-Series (MTS) are ubiquitous, and are generated inareas as disparate as sensor recordings in aerospace systems, music andvideo streams, medical monitoring, and financial systems. Domain expertsare often interested in searching for interesting multivariate patterns fromthese MTS databases which can contain up to several gigabytes of data.Surprisingly, research on MTS search is very limited. Most existing workonly supportsquerieswith the same length of data, or queries on a fixedsetof variables. In this paper, we propose an efficient and flexible subsequencesearch framework for massive MTS databases, that, for the first time,enables querying on any subset of variables with arbitrary time delaysbetween them. We propose two provably correct algorithms to solve thisproblem — (1) an R ∗ -tree Based Search (RBS) which uses MinimumBounding Rectangles (MBR) to organize the subsequences, and (2) a ListBased Search (LBS) algorithm which uses sorted lists for indexing. Wedemonstrate the performance of these algorithms using two large MTSdatabases from the aviation domain, each containing several millions ofobservations. Both these tests show that our algorithms have very highprune rates (>95%) thus needing actual disk access for only less than 5%of the observations. To the best of our knowledge, this is the first flexibleMTS search algorithm capable of subsequence search on any subset ofvariables. Moreover, MTS subsequence search has never been attemptedon datasets of the size we have used in this paper.