Fast l(1)-norm nearest neighbor search using a simple variant of randomized partition tree

Abstract

For big data applications, randomized partition trees have recently been shown to be very effective in answering high dimensional nearest neighbor search queries with provable guarantee, when distances are measured using l(2) norm. Unfortunately, if distances are measured using l(1) norm, the same theoretical guarantee does not hold. In this paper, we show that a simple variant of randomized partition tree, which uses a different randomization using 1-stable distribution, can be used to efficiently answer high dimensional nearest neighbors queries when distances are measured using l(1) norm. Experimental evaluations on eight real datasets suggest that the proposed method achieves better l(i)-norm nearest neighbor search accuracy with fewer retrieved data points as compared to locality sensitive hashing.