Pruning Algorithms For Low-dimensional Non-metric K-nn Search: A Case Study

Abstract

We focus on low-dimensional non-metric search, where tree-based approaches permit efficient and accurate retrieval while having short indexing time. These methods rely on space partitioning and require a pruning rule to avoid visiting unpromising parts. We consider two known data-driven approaches to extend these rules to non-metric spaces: TriGen and a piece-wise linear approximation of the pruning rule. We propose and evaluate two adaptations of TriGen to non-symmetric similarities (TriGen does not support non-symmetric distances). We also evaluate a hybrid of TriGen and the piece-wise linear approximation pruning. We find that this hybrid approach is often more effective than either of the pruning rules. We make our software publicly available.

Stats

• citations1
• S2 citations—
• github stars0
• HF likes0
• heat score2.26
• arxiv keyboytsov2019pruning

Related papers

• Accurate And Fast Retrieval For Complex Non-metric Data Via Neighborhood Graphs (2019)0.00
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• Hd-index: Pushing The Scalability-accuracy Boundary For Approximate Knn Search In High-dimensional Spaces (2018)14.02
• A Scalable Solution To The Nearest Neighbor Search Problem Through Local-search Methods On Neighbor Graphs (2017)3.58
• Exact Trajectory Similarity Search With N-tree: An Efficient Metric Index For Knn And Range Queries (2024)0.00
• Sparse Neighborhood Graph-based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis And Optimization (2025)0.00
• Efficient Autotuning Of Hyperparameters In Approximate Nearest Neighbor Search (2018)6.77
• Optimization Of Indexing Based On K-nearest Neighbor Graph For Proximity Search In High-dimensional Data (2018)0.00