Learning to Prune in Metric and Non-Metric Spaces
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-toprune 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.
Summary: The paper presents a method that learns a 
      pruning algorithm for a VP-tree, in non-metric spaces. The idea is to 
      estimate the decision function of the approximate nearest neighbor search 
      in the VP-tree by sampling, and approximating it with a piecewise linear 
      function. The learning to prune method is validated for the search 
      efficiency against relevant baselines for prunning, and outperforms them 
      substantially when the intrinsic dimensionality of the data is small. 
      Clarity: The paper is mostly clearly written but sometimes does 
      not really go into explaining the implementation details and the choice of 
      some parameters (for example, why choose K=100, m=7, rho=8 and the bucket 
      size = 10^5? Line 185,227,315) Originality: Learning to 
      approximate the approximate nearest neighbor classification on a VP-tree, 
      to the extent of my knowledge, is the first work that 'learns to prune' 
      Significance: Nearest neighbor method is a very fundamental topic 
      in search or classification; thus this learning-to-prune method which 
      approximates the nearest neighbor search with a non-linear function would 
      be of some interest to a wide audience. However, the datasets 
      chosen for validation for the experiments seem rather simple and have 
      low-dimensionality, which are far from realistic. (What is the result on 
      the RCV-256, and SIFT for L2?) Also, whether the proposed method can 
      achieve the desired the speed-up is not well justified for the metric 
      space, which limits its application. For fast search in the metric space, 
      there are existing methods that utilize LSH and embeddings. One relevant 
      paper is as follows: [31] P. Jain, B. Kulis, K. Grauman, Fast Image Search 
      for Learned Metrics, CVPR 2008.