Pros: Data Series Progressive K-nn Similarity Search And Classification With Probabilistic Quality Guarantees

Abstract

Existing systems dealing with the increasing volume of data series cannot guarantee interactive response times, even for fundamental tasks such as similarity search. Therefore, it is necessary to develop analytic approaches that support exploration and decision making by providing progressive results, before the final and exact ones have been computed. Prior works lack both efficiency and accuracy when applied to large-scale data series collections. We present and experimentally evaluate ProS, a new probabilistic learning-based method that provides quality guarantees for progressive Nearest Neighbor (NN) query answering. We develop our method for k-NN queries and demonstrate how it can be applied with the two most popular distance measures, namely, Euclidean and Dynamic Time Warping (DTW). We provide both initial and progressive estimates of the final answer that are getting better during the similarity search, as well suitable stopping criteria for the progressive queries. Moreover, w

Stats

• citations10
• S2 citations—
• github stars0
• HF likes0
• heat score7.81
• arxiv keyechihabi2022pros

Related papers

• Let Them Have CAKES: A Cutting-edge Algorithm For Scalable, Efficient, And Exact Search On Big Data (2023)2.68
• 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
• Leveraging Reinforcement Learning For Evaluating Robustness Of KNN Search Algorithms (2021)0.00
• Approximate Nearest Neighbour Search On Dynamic Datasets: An Investigation (2024)0.00
• High-dimensional Approximate Nearest Neighbor Search: With Reliable And Efficient Distance Comparison Operations (2023)13.44
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• Pruning Algorithms For Low-dimensional Non-metric K-nn Search: A Case Study (2019)2.26