Timezone: »

Learning to Prune in Metric and Non-Metric Spaces
Leonid Boytsov · Bilegsaikhan Naidan

Thu Dec 05 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor #None

To the best of our knowledge, this work is the first successful attempt to employ a VP-tree with the learned pruning algorithm in non-metric spaces. We focus on approximate nearest neighbor (NN) retrieval methods and experiment with 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 a metric (the Euclidean) and a non-metric (the KL-divergence) distance functions. 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 outperformed them in most cases by a wide margin. Our experiments also showed that the bbtree (an exact search method) was typically slower than exhaustive searching, if the KL-divergence was evaluated efficiently (through precomputing logarithms at index time). Conditions on spaces where the VP-tree is applicable are discussed.

Author Information

Leo Boytsov (Bosch Center for AI)
Bilegsaikhan Naidan (Norwegian University of Science and Technology (NTNU))