Dumpyos: A Data-adaptive Multi-ary Index For Scalable Data Series Similarity Search

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

Stats

• citations4
• S2 citations—
• github stars0
• HF likes0
• heat score5.24
• arxiv keywang2024dumpyos

Related papers

• Return Of The Lernaean Hydra: Experimental Evaluation Of Data Series Approximate Similarity Search (2020)0.00
• Climber++: Pivot-based Approximate Similarity Search Over Big Data Series (2024)2.26
• The Lernaean Hydra Of Data Series Similarity Search: An Experimental Evaluation Of The State Of The Art (2020)0.00
• Indexing Metric Spaces For Exact Similarity Search (2020)10.85
• Scalable Similarity Search For Molecular Descriptors (2016)0.00
• Scalable Overload-aware Graph-based Index Construction For 10-billion-scale Vector Similarity Search (2025)4.52
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• Starling: An I/o-efficient Disk-resident Graph Index Framework For High-dimensional Vector Similarity Search On Data Segment (2024)12.61