Pruning Algorithms for Low-Dimensional Non-metric k-NN Search: A Case Study
Lists
Only you see this
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.
BibTeX
@inproceedings{boytsov2019pruning,
author = {Leonid Boytsov and Eric Nyberg},
title = {{Pruning Algorithms for Low-Dimensional Non-metric k-NN Search: A Case Study}},
booktitle = {SISAP},
year = {2019},
doi = {10.1007/978-3-030-32047-8\_7},
}Loading related content...