More Web Proxy on the site http://driver.im/

research-article

Open access

FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search

Authors:

Wei-Cheng Chang,

Inderjit Dhillon,

Cho-Jui HsiehAuthors Info & Claims

WWW '23: Proceedings of the ACM Web Conference 2023

Pages 3225 - 3235

https://doi.org/10.1145/3543507.3583318

Published: 30 April 2023 Publication History

All formats PDF

Abstract

Approximate K-Nearest Neighbor Search (AKNNS) has now become ubiquitous in modern applications, such as a fast search procedure with two-tower deep learning models. Graph-based methods for AKNNS in particular have received great attention due to their superior performance. These methods rely on greedy graph search to traverse the data points as embedding vectors in a database. Under this greedy search scheme, we make a key observation: many distance computations do not influence search updates so that these computations can be approximated without hurting performance. As a result, we propose FINGER, a fast inference method for efficient graph search in AKNNS. FINGER approximates the distance function by estimating angles between neighboring residual vectors. The approximated distance can be used to bypass unnecessary computations for faster searches. Empirically, when it comes to speeding up the inference of HNSW, which is one of the most popular graph-based AKNNS methods, FINGER significantly outperforms existing acceleration approaches and conventional libraries by 20 to 60 across different benchmark datasets.

References

[1]

2019. IEEE Standard for Floating-Point Arithmetic. IEEE Std 754-2019 (Revision of IEEE 754-2008) (2019), 1–84. https://doi.org/10.1109/IEEESTD.2019.8766229

[2]

Sunil Arya and David M Mount. 1993. Approximate nearest neighbor queries in fixed dimensions. In SODA, Vol. 93. Citeseer, 271–280.

[3]

Martin Aumüller, Erik Bernhardsson, and Alexander Faithfull. 2020. ANN-Benchmarks: A benchmarking tool for approximate nearest neighbor algorithms. Information Systems 87 (2020), 101374.

Digital Library

[4]

Franz Aurenhammer. 1991. Voronoi diagrams—a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR) 23, 3 (1991), 345–405.

Digital Library

[5]

Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, and Bernhard Seeger. 1990. The R*-tree: An efficient and robust access method for points and rectangles. In SIGMOD. 322–331.

[6]

Christopher M Bishop. 2006. Pattern recognition. Machine learning 128, 9 (2006).

[7]

Deng Cai. 2019. A revisit of hashing algorithms for approximate nearest neighbor search. IEEE Transactions on Knowledge and Data Engineering (2019).

[8]

Moses S Charikar. 2002. Similarity estimation techniques from rounding algorithms. In STOC. 380–388.

[9]

Patrick H Chen, Si Si, Sanjiv Kumar, Yang Li, and Cho-Jui Hsieh. 2019. Learning to screen for fast softmax inference on large vocabulary neural networks. In ICLR.

[10]

Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zhiyong Zheng, Mao Yang, and Jingdong Wang. 2021. SPANN: Highly-efficient Billion-scale Approximate Nearest Neighborhood Search. NeurIPS 34 (2021).

[11]

DW Dearholt, N Gonzales, and G Kurup. 1988. Monotonic search networks for computer vision databases. In Twenty-Second Asilomar Conference on Signals, Systems and Computers, Vol. 2. IEEE, 548–553.

[12]

Qin Ding, Hsiang-Fu Yu, and Cho-Jui Hsieh. 2019. A fast sampling algorithm for maximum inner product search. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 3004–3012.

[13]

Wei Dong, Charikar Moses, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In WWW. 577–586.

[14]

Matthijs Douze, Alexandre Sablayrolles, and Hervé Jégou. 2018. Link and code: Fast indexing with graphs and compact regression codes. In CVPR. 3646–3654.

[15]

Casper Benjamin Freksen. 2021. An Introduction to Johnson-Lindenstrauss Transforms. arXiv preprint arXiv:2103.00564 (2021).

[16]

Cong Fu and Deng Cai. 2016. EFANNA: An extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv preprint arXiv:1609.07228 (2016).

[17]

Cong Fu, Changxu Wang, and Deng Cai. 2021. High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility. IEEE Trans. Pattern Anal. Mach. Intell. PP (March 2021).

Digital Library

[18]

Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2017. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. (July 2017). arxiv:cs.LG/1707.00143

[19]

Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2013. Optimized product quantization. IEEE TPAMI 36, 4 (2013), 744–755.

Digital Library

[20]

Aristides Gionis, Piotr Indyk, Rajeev Motwani, 1999. Similarity search in high dimensions via hashing. In VLDB, Vol. 99. 518–529.

[21]

Michel X Goemans and David P Williamson. 1995. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. Journal of the ACM (JACM) 42, 6 (1995), 1115–1145.

Digital Library

[22]

Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. 2020. Accelerating large-scale inference with anisotropic vector quantization. In ICML. PMLR, 3887–3896.

[23]

Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In Twenty-Second International Joint Conference on Artificial Intelligence.

[24]

Ben Harwood and Tom Drummond. 2016. FANNG: Fast approximate nearest neighbour graphs. In CVPR. 5713–5722.

[25]

Kaiming He, Fang Wen, and Jian Sun. 2013. K-means hashing: An affinity-preserving quantization method for learning binary compact codes. In CVPR.

[26]

Piotr Indyk and Rajeev Motwani. 1998. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC. 604–613.

[27]

Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krishnawamy, and Rohan Kadekodi. 2019. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. NeurIPS 32 (2019).

[28]

Herve Jegou, Matthijs Douze, and Cordelia Schmid. 2010. Product quantization for nearest neighbor search. IEEE TPAMI 33, 1 (2010), 117–128.

Digital Library

[29]

Zhongming Jin, Debing Zhang, Yao Hu, Shiding Lin, Deng Cai, and Xiaofei He. 2014. Fast and accurate hashing via iterative nearest neighbors expansion. IEEE transactions on cybernetics 44, 11 (2014), 2167–2177.

[30]

Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with gpus. IEEE Transactions on Big Data 7, 3 (2019), 535–547.

[31]

Maximilian Lam. 2018. Word2Bits - Quantized Word Vectors. arXiv preprint arXiv:1803.05651 (2018).

[32]

Der-Tsai Lee and Bruce J Schachter. 1980. Two algorithms for constructing a Delaunay triangulation. International Journal of Computer & Information Sciences 9, 3 (1980), 219–242.

[33]

Conglong Li, Minjia Zhang, David G Andersen, and Yuxiong He. 2020. Improving approximate nearest neighbor search through learned adaptive early termination. In SIGMOD. 2539–2554.

[34]

Xiaoyun Li and Ping Li. 2019. Random projections with asymmetric quantization. NeurIPS 32 (2019).

[35]

Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE TPAMI 42, 4 (2018), 824–836.

Digital Library

[36]

Etienne Marcheret, Vaibhava Goel, and Peder A Olsen. 2009. Optimal quantization and bit allocation for compressing large discriminative feature space transforms. In 2009 IEEE Workshop on ASRU. IEEE, 64–69.

[37]

Julieta Martinez, Shobhit Zakhmi, Holger H Hoos, and James J Little. 2018. LSQ++: Lower running time and higher recall in multi-codebook quantization. In ECCV.

[38]

Yusuke Matsui, Yusuke Uchida, Hervé Jégou, and Shin’ichi Satoh. 2018. A survey of product quantization. ITE Transactions on Media Technology and Applications 6, 1 (2018), 2–10.

[39]

Stanislav Morozov and Artem Babenko. 2019. Unsupervised neural quantization for compressed-domain similarity search. In ICCV. 3036–3045.

[40]

Javier Vargas Munoz, Marcos A Gonçalves, Zanoni Dias, and Ricardo da S Torres. 2019. Hierarchical clustering-based graphs for large scale approximate nearest neighbor search. Pattern Recognition 96 (2019), 106970.

Digital Library

[41]

Tobias Plötz and Stefan Roth. 2018. Neural nearest neighbors networks. arXiv preprint arXiv:1810.12575 (2018).

[42]

Chanop Silpa-Anan and Richard Hartley. 2008. Optimised KD-trees for fast image descriptor matching. In CVPR. IEEE, 1–8.

[43]

Kohei Sugawara, Hayato Kobayashi, and Masajiro Iwasaki. 2016. On approximately searching for similar word embeddings. In ACL.

[44]

Hongya Wang, Zhizheng Wang, Wei Wang, Yingyuan Xiao, Zeng Zhao, and Kaixiang Yang. 2020. A Note on Graph-Based Nearest Neighbor Search. arXiv preprint arXiv:2012.11083 (2020).

[45]

Jun Wang, Sanjiv Kumar, and Shih-Fu Chang. 2010. Sequential projection learning for hashing with compact codes. (2010).

[46]

Xiang Wu, Ruiqi Guo, Ananda Theertha Suresh, Sanjiv Kumar, Daniel N Holtmann-Rice, David Simcha, and Felix Yu. 2017. Multiscale quantization for fast similarity search. NeurIPS 30 (2017), 5745–5755.

[47]

Xiaoliang Xu, Mengzhao Wang, Yuxiang Wang, and Dingcheng Ma. 2021. Two-stage routing with optimized guided search and greedy algorithm on proximity graph. Knowledge-Based Systems 229 (2021), 107305.

Digital Library

[48]

Hsiang-Fu Yu, Cho-Jui Hsieh, Qi Lei, and Inderjit S Dhillon. 2017. A greedy approach for budgeted maximum inner product search. Advances in neural information processing systems 30 (2017).

[49]

Hsiang-Fu Yu, Kai Zhong, and Inderjit S Dhillon. 2020. PECOS: Prediction for Enormous and Correlated Output Spaces. arXiv preprint arXiv:2010.05878 (2020).

[50]

Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. 2019. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR) 52, 1 (2019), 1–38.

Digital Library

Cited By

Hezel NBarthel KSchilling BSchall KJung K(2025)Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia DatasetsMultiMedia Modeling10.1007/978-981-96-2054-8_25(333-347)Online publication date: 3-Jan-2025
https://doi.org/10.1007/978-981-96-2054-8_25
Gao JLong C(2024)RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/36549702:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654970
Hezel NBarthel KSchall KJung KGurrin CKongkachandra RSchoeffmann KDang-Nguyen DRossetto LSatoh SZhou L(2024)An Exploration Graph with Continuous Refinement for Efficient Multimedia RetrievalProceedings of the 2024 International Conference on Multimedia Retrieval10.1145/3652583.3658117(657-665)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3652583.3658117
Show More Cited By

Index Terms

FINGER: Fast Inference for Graph-based Approximate Nearest Neighbor Search
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
  2. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
    2. Machine learning approaches
      1. Learning latent representations
2. Information systems
  1. World Wide Web
    1. Web applications
      1. Social networks

Recommendations

Efficient approximate nearest neighbor search with integrated binary codes
MM '11: Proceedings of the 19th ACM international conference on Multimedia

Nearest neighbor search in Euclidean space is a fundamental problem in multimedia retrieval. The difficulty of exact nearest neighbor search has led to approximate solutions that sacrifice precision for efficiency. Among such solutions, approaches that ...
A Fast Approximate Nearest Neighbor Search Algorithm in the Hamming Space

A fast approximate nearest neighbor search algorithm for the (binary) Hamming space is proposed. The proposed Error Weighted Hashing (EWH) algorithm is up to 20 times faster than the popular locality sensitive hashing (LSH) algorithm and works well even ...
Fast Instance Search Based on Approximate Bichromatic Reverse Nearest Neighbor Search
MM '14: Proceedings of the 22nd ACM international conference on Multimedia

In the TRECVID Instance Search (INS) task, it is known that use of BM25, which is an improvement of the TFIDF,greatly improves retrieval performance. Its calculation, however, requires tremendous amount of computational cost and this fact makes its use ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

WWW '23: Proceedings of the ACM Web Conference 2023

April 2023

4293 pages

ISBN:9781450394161

DOI:10.1145/3543507

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Sponsors

SIGWEB: ACM Special Interest Group on Hypertext, Hypermedia, and Web

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 April 2023

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

WWW '23

Sponsor:

SIGWEB

WWW '23: The ACM Web Conference 2023

April 30 - May 4, 2023

TX, Austin, USA

Acceptance Rates

Overall Acceptance Rate 1,899 of 8,196 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
1,895
Total Downloads

Downloads (Last 12 months)1,240
Downloads (Last 6 weeks)155

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hezel NBarthel KSchilling BSchall KJung K(2025)Dynamic Exploration Graph: A Novel Approach for Efficient Nearest Neighbor Search in Evolving Multimedia DatasetsMultiMedia Modeling10.1007/978-981-96-2054-8_25(333-347)Online publication date: 3-Jan-2025
https://doi.org/10.1007/978-981-96-2054-8_25
Gao JLong C(2024)RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor SearchProceedings of the ACM on Management of Data10.1145/36549702:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654970
Hezel NBarthel KSchall KJung KGurrin CKongkachandra RSchoeffmann KDang-Nguyen DRossetto LSatoh SZhou L(2024)An Exploration Graph with Continuous Refinement for Efficient Multimedia RetrievalProceedings of the 2024 International Conference on Multimedia Retrieval10.1145/3652583.3658117(657-665)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3652583.3658117
Rajendram Bashyam LKrestel R(2024)Advancing Automatic Subject Indexing: Combining Weak Supervision with Extreme Multi-label ClassificationNatural Scientific Language Processing and Research Knowledge Graphs10.1007/978-3-031-65794-8_14(214-223)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-65794-8_14
Iwabuchi KSteil TPriest BPearce RSanders G(2023)Towards A Massive-scale Distributed Neighborhood Graph ConstructionProceedings of the SC '23 Workshops of The International Conference on High Performance Computing, Network, Storage, and Analysis10.1145/3624062.3625132(730-738)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3624062.3625132

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents