Abstract | ||
---|---|---|
Our focus is on approximate nearest neighbor retrieval in metric and non-metric spaces. We employ a VP-tree and explore two simple yet effective learning-to prune approaches: density estimation through sampling and “stretching” of the triangle inequality. Both methods are evaluated using data sets with metric (Euclidean) and non-metric (KL-divergence and Itakura-Saito) distance functions. Conditions on spaces where the VP-tree is applicable are discussed. The VP-tree with a learned pruner is compared against the recently proposed state-of-the-art approaches: the bbtree, the multi-probe locality sensitive hashing (LSH), and permutation methods. Our method was competitive against state-of-the-art methods and, in most cases, was more efficient for the same rank approximation quality. |
Year | Venue | Field |
---|---|---|
2013 | NIPS | Locality-sensitive hashing,Equivalence of metrics,Computer science,M-tree,Metric tree,Convex metric space,Artificial intelligence,Triangle inequality,Metric space,Machine learning,Injective metric space |
DocType | Citations | PageRank |
Conference | 4 | 0.39 |
References | Authors | |
24 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Leonid Boytsov | 1 | 166 | 10.21 |
Bilegsaikhan Naidan | 2 | 28 | 3.32 |