Which Space Partitioning Tree to Use for Search?
We consider the task of nearest-neighbor search with the class of binary-spacepartitioning trees, which includes kd-trees, principal axis trees and random projection trees, and try to rigorously answer the question "which tree to use for nearestneighbor search?" To this end, we present the theoretical results which imply that trees with better vector quantization performance have better search performance guarantees. We also explore another factor affecting the search performancemargins of the partitions in these trees. We demonstrate, both theoretically and empirically, that large margin partitions can improve tree search performance.
The paper presents bounds on the search performance of 
      a simple, tree-based nearest neighbor search algorithm. The bounds 
      depend on the vector quantization performance on the tree. It is 
      argued that this result implies that trees with good vector 
      quantization performance are advantageous for nearest neighbor search. 
      The statement is extended to large margin splits. The title of 
      the paper asks "which space partitioning tree to use for search"? It 
      should better ask "which tree results in the strongest performance 
      guarantees"? The paper says almost nothing about practical 
      performance. This is mostly due to the choice of an artificially 
      simplified search procedure. More often than not, a better guarantee 
      is an artifact of a certain flavor of analysis or a proof technique, 
      since we are only talking about upper bounds. If the bounds are not 
      tight then the bounds say little about which tree to "use" (in 
      practice!). This paper makes the common mistake of confusing a better 
      performance guarantee with a guarantee for better performance. This 
      happens at several spots, e.g., first sentence of section 4. 
      Algorithm 1 is analyzed in depth. However, I am unsure how 
      relevant this algorithm is. It descends the tree without backtracking. 
      At the target depth l it performs exhaustive search. Although this is 
      not taken into account in the analysis, the final search can be 
      performed with efficient exact tree search, so, this time with 
      backtracking. This algorithm does not find the exact nearest 
      neighbor. The obvious alternative is to apply a heuristic for skipping 
      some of the branches on the fly. The decisive difference is that in 
      Algorithm 1 the decision which branches to traverse is not made in a 
      data dependent manner, but instead based on a pre-specified parameter. 
      This is why personally I would never use this algorithm. Since all 
      results are restricted to this algorithm I question the relevance of 
      this paper. I see that analyzing the computational complexity of a 
      method with backtracking is surely much harder. I argue that doing so 
      would be a prerequisite for understanding the behavior of realistic 
      algorithms. I cannot get rid of the impression that this analysis was 
      conducted simply because it is possible, and not because it is 
      relevant. The logic of the conclusion is as follows: Algorithm 
      1: good VQ performance => good search performance. Now Algorithm 1 
      is not a good search algorithm by itself. When using more elaborate 
      tree search procedures there remains little to nothing to conclude 
      from the present analysis. However, the title as well as other 
      statements in the paper (e.g., top of page 5) indicate that the 
      conclusion is rather general. I want to emphasize that this is not the 
      case, and thus this paper does NOT answer the question which search 
      tree to use for search in practice. I would appreciate the 
      result if it could help the analysis of more realistic search 
      procedures. However, I am not an expert on the analysis of tree search 
      and thus I cannot judge the present paper from this perspective. Also, 
      this paper does not claim to provide new methods for analysis, it is 
      all about the theorems. And this makes me question its value. 
      The empirical evaluation is weak. Only four data sets are used, 
      and they are even non-standard. E.g., why is MNIST sub-sampled to 6000 
      training and 1000 test samples? This is arbitrary, an no reason is 
      given. This does not help my trust in the evaluation. With low numbers 
      of training points there is no real need for tree search at all. I 
      see that the empirical results are nicely in line with the analysis. 
      However, how about computation time? E.g., a single decision in a 
      kd-tree is cheaper than in a PA-tree by a factor of O(dim(X)). The 
      added computation time could be used for backtracking, which could 
      well give the kd-tree an advantage. So once more, this analysis says 
      nothing about which tree to use for search with a better algorithm.