Data series are widely used in numerous domains. Analyzing this data is important for a variety of real-world applications and has been extensively studied over the past 25 years. At the core of the analysis task lies a classic algorithm called similarity search. A number of approaches have been proposed to support similarity search over massive data series collections. The results of two comprehensive data series experimental evaluations form the foundations of our future work, which will lead to the development of a novel index that can e ciently support both exact and approximate data series similarity search, as well as progressive query answering with bound guarantees. Based on the insights gained from the exhaustive study of the related work, the new index will surpass the state-the-art approximate and exact techniques both in performance and accuracy.
1 The order attribute can be angle, mass, frequency, position, or time [39]. When the order is based on time, the sequence is called a time series. The terms data series, time series and sequence are used interchangeably.
A data series is a sequence of ordered real values 1 . Data series are omnipresent in various domains from science and engineering to business and medicine [35]. The proliferation of IoT technologies is also heavily contributing to the explosive growth of data series collections to the order of terabytes [38]. A common subroutine to data series analytical tasks is a classic algorithm called similarity search. Therefore the research community has extensively studied the development of e cient similarity search algorithms for data series. The similarity search algorithm for data series returns the set of candidate data series in a collection that is similar to a given query series. This algorithm is often reduced to the nearest neighbor problem where data series are represented as data points in multidimensional space and their (dis)similarity is evaluated using a distance function.
Although a data series can be represented as a vector in high dimensional space, conventional vector-based approaches are not adapted for two reasons: (a) they cannot scale to thousands of dimensions; and (b) they do not exploit the correlation among dimensions typical for data series.
Similarity search methods can either return exact or approximate answers. Exact methods are costly while approximate methods o↵er better e ciency at the expense of losing some accuracy. We call approximate the methods that do not provide any guarantees on the results ng-approximate, and those that provide guarantees on the approximation error, -✏-approximate methods, where ✏ is the approximation error and , the probability that ✏ will not be exceeded.
A plethora of similarity search methods have been published by the community including techniques designed for generic vectors [24,23,7,14,46,20,25,44,5,36] and those specific to data series [3,41,27,42,47,34,33,40,15,9,43,45,10,49,30].
This work aims to propose a novel index that will support progressive query answering with probabilistic guarantees. We describe the related work, succinctly report the results of our extensive experimental evaluation of exact methods [17], and give a glimpse of some very interesting results from an ongoing experimental study focused on approximate methods [18]. Finally, we present our future work directions.
In our work, we focus on the problem of whole matching similarity search in collections with a very large number of data series, i.e., similarity search that produces approximate or exact results, by calculating distances on the whole (not a sub-) sequence. This is a very popular problem that lies at the core of several other algorithms, and is important for many applications in various domains in the real world [17].
Similarity search involves finding a set of data series in a collection that are similar to a query according to some definition of sameness. A common abstraction is to consider the query and candidate data series as points in a metric space and evaluating the sameness (or di↵erence) using the euclidean distance.
To develop e cient similarity search algorithms on massive datasets, two major costs need to be optimized: the cost of accessing data on disk (I/O) and the cost of comparing the query to candidates (CPU cost). Typically, the first cost is reduced by using summarization techniques that map the high-dimensional data to a lower-dimensional space, while the second cost is optimized with sophisticated data structures and search algorithms. Several similarity search meth-ceur-ws.org/Vol-2399/paper11.pdf ods have been proposed in the literature supporting either exact search [23,7,46,20,27,42], approximate search [24,25,44,5,36], or both [14,43,45,10,49,47,30,34].
In the following section, we provide a succinct description of the state-of-the-art similarity search methods and the summarizations techniques on which they are based. 1. Summarization Techniques. The Discrete Fourier Transform (DFT) [19] decomposes a data series into frequency coe cients, a subset of which represents a summarization of the data series.
The Discrete Haar Wavelet Transform (DHWT) [12] transforms a data series using Haar wavelets into a hierarchical representation.
Random projections map the raw high dimensional data into a lower dimensional space using a random matrix while preserving pairwise distances within a distortion threshold [26].
The Piecewise Aggregate Approximation (PAA) [28] and Adaptive Piecewise Constant Approximation (APCA) [11] techniques divide a data series into segments (of equal and arbitrary length, respectively) and approximate each segment with the mean of the points that belong to it. The Extended Adaptive Piecewise Approximation (EAPCA) [45] method enhance APCA by approximating each segment with the standard deviation in addition to the mean.
Symbolic Aggregate Approximation (SAX) [32] first approximates data series using PAA, then discretizes the PAA values into a compact binary representation.
Symbolic Fourier Approximation (SFA) [43] first transforms a data series into DFT coe cients, which are then approximated using a succinct symbolic approximation.
Optimized Product Quantization (OPQ) [21] applies a linear transformation on the data series to decorrelate it, then applies on it a product quantizer [25]. 2. Exact Similarity Search Methods. Below, we briefly describe algorithms that produce exact results.
The R*-tree [7] is a height-balanced spatial index that organizes data into a hierarchy of nested overlapping rectangles. Search returns all entries in leaves whose rectangle contains the query.
The M-tree [14] is a multidimensional index for metric space which partitions the data using hyper-spheres based on their relative distances. The search algorithm uses the triangular inequality to prune data.
The VA+file [20] is an improvement of the VA-file [46]. It creates a filter file containing summarizations of the raw data. Search uses the filter file to prune candidates based on a lower bounding distance. For e ciency reasons, we modified the VA+file to use the DFT transform instead of the Karhunen-Loève transform (KLT).
Stepwise [27] represents the data space in a multi-level hierarchical representation using DHWT summarizations. Search transforms a query into DHWT and filters out candidate based on upper and lower bounding distances.
The SFA method [43] builds a trie with SFA summarizations of the data. During query answering, a lower bounding distance is used to prune out candidates.
The UCR Suite [42] is an optimized sequential scan algorithm for exact matching that we consider as a baseline for performance comparisons.
The DSTree [45] index dynamically segments data using EAPCA. During search, it uses a lower bounding distance to prune the search space. iSAX2+ [10] is a bulk-loading index based on SAX. During search, a query is represented with SAX symbols and the candidates contained in non-pruned leaves are further refined using the euclidean distance. Pruning uses a lower bounding distance.
ADS+ [49] is the first adaptive data series index based on SAX. It starts with a minimal tree structure containing only summarizations, and then adds in the raw data to leaves during query answering. It supports a number of search options, in particular SIMS, a skip-sequential algorithm.
In addition to exact search, the MTree, SFA trie, DSTree, iSAX2+ and ADS+ also support ng-approximate search. 3. Approximate Similarity Search Methods. We now present the three most popular approximate methods.
SRS [44] belongs to the family of LSH methods, inspired by the randomized algorithm in [24]. It uses random projections to build a scalable index and supports approximate search with theoretical guarantees.
IMI [21,5] is an inverted index based on OPQ. A query is answered by returning all points corresponding to the corresponding entries in the inverted index. Returned results are ng-approximate.
HNSW [36] is an in-memory neighborhood graph exploiting the Voronoi Diagram and the Delaunay Triangulation. A greedy search returns the best candidates with high empirical accuracy but no formal theoretical guarantees.
We propose a novel data series index that can answer progressive similarity search queries with strong probability guarantees. In addition to this unique functionality, it also leverages the strengths and addresses the weaknesses of the state-of-the-art approximate and exact techniques. Completed Work. We outline the main contributions in [17]: (i) we provide a formal problem definition for data series similarity search, unifying conflicting terminology from di↵erent research communities; (ii) we present a survey of the state-of-the-art data series similarity search techniques (Table 1 summarizes each technique according to our definitions); and (iii) we conduct an extensive experimental evaluation for the e ciency of data series exact similarity search.
The study assessed ten state-of-the-art methods under the same experimental framework. To guard against implementation bias, we used a large number of comparison criteria including implementation-independent ones, and we reimplemented from scratch four methods that were not available in C/C++. Our implementations largely outperform the original ones both in time and space, thus enriching the landscape of data series similarity search methods.
In an e↵ort to make our results reproducible and support future research in the area, we share with the community a public archive containing all source codes, datasets, queries, results, and plots [1].
Based on the results of our study, we draw up recommendations to help users decide the best approach for their problem. Figure 1 shows a decision matrix given a typical hardware and query workload. The VA+file is particularly well-suited for long series in-memory while for shorter series, the DSTree is the best contender on disk, and iSAX2+ is the winner in-memory.
We present an elaborate discussion based on the deep insights gained about the data series similarity search problem. The main points are the following:
1. Unexpected results confirmed the importance of careful parameter tuning, hardware setup, implementation framework, and workload selection. In particular, Stepwise and ADS+ performed below our expectations while our optimized implementations of the DSTree and the VA+file helped bring them back to the spotlight. Moreover, our carefully crafted experiments identified optimal parameters that were di↵erent than the ones published in the original papers. Another important finding was that, unlike what was originally believed [29], the tightness of the lower bound of a given method does not alone predict its performance. In fact, it is of paramount importance to consider other factors such as the hardware platform and the the clustering quality of a an index.
2. A better understanding of current approaches helped pinpoint interesting avenues for improvement, in particular identifying the methods that would most benefit from modern hardware. For instance: (i) the DSTree is a very good candidate for parallelization as its index building is over 85% CPU cost; (ii) the performance of Stepwise can be significantly improved with a redesign of the physical storage and the use of modern hardware as the total cost of query answering is 50%-98% CPU; (iii) ADS+ can be enhanced with the use of asynchronous I/O to overcome the expensive random I/O incurred with each skip.
3. Although index building with iSAX-based indexes is much faster than with the DSTree, the latter achieves a better clustering as it adapts to the data distribution.
4. Choosing between an index scan and a serial scan is not a trivial decision. In fact, access path selection is an optimization problem that depends on a variety of factors including hardware, query pruning ratio, data characteristics, the accuracy of a summarization and the e cacy of the clustering provided by an index. Work In Progress. Our current work involves an experimental study that evaluates data series approximate similarity search, both in-memory and on-disk [18]. It di↵ers from other experimental studies which focused on the eciency of exact search [17], the accuracy of dimensionality reduction techniques and similarity measures for classification tasks [29,16,6], or in-memory data [31,4].
Our results show that some strikingly simple modifications to existing exact methods enable them to answer -✏-approximate queries and have excellent empirical performance. In fact, extensive experiments on large synthetic and real datasets, including the two largest real datasets publicly available, demonstrate that the extended techniques compete in memory and outperform on disk the state-of-the-art approximate techniques from the vector indexing community both in accuracy and e ciency. Figure 2 summarizes results for 100-NN queries on an in-memory 25GB data collection extracted from the Sift dataset [2]. We observe that our modifications to iSAX2+ enable it to outperform the popular ng-approximate search approaches HNSW and IMI (Faiss implementation) and the state-of-the-art LSH method SRS, in terms of combined indexing and query answering costs. We measure accuracy using MAP, a popular metric in the information retrieval literature [37,8]. Future Work. Inspired by the insights gained from our two experimental studies on the the inner workings of the di↵erent indexing approaches and the e↵ectiveness of their design choices, the key future direction for our work is the design and development of a novel data series index that will outperform the state-of-the-art approximate and exact techniques. The new index will also support progressive query answering [22] with probability guarantees, so as to further enable interactive exploration tasks on very large data series collections.
The goal of this thesis is to develop a new index that will support approximate and exact search, and progressive query answering with probability guarantees. The first step in this direction was to thoroughly assess the state-of-theart [17,18]. We describe the lessons learned from two extensive experimental evaluations and outline our future work.