Efficiently searching archival data for historical similarities (2007)

With recent developments in the areas of data warehousing and data mining, there has been an increasing interest in querying multiple snapshots of data, often stored in temporal databases, semi-structured document collections, and OLAP applications. Similarity queries, in particular, is an important class of queries with growing applications in fields as diverse as data mining, pattern recognition, multimedia databases, and bioinformatics. This thesis addresses the problem of efficiently answering similarity queries on historical market-basket data and multidimensional histories. 
The thesis introduces a domain-independent filter-and-refine framework for evaluating order-preserving similarity queries on historical market-basket data. For instance, given a database of customer transactions and a time period, a query is customers with similar purchasing behaviors over this period. Our work is different from previous work on time-series, in that we address the general problem where a history cannot be modeled effectively as a time-series, hence the conventional relevant approaches are not applicable. We propose a similarity measure for histories, based on a constrained aggregation of the similarities between their constituent observations. Given the non-metric nature of our measure, some upper bounds are proposed and an algorithm is developed that uses an index to prune histories that are guaranteed not to be in the answer set of a query. Experimental results on real and synthetic data confirm the effectiveness and efficiency of our approach. For instance, when the minimum length of a match is provided, our approach achieves up to an order of magnitude speed up over alternative methods. 
The thesis further studies the problem in a slightly more constrained domain where a history is modeled as a d separate time-series. While there are some solutions for special cases where d ≤ 4, none of these works scale up well to high-dimensional histories. To address the problem, we propose a class of summaries for histories with a few interesting properties. First, for commonly used distance functions, the summaries can be used to efficiently prune histories that are guaranteed not to be in the answer set of a query. Second, histories can be indexed based on their summaries, hence the qualifying candidates can be efficiently retrieved. To further reduce the number of unnecessary distance computations for false positives, we propose a finer level approximation of histories and an algorithm to find an approximation with the least maximum distance estimation error, before seeing queries. We also investigate adaptive splitting of histories and develop a few splitting schemes and heuristics to enhance the quality of our approximations, and to improve the performance of our similarity queries. Our experimental results confirm that the combination of our feature extraction approaches and the indexability of our summaries can improve upon existing methods when d ≤ 4 and scales up for larger values of d and database sizes, based on our experiments on real and synthetic data of 17-dimensional histories.