publication . Preprint . 2016

Approximate Nearest Neighbor Search on High Dimensional Data --- Experiments, Analyses, and Improvement (v1.0)

Li, Wen; Zhang, Ying; Sun, Yifang; Wang, Wei; Zhang, Wenjie; Lin, Xuemin;
Open Access English
  • Published: 07 Oct 2016
Abstract
Comment: All source codes of the algorithms evaluated are available at https://github.com/DBWangGroupUNSW/nns_benchmark. arXiv admin note: text overlap with arXiv:1506.03163 by other authors
Subjects
free text keywords: Computer Science - Databases
Download from
78 references, page 1 of 6

Index Scalabiliity Datasize Dim =4th =1st =4th 4th =4th =1st 7th 3rd =2nd 7th 1st =5th =2nd =5th Search Scalabiliity Datasize Dim =1st 5th =1st 4th =1st 7th 6th =2nd =1st 6th 5th =2nd 7th 1st

[1] L. Amsaleg, O. Chelly, T. Furon, S. Girard, M. E. Houle, K. Kawarabayashi, and M. Nett. Estimating local intrinsic dimensionality. In SIGKDD, 2015.

[2] A. Andoni, P. Indyk, T. Laarhoven, I. P. Razenshteyn, and L. Schmidt. Practical and optimal LSH for angular distance. CoRR, abs/1509.02897, 2015. [OpenAIRE]

[3] A. Andoni and I. Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In STOC, 2015. [OpenAIRE]

[4] F. Andr´e, A. Kermarrec, and N. L. Scouarnec. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. PVLDB, 9(4):288-299, 2015.

[5] K. Aoyama, K. Saito, H. Sawada, and N. Ueda. Fast approximate similarity search based on degree-reduced neighborhood graphs. In SIGKDD, 2011.

[6] A. Babenko and V. S. Lempitsky. The inverted multi-index. In CVPR, pages 3069-3076, 2012.

[7] E. Bernhardsson. Annoy at github https://github.com/spotify/annoy, 2015.

[8] E. Bernhardsson. Benchmarking nearest neighbors https://github.com/erikbern/ann-benchmarks, 2016.

[9] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In ICML, pages 97-104, 2006. [OpenAIRE]

[10] L. Boytsov and B. Naidan. Learning to prune in metric and non-metric spaces. In NIPS, 2013.

[11] S. Brin. Near neighbor search in large metric spaces. In VLDB, pages 574-584, 1995.

[12] R. Caruana, N. Karampatziakis, and A. Yessenalina. An empirical evaluation of supervised learning in high dimensions. In ICML, pages 96-103, 2008.

[13] S. Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. In STOC, 2008.

[14] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG, 2004. [OpenAIRE]

78 references, page 1 of 6
Abstract
Comment: All source codes of the algorithms evaluated are available at https://github.com/DBWangGroupUNSW/nns_benchmark. arXiv admin note: text overlap with arXiv:1506.03163 by other authors
Subjects
free text keywords: Computer Science - Databases
Download from
78 references, page 1 of 6

Index Scalabiliity Datasize Dim =4th =1st =4th 4th =4th =1st 7th 3rd =2nd 7th 1st =5th =2nd =5th Search Scalabiliity Datasize Dim =1st 5th =1st 4th =1st 7th 6th =2nd =1st 6th 5th =2nd 7th 1st

[1] L. Amsaleg, O. Chelly, T. Furon, S. Girard, M. E. Houle, K. Kawarabayashi, and M. Nett. Estimating local intrinsic dimensionality. In SIGKDD, 2015.

[2] A. Andoni, P. Indyk, T. Laarhoven, I. P. Razenshteyn, and L. Schmidt. Practical and optimal LSH for angular distance. CoRR, abs/1509.02897, 2015. [OpenAIRE]

[3] A. Andoni and I. Razenshteyn. Optimal data-dependent hashing for approximate near neighbors. In STOC, 2015. [OpenAIRE]

[4] F. Andr´e, A. Kermarrec, and N. L. Scouarnec. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. PVLDB, 9(4):288-299, 2015.

[5] K. Aoyama, K. Saito, H. Sawada, and N. Ueda. Fast approximate similarity search based on degree-reduced neighborhood graphs. In SIGKDD, 2011.

[6] A. Babenko and V. S. Lempitsky. The inverted multi-index. In CVPR, pages 3069-3076, 2012.

[7] E. Bernhardsson. Annoy at github https://github.com/spotify/annoy, 2015.

[8] E. Bernhardsson. Benchmarking nearest neighbors https://github.com/erikbern/ann-benchmarks, 2016.

[9] A. Beygelzimer, S. Kakade, and J. Langford. Cover trees for nearest neighbor. In ICML, pages 97-104, 2006. [OpenAIRE]

[10] L. Boytsov and B. Naidan. Learning to prune in metric and non-metric spaces. In NIPS, 2013.

[11] S. Brin. Near neighbor search in large metric spaces. In VLDB, pages 574-584, 1995.

[12] R. Caruana, N. Karampatziakis, and A. Yessenalina. An empirical evaluation of supervised learning in high dimensions. In ICML, pages 96-103, 2008.

[13] S. Dasgupta and Y. Freund. Random projection trees and low dimensional manifolds. In STOC, 2008.

[14] M. Datar, N. Immorlica, P. Indyk, and V. S. Mirrokni. Locality-sensitive hashing scheme based on p-stable distributions. In SoCG, 2004. [OpenAIRE]

78 references, page 1 of 6
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue