کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
484814 | 703295 | 2015 | 10 صفحه PDF | دانلود رایگان |
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 £2 norm. Unfortunately, if distances are measured using £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 £1 norm. Experimental evaluations on eight real datasets suggest that the proposed method achieves better £i-norm nearest neighbor search accuracy with fewer retrieved data points as compared to locality sensitive hashing.
Journal: Procedia Computer Science - Volume 53, 2015, Pages 64-73