Pruning Algorithms for Low-Dimensional Non-metric k-NN Search: A Case Study
This work addresses incremental improvements in pruning algorithms for non-metric search, relevant for researchers and practitioners in information retrieval and machine learning.
The paper tackled the problem of efficient low-dimensional non-metric k-NN search by proposing adaptations of TriGen for non-symmetric similarities and evaluating a hybrid pruning approach, finding that the hybrid method often outperforms individual rules.
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.