Timezone: »

 
Poster
Which Space Partitioning Tree to Use for Search?
Parikshit Ram · Alexander Gray

Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
in Poster Session »

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.

[ PDF] 

Author Information

Parikshit Ram (IBM Research AI)
Alexander Gray (Skytree Inc. and Georgia Tech)

More from the Same Authors