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

Loading...
Thumbnail Image
Issue Date
2015-08-08
Authors
Sinha, Kaushik
Advisor
Citation

Sinha, Kaushik. 2015. Fast l(1)-norm nearest neighbor search using a simple variant of randomized partition tree. Procedia Computer Science, vol. 53:pp 64–73, INNS Conference on Big Data 2015 Program San Francisco, CA, USA 8-10 August 2015

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.

Table of Content
Description
Open Access article. Under a Creative Commons License.
publication.page.dc.relation.uri