DumpyOS: A Data-Adaptive Multi-ary Index for Scalable Data Series Similarity Search
Zeyu Wang, Qitong Wang, Peng Wang 🖂, Themis Palpanas, Wei Wang · 2024
Read DumpyOS: A Data-Adaptive Multi-ary Index for Scalable Data Series Similarity Search by Zeyu Wang, Qitong Wang, Peng Wang 🖂, Themis Palpanas, Wei Wang (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-09448.txt.
Introduction
Zeyu Wang and co-authors present a 2024 paper on searching data series at scale. Collections of time series keep growing, and indexes must answer likeness searches in milliseconds. Two leading index families trade off build time against search accuracy, and each leaves a weakness.
The team traces the weakness to fanout choices in the index tree and to skewed data spread. Their index, Dumpy, uses a multi-way tree with splits that adapt to the data. A fuzzy variant copies some series to lift accuracy further. The full system, DumpyOS, runs in parallel across cores and fast drives. Pruning search methods keep speed high while the fuzzy search lifts result quality.
Catalog record
| CREATOR | Zeyu Wang, Qitong Wang, Peng Wang 🖂, Themis Palpanas, Wei Wang |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 97 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-09448
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
DumpyOS: A Data-Adaptive Multi-ary Index for Scalable Data Series Similarity Search Zeyu Wang, Qitong Wang, Peng Wang 🖂, Themis Palpanas, Wei Wang Abstract Data series indexes are necessary for managing and analyzing the increasing amounts of data series collections that are nowadays available. These indexes support both exact and approximate similarity search, with approximate search providing high-quality results within milliseconds, which makes it very attractive for certain modern applications. Reducing the pre-processing (i.e., index building) time and improving the accuracy of search results are two major challenges. DSTree and the iSAX index family are state-of-the-art solutions for this problem. However, DSTree suffers from long index building times, while iSAX suffers from low search accuracy. In this paper, we identify two problems of the iSAX index family that adversely affect the overall performance. First, we observe the presence of a proximity-compactness trade-off related to the index structure design (i.e., the node fanout degree), significantly limiting the efficiency and accuracy of the resulting index. Second, a skewed data distribution will negatively affect the performance of iSAX. To overcome these problems, we propose Dumpy, an index that employs a novel multi-ary data structure with an adaptive node splitting algorithm and an efficient building workflow. Furthermore, we devise Dumpy-Fuzzy as a variant of Dumpy which further improves search accuracy by proper duplication of series. To fully leverage the potential of modern hardware including multicore CPUs and Solid State Drives (SSDs), we parallelize Dumpy to DumpyOS with sophisticated indexing and pruning-based querying algorithms. An optimized approximate search algorithm, DumpyOS-F that prominently improves the search accuracy without violating the index, is also proposed. Experiments with a variety of large, real datasets demonstrate that the Dumpy solutions achieve considerably better efficiency, scalability and search accuracy than its competitors. DumpyOS further improves on Dumpy, by delivering several times faster index building and querying, and DumpyOS-F improves the search accuracy of Dumpy-Fuzzy without the additional space cost of Dumpy-Fuzzy. This paper is an extension of the previously published SIGMOD paper [ 82 ] . ∎ 1 Introduction Massive data series collections are now being produced by applications across virtually every scientific and social domain [ 94 , 55 , 42 ] , making data series one of the most common data types. The problems of managing and analyzing large-volume data series have attracted the research interest of the data management community in the past three decades [ 56 , 11 ] . In this context, similarity search is an essential primitive operation, lying at the core of several other high-level algorithms, e.g., classification, clustering, motif discovery and outlier detection [ 55 , 58 , 71 , 13 , 14 , 77 ] . Similarity search aims to find the nearest neighbors in the dataset, given a query series and a distance measure. The naive solution is to sequentially calculate the distances of all series to the query series. However, sequential scan quickly becomes intractable as the dataset size increases. To facilitate similarity search at scale, a data series index can be used to prune irrelevant data and thus, reduce the effort required to answer the queries. Moreover, as researchers pay more attention to data exploration, the importance of approximate similarity search grows rapidly [ 29 , 30 ] . It is widely employed in real-world applications since it can provide high-quality approximate query results within the interactive response time, in the order of milliseconds [ 19 , 76 , 10 , 50 , 9 ] . In such applications, approximate query result quality is sufficient to support downstream applications [ 20 ] . Recent examples include 1) a k-nearest-neighbors (kNN) classifier [ 5 ] , whose accuracy converges to the best when kNN mean average precision (MAP) reaches 60%; 2) an outlier detector [ 67 ] that achieves the best ROC-AUC with 50% MAP; and 3) a kNN-based SoftMax approximation technique for large-scale classification, which achieves nearly the same accuracy as the exact SoftMax when kNN recall reaches 80% [ 88 ] . For these applications, the core requirements for the kNN-index are the query time under the above precision (should be in the order of milliseconds), the index building time, and the scalability to support large datasets. Although there are dozens of approaches in the literature that can index data series [ 30 ] , only a few of them can robustly support large data series collections, e.g., over 100GB (which is why techniques for approximate search [ 30 ] , as well as progressive search for exact [ 27 ] and approximate [ 40 ] query answering have been studied). Among them, DSTree [ 79 ] and the iSAX index family [ 57 ] show the best query performance on the approximate search and support exact search at the same time. Due to the dynamic segmentation technique, DSTree requires a long index building time (over one order of magnitude slower than iSAX) and is hard to optimize. On the contrary, benefiting from fast index building and rich optimizations [ 16 , 90 , 85 , 62 , 61 , 64 , 17 ] , the iSAX index family has become the most popular data series index in the past decade. Nonetheless, iSAX still suffers from unsatisfactory approximate search accuracy when visiting a small portion of data (one or several nodes, ensuring millisecond-level delay), e.g., its MAP is less than 10% when visiting one node while query time exceeds one second when improving MAP to \geq 50% [ 30 ] . In this work, we identify the intrinsic problem of the index structure and building workflow of the iSAX index family and propose our novel solution, Dumpy, to tackle those. First, we observe that the design of the index structure is an inherent but overlooked problem that significantly limits the performance of the iSAX index family. Although iSAX [ 69 ] does not in principle limit the fanout of a node, popular iSAX-family indexes [ 15 , 90 , 85 , 51 , 60 , 61 , 64 , 17 ] still adopt a binary structure (except for the first layer that has a full fanout). When a node contains more series than the leaf size threshold th , it selects one SAX segment and splits the node into two child nodes. However, under this binary structure, the splitting policies being used [ 69 , 15 ] often lead to sub-optimal decisions (cf. [ 87 ] , Section 4 ), that hurt the proximity (i.e., similarity) of series inside a node, and finally the quality of approximate query results. Recently, a full-ary SAX-based index has been proposed to tackle this problem [ 87 ] . A full-ary structure splits a full node on all segments, such that it avoids the problems of focusing on a single segment that leads to sub-optimal splitting decisions. However, it generates too many nodes (at most 2^{w} , w is the total number of segments) in each split, leading to an excessive number of leaf nodes, and hence extremely low leaf node fill factors. This leads to an underperforming (disk-resident) index, due to inefficient disk utilization and overwhelming disk accesses. Although subtrees in the index can be merged into larger partitions (e.g., 128MB)