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

research-article

HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search

Authors:

Yoshiharu IshikawaAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 15, Issue 2

Pages 246 - 258

https://doi.org/10.14778/3489496.3489506

Published: 01 October 2021 Publication History

Abstract

Approximate nearest neighbor search (ANNS) is a fundamental problem that has a wide range of applications in information retrieval and data mining. Among state-of-the-art in-memory ANNS methods, graph-based methods have attracted particular interest owing to their superior efficiency and query accuracy. Most of these methods focus on the selection of edges to shorten the search path, but do not pay much attention to the computational cost at each hop. To reduce the cost, we propose a novel graph structure called HVS. HVS has a hierarchical structure of multiple layers that corresponds to a series of subspace divisions in a coarse-to-fine manner. In addition, we utilize a virtual Voronoi diagram in each layer to accelerate the search. By traversing Voronoi cells, HVS can reach the nearest neighbors of a given query efficiently, resulting in a reduction in the total search cost. Experiments confirm that HVS is superior to other state-of-the-art graph-based methods.

References

[1]

Walid G. Aref, Ann Christine Catlin, Jianping Fan, Ahmed K. Elmagarmid, Moustafa A. Hammad, Ihab F. Ilyas, Mirette S. Marzouk, and Xingquan Zhu. 2002. A Video Database Management System for Advancing Video Database Research. In Multimedia Information Systems. 8--17.

[2]

Sunil Arya and David M. Mount. 1993. Approximate Nearest Neighbor Queries in Fixed Dimensions. In SODA. 271--280.

Digital Library

[3]

Olivier Bachem, Mario Lucic, and Andreas Krause. 2018. Scalable k -Means Clustering via Lightweight Coresets. In KDD. 1119--1127.

Digital Library

[4]

Dmitry Baranchuk, Dmitry Persiyanov, Anton Sinitsin, and Artem Babenko. 2019. Learning to Route in Similarity Graphs. In ICML. 475--484.

[5]

Gérard Biau and Luc Devroye. 2015. Lectures on the Nearest Neighbor Method. (2015), 28--38.

Digital Library

[6]

Brankica Bratic, Michael E. Houle, Vladimir Kurbalija, Vincent Oria, and Milos Radovanovic. 2018. NN-Descent on High-Dimensional Data. In WIMS. 1--8.

Digital Library

[7]

Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. 2018. SPTAG: A library for fast approximate nearest neighbor search. https://github.com/Microsoft/SPTAG

[8]

D. Dearholt, N. Gonzales, and G. Kurup. 1988. Monotonic search networks for computer vision databases. Signals, Systems and Computers 2 (1988), 548--553.

[9]

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

Digital Library

[10]

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

[11]

Karima Echihabi, Kostas Zoumpatianos, Themis Palpanas, and Houda Benbrahim. 2019. Return of the Lernaean Hydra: Experimental Evaluation of Data Series Approximate Similarity Search. PVLDB 13, 3 (2019), 403--420.

Digital Library

[12]

Cong Fu and Deng Cai. 2016. Efanna: An extremely fast approximate nearest neighbor search algorithm based on knn graph. In arXiv:1609.07228.

[13]

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 (2021).

[14]

Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. 2019. Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. PVLDB 12, 5 (2019), 461--474.

Digital Library

[15]

Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized Product Quantization. IEEE Trans. Pattern Anal. Mach. Intell 36, 4 (2014), 744--755.

Digital Library

[16]

Rachid Guerraoui, Anne-Marie Kermarrec, Olivier Ruas, and François Taïani. 2020. Smaller, Faster & Lighter KNN Graph Constructions. In WWW. 1060--1070.

Digital Library

[17]

Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast Approximate Nearest-Neighbor Search with k-Nearest Neighbor Graph. In IJCAI. 1312--1317.

Digital Library

[18]

Ben Harwood and Tom Drummond. 2016. FANNG: Fast Approximate Nearest Neighbour Graphs. In CVPR. 5713--5722.

[19]

Qiang Huang, Jianlin Feng, Qiong Fang, Wilfred Ng, and Wei Wang. 2017. Query-aware locality-sensitive hashing scheme for lp norm. VLDB J. 26, 5 (2017), 683--708.

Digital Library

[20]

Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 2011. Product Quantization for Nearest Neighbor Search. IEEE Trans. Pattern Anal. Mach. Intell 33, 1 (2011), 117--128.

Digital Library

[21]

Zhongming Jin, Debing Zhang, Yao Hu, Shiding Lin, Deng Cai, and Xiaofei He. 2014. Fast and Accurate Hashing Via Iterative Nearest Neighbors Expansion. IEEE Trans. Cybern 44, 11 (2014), 2016--2177.

[22]

Yan Ke, Rahul Sukthankar, and Larry Huston. 2004. An efficient parts-based near-duplicate and sub-image retrieval system. In ACM Multimedia. 869--876.

Digital Library

[23]

Yifan Lei, Qiang Huang, Mohan S. Kankanhalli, and Anthony K. H. Tung. 2020. Locality-Sensitive Hashing Scheme based on Longest Circular Co-Substring. In SIGMOD. 2589--2599.

Digital Library

[24]

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.

Digital Library

[25]

Wen Li, Ying Zhang, Yifang Sun, Wei Wang, Mingjie Li, Wenjie Zhang, and Xuemin Lin. 2020. Approximate Nearest Neighbor Search on High Dimensional Data - Experiments, Analyses, and Improvement. IEEE Trans. Knowl. Data Eng 32, 8 (2020), 1475--1488.

[26]

Jie Liu, Xiao Yan, Xinyan Dai, Zhirong Li, James Cheng, and Ming-Chang Yang. 2020. Understanding and Improving Proximity Graph based Maximum Inner Product Search. In AAAI. 139--146.

[27]

Kejing Lu and Mineichi Kudo. 2020. R2LSH: A Nearest Neighbor Search Scheme Based on Two-dimensional Projected Spaces. In ICDE. 1045--1056.

[28]

Kejing Lu, Hongya Wang, Wei Wang, and Mineichi Kudo. 2020. VHP: Approximate Nearest Neighbor Search via Virtual Hypersphere Partitioning. In PVLDB. 1443--1455.

Digital Library

[29]

Yury Malkov, Alexander Ponomarenko, Andrey Logvinov, and Vladimir Krylov. 2014. Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems 45 (2014), 61--68.

[30]

Yury A. Malkov and D. A. Yashunin. 2020. Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs. IEEE Trans. Pattern Anal. Mach. Intell 42, 4 (2020), 824--836.

Digital Library

[31]

Marius Muja. 2019. https://github.com/flann-lib/flann.

[32]

Liudmila Prokhorenkova and Aleksandr Shekhovtsov. 2020. Graph-based Nearest Neighbor Search: From Practice to Theory. In ICML. 7803--7813.

[33]

Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, and Hervé Jégou. 2019. Spreading vectors for similarity search. In ICLR.

[34]

Yifang Sun, Wei Wang, Jianbin Qin, Ying Zhang, and Xuemin Lin. 2014. SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index. PVLDB 8, 1 (2014), 1--12.

Digital Library

[35]

Javier Vargas Muñoz, 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).

[36]

Minjia Zhang and Yuxiong He. 2019. GRIP: Multi-Store Capacity-Optimized High-Performance Nearest Neighbor Search for Vector Search Engine. In CIKM. 1673--1682.

Digital Library

[37]

Zhixin Zhou, Shulong Tan, Zhaozhuo Xu, and Ping Li. 2019. Mobius Transformation for Fast Inner Product Search on Graph. In NeurIPS. 8216--8227.

Digital Library

Cited By

Lu KXiao CIshikawa YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Probabilistic routing for graph-based approximate nearest neighbor searchProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693417(33177-33195)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693417
Chen MZhang KHe ZJing YWang X(2024)RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor SearchProceedings of the VLDB Endowment10.14778/3681954.368195917:11(2735-2749)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681959
Hu HQiu JWang HLiang BZou S(2024)DIDS: Double Indices and Double Summarizations for Fast Similarity SearchProceedings of the VLDB Endowment10.14778/3665844.366585117:9(2198-2211)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665851
Show More Cited By

Index Terms

HVS: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search
1. Information systems
  1. Information retrieval
  2. Information systems applications
2. Mathematics of computing
  1. Discrete mathematics

Index terms have been assigned to the content through auto-classification.

Recommendations

The Hierarchical Visualisation System (HVS)
IV '07: Proceedings of the 11th International Conference Information Visualization

Numerous techniques have been developed for visualising hierarchically structured information. This paper presents a new framework for the visualisation of hierarchies called the Hierarchical Visualisation System (HVS). HVS is a general framework ...
Multi-probe LSH: efficient indexing for high-dimensional similarity search
VLDB '07: Proceedings of the 33rd international conference on Very large data bases

Similarity indices for high-dimensional data are very desirable for building content-based search systems for feature-rich data such as audio, images, videos, and other sensor data. Recently, locality sensitive hashing (LSH) and its variations have been ...
K-Nearest Neighbor Finding Using MaxNearestDist

Similarity searching often reduces to finding the k nearest neighbors to a query object. Finding the k nearest neighbors is achieved by applying either a depth- first or a best-first algorithm to the search hierarchy containing the data. These ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 15, Issue 2

October 2021

247 pages

ISSN:2150-8097

Editors:
Juliana Freire
New York University
,
Xuemin Lin
University of New South Wales

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 October 2021

Published in PVLDB Volume 15, Issue 2

Badges

Artifacts Available / v1.1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
269
Total Downloads

Downloads (Last 12 months)88
Downloads (Last 6 weeks)6

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lu KXiao CIshikawa YSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Probabilistic routing for graph-based approximate nearest neighbor searchProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3693417(33177-33195)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3693417
Chen MZhang KHe ZJing YWang X(2024)RoarGraph: A Projected Bipartite Graph for Efficient Cross-Modal Approximate Nearest Neighbor SearchProceedings of the VLDB Endowment10.14778/3681954.368195917:11(2735-2749)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681959
Hu HQiu JWang HLiang BZou S(2024)DIDS: Double Indices and Double Summarizations for Fast Similarity SearchProceedings of the VLDB Endowment10.14778/3665844.366585117:9(2198-2211)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.14778/3665844.3665851
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
Wang MXu WYi XWu SPeng ZKe XGao YXu XGuo RXie C(2024)Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data SegmentProceedings of the ACM on Management of Data10.1145/36392692:1(1-27)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639269
Manohar MShen ZBlelloch GDhulipala LGu YSimhadri HSun YLee IChabbi MSteuwer M(2024)ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search AlgorithmsProceedings of the 29th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming10.1145/3627535.3638475(270-285)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1145/3627535.3638475
Chen MLiu CLiang SHe LWang YZhang LLi HLi X(2024)An Energy-Efficient In-Memory Accelerator for Graph Construction and UpdatingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.335503843:6(1781-1793)Online publication date: 18-Jan-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3355038
Gao JLong C(2023)High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison OperationsProceedings of the ACM on Management of Data10.1145/35892821:2(1-27)Online publication date: 20-Jun-2023
https://dl.acm.org/doi/10.1145/3589282
Li WFeng CLian DXie YLiu HGe YChen ESingh ASun YAkoglu LGunopulos DYan XKumar ROzcan FYe J(2023)Learning Balanced Tree Indexes for Large-Scale Vector RetrievalProceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining10.1145/3580305.3599406(1353-1362)Online publication date: 6-Aug-2023
https://dl.acm.org/doi/10.1145/3580305.3599406
Lu KIshikawa YXiao C(2022)MQHProceedings of the VLDB Endowment10.14778/3574245.357426916:4(864-876)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574269
Show More Cited By

View Options

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents