a01a0380ca3c61428c26a231f0e49a09-Reviews.html

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"?