Which Space Partitioning Tree To Use For Search

Parikshit Ram, Alexander Gray. Neural Information Processing Systems 2013

[Paper]    
Independent NEURIPS Quantisation

We consider the task of nearest-neighbor search with the class of binary-space-partitioning trees, which includes kd-trees, principal axis trees and random projection trees, and try to rigorously answer the question which tree to use for nearest-neighbor 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 performance – margins of the partitions in these trees. We demonstrate, both theoretically and empirically, that large margin partitions can improve the search performance of a space-partitioning tree. “

Similar Work