Proceedings

A Unified Approximate Nearest Neighbor Search Scheme by Combining Data Structure and Hashing

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 681-687.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

Nowadays, Nearest Neighbor Search becomes more and more important when facing the challenge of big data. Traditionally, to solve this problem, researchers mainly focus on building effective data structures such as hierarchical k-means tree or using hashing methods to accelerate the query process. In this paper, we propose a novel unified approximate nearest neighbor search scheme to combine the advantages of both the effective data structure and the fast Hamming distance computation in hashing methods. In this way, the searching procedure can be further accelerated. Computational complexity analysis and extensive experiments have demonstrated the effectiveness of our proposed scheme.

  1. [Andoni and Indyk, 2008] Alexandr Andoni and Piotr Indyk. Near-optimal hashing algorithms for approximate near- est neighbor in high dimensions. Communications of the ACM, 51(1):117-122, 2008.
  2. [Cheung and Fu, 1998] King Lum Cheung and Ada Wai- Chee Fu. Enhanced nearest neighbour search on the r-tree. ACM SIGMOD Record, 27(3):16-21, 1998.
  3. [Friedman et al., 1977] Jerome H. Friedman, Jon Louis Bentley, and Raphael Ari Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Transac- tions on Mathematical Software, 3(3):209-226, 1977.
  4. [Gionis et al., 1999] Aristides Gionis, Piotr Indyk, and Ra- jeev Motwani. Similarity search in high dimensions via hashing. In Proceedings of the 25th International Confer- ence on Very Large Data Bases, 1999.
  5. [Gong and Lazebnik, 2011] Yunchao Gong and S. Lazebnik. Iterative quantization: A procrustean approach to learning binary codes. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2011.
  6. [Hajebi et al., 2011] Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Proceedings of the Twenty-Second international joint con- ference on Artificial Intelligence, 2011. IJCAI
  7. [Heo et al., 2012] Jae-Pil Heo, YoungWoon Lee, Junfeng He, Shih-Fu Chang, and Sung eui Yoon. Spherical hash- ing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2012.
  8. [Joly and Buisson, 2011] Alexis Joly and Olivier Buisson. Random maximum margin hashing. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recog- nition, 2011.
  9. [Jun Wang, 2010] Shih-Fu Chang Jun Wang, Sanjiv Kumar. Sequential projection learning for hashing with compact codes. In Proceedings of the International Conference on Machine Learning, 2010.
  10. [Kulis and Grauman, 2009] Brian Kulis and Kristen Grau- man. Kernelized locality-sensitive hashing for scalable image search. In IEEE International Conference on Com- puter Vision, 2009.
  11. [Liu et al., 2012] Wei Liu, Jun Wang, Rongrong Ji, Yu-Gang Jiang, and Shih-Fu Chang. Supervised hashing with ker- nels. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2012.
  12. [Lowe, 2004] David G. Lowe. Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision, 60(2):91-110, 2004.
  13. [Me et al., 2011] Wei Me, Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. Hashing with graphs. In Proceedings of the International Conference on Machine Learning, 2011.
  14. [Muja and Lowe, 2009] Marius Muja and David G. Lowe. Fast approximate nearest neighbors with automatic algo- rithm configuration. In In VISAPP International Confer- ence on Computer Vision Theory and Applications, 2009.
  15. [Nister and Stewenius, 2006] David Nister and Henrik Stewenius. Scalable recognition with a vocabulary tree. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006.
  16. [Norouzi et al., 2012] Mohammad Norouzi, Ali Punjani, and David J. Fleet. Fast search in hamming space with multi- index hashing. In Proceedings of the IEEE Computer So- ciety Conference on Computer Vision and Pattern Recog- nition, 2012.
  17. [Paredes and Chávez, 2005] Rodrigo Paredes and Edgar Chávez. Using the k-nearest neighbor graph for proximity searching in metric spaces. In Proceedings of the inter- national conference on String Processing and Information Retrieval, 2005.
  18. [Raginsky and Lazebnik, 2009] Maxim Raginsky and Svet- lana Lazebnik. Locality-sensitive binary codes from shift- invariant kernels. In Advances in Neural Information Pro- cessing Systems. 2009.
  19. [Sengupta, 2012] Sunando Sengupta. Efficient discrimina- tive learning of parametric nearest neighbor classifiers. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2012.
  20. [Shindler et al., 2011] Michael Shindler, Alex Wong, and Adam W. Meyerson. Fast and accurate k-means for large datasets. In Advances in Neural Information Processing Systems 24. 2011.
  21. [Silpa-Anan and Hartley, 2008] Chanop Silpa-Anan and Richard Hartley. Optimised kd-trees for fast image de- scriptor matching. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2008.
  22. [Song et al., 2011] Jingkuan Song, Yi Yang, Zi Huang, Heng Tao Shen, and Richang Hong. Multiple feature hash- ing for real-time large scale near-duplicate video retrieval. In Proceedings of the ACM international conference on Multimedia, 2011.
  23. [Wang et al., 2012] Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. Semi-supervised hashing for large-scale search. IEEE Transactions on Pattern Analysis and Machine In- telligence, 34(12):2393-2406, 2012.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards