基于容忍因子的近似最近邻混合查询算法

doi:10.11959/j.issn.2096-0271.2024010

大数据 ›› 2024, Vol. 10 ›› Issue (1): 17-34.doi: 10.11959/j.issn.2096-0271.2024010

• 研究 • 上一篇

基于容忍因子的近似最近邻混合查询算法

贺广福¹^,², 薛源海¹, 陈翠婷¹^,², 俞晓明¹^,², 刘欣然¹^,³, 程学旗¹^,²

¹ 中国科学院计算技术研究所，北京 100190
² 中国科学院大学，北京 101408
³ 北京邮电大学，北京 100876

出版日期:2024-01-01 发布日期:2024-01-01
作者简介:贺广福（1992- ），男，中国科学院大学博士生，中国科学院计算技术研究所工程师、中级软件设计师，主要研究方向为大数据、信息检索、自然语言处理。
薛源海（1987- ），男，博士，中国科学院计算技术研究所高级工程师，主要研究方向为信息检索。
陈翠婷（1991- ），女，中国科学院大学博士生，中国科学院计算技术研究所工程师，主要研究方向为人工智能、信息检索。
俞晓明（1977- ），男，博士，中国科学院计算技术研究所高级工程师，主要研究方向为信息检索、自然语言处理。
刘欣然（1971- ），男，博士，北京邮电大学研究员，主要研究方向为网络空间安全、大数据应用。
程学旗（1971- ），男，博士，中国科学院计算技术研究所研究员、副所长，主要研究方向为网络科学与社会计算、网络大数据。
基金资助:
国家自然科学基金项目(U21B2046)

Approximate nearest neighbor hybrid query algorithm based on tolerance factor

Guangfu HE¹^,², Yuanhai XUE¹, Cuiting CHEN¹^,², Xiaoming YU¹^,², Xinran LIU¹^,³, Xueqi CHENG¹^,²

¹ Institute of Computing Technology, Chinese Academy of Sciences, Beijing 100190, China
² University of Chinese Academy of Sciences, Beijing 101408, China
³ Beijing University of Posts and Telecommunications, Beijing 100876, China

Online:2024-01-01 Published:2024-01-01
Supported by:
The National Natural Science Foundation of China(U21B2046)

摘要/Abstract

摘要：

近似最近邻搜索（ANNS）是计算机领域中一种重要的高效相似度搜索技术，可用于在大规模数据集中进行快速信息检索。随着人们对高精度信息检索的需求不断增长，同时使用结构化信息和非结构化信息进行混合查询的方式也得到了广泛应用。然而，基于近邻图的过滤贪心算法在混合查询时可能会因结构化约束条件的影响导致连通性降低，进而损害搜索精度。为此，提出了一种基于容忍因子的过滤贪心算法，通过容忍因子控制不满足结构化约束条件的顶点参与路由，在不改变索引结构的前提下维持原有近邻图的连通性，克服了结构化约束条件对检索精度的负面影响。实验结果证明，新算法可以在不同结构化约束强度下实现ANNS的高精度搜索，同时保持检索效率。该研究解决了基于近邻图的ANNS在混合查询场景中的问题，为大规模数据集的快速混合查询信息检索提供了一种有效的解决方案。

关键词: 混合查询, 向量检索, 最近邻搜索, 过滤搜索

Abstract:

Approximate nearest neighbor search (ANNS) is an important technique in the field of computer science for efficient similarity search, enabling fast information retrieval in large-scale datasets.With the increasing demand for high-precision information retrieval, there is a growing use of the hybrid query method that utilizes both structured and unstructured information for querying, which has broad application prospects.However, filtered greedy algorithms based on nearest neighbor graphs may reduce the connectivity of the graph due to the impact of structural constraints in hybrid queries, ultimately damaging search accuracy.This article proposes a tolerance factor based filtered greedy algorithm, which controls the participation of vertices that do not meet structural constraints in routing through a tolerance factor, maintaining the connectivity of the original nearest neighbor graph without changing the index structure, and overcoming the negative impact of structural constraints on retrieval accuracy.The experimental results demonstrate that the new method can achieve high-precision search for ANNS under different levels of structural constraints, while maintaining retrieval efficiency.This study solves the problem of ANNS based on nearest neighbor graphs in hybrid query scenarios, providing an effective solution for fast hybrid query information retrieval in large-scale datasets.

Key words: hybrid query, vector search, nearest neighbor search, filtered search

中图分类号:

TP391.3，TP18

贺广福, 薛源海, 陈翠婷, 俞晓明, 刘欣然, 程学旗. 基于容忍因子的近似最近邻混合查询算法[J]. 大数据, 2024, 10(1): 17-34.

Guangfu HE, Yuanhai XUE, Cuiting CHEN, Xiaoming YU, Xinran LIU, Xueqi CHENG. Approximate nearest neighbor hybrid query algorithm based on tolerance factor[J]. Big Data Research, 2024, 10(1): 17-34.

图/表 10

图1

图2

图3

表1

表2

图4

图5

图6

图7

图8

参考文献 30

[1]	YANG F , HINAMI R , MATSUI Y ,et al. Efficient image retrieval via decoupling diffusion into online and offline processing[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2019,33(1): 9087-9094.
[2]	PHILBIN J , CHUM O , ISARD M ,et al. Object retrieval with large vocabularies and fast spatial matching[C]// Proceedings of 2007 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2007: 1-8.
[3]	SHANKAR D , NARUMANCHI S , ANANYA H A ,et al. Deep learning based large scale visual recommendation and search for E-commerce[EB]. arXiv preprint, 2017,arXiv:1703.02344.
[4]	CHEN R H , LIU B , ZHU H ,et al. Approximate nearest neighbor search under neural similarity metric for largescale recommendation[C]// Proceedings of the 31st ACM International Conference on Information ＆ Knowledge Management. New York:ACM, 2022: 3013-3022.
[5]	BERLIN K , KOREN S , CHIN C S ,et al. Assembling large genomes with singlemolecule sequencing and locality-sensitive hashing[J]. Nature Biotechnology, 2015,33(6): 623-630.
[6]	TOPSAKAL O , AKINCI T C . Creating large language model applications utilizing LangChain:a primer on developing LLM apps fast[J]. International Conference on Applied Engineering and Natural Sciences, 2023,1(1): 1050-1056.
[7]	AUMüLLER M , BERNHARDSSON E , FAITHFULL A . ANN-Benchmarks:a benchmarking tool for approximate nearest neighbor algorithms[J]. Information Systems, 2020,87:101374.
[8]	GOLLAPUDI S , KARIA N , SIVASHANKAR V ,et al. FilteredDiskANN:graph algorithms for approximate nearest neighbor search with filters[C]// Proceedings of the ACM Web Conference 2023. New York:ACM, 2023: 3406-3416.
[9]	WANG J G , YI X M , GUO R T ,et al. Milvus:a purpose-built vector data management system[C]// Proceedings of the 2021 International Conference on Management of Data. New York:ACM, 2021: 2614-2627.
[10]	VAN LUIJT B , VERHAGEN M . Bringing semantic knowledge graph technology to your data[J]. IEEE Software, 2020,37(2): 89-94.
[11]	LI J , LIU H F , GUI C H ,et al. The design and implementation of a real time visual search system on JD E-commerce platform[C]// Proceedings of the 19th International Middleware Conference Industry. New York:ACM, 2018: 9-16.
[12]	JOHNSON J , DOUZE M , JEGOU H . Billion-scale similarity search with GPUs[J]. IEEE Transactions on Big Data, 2021,7(3): 535-547.
[13]	PARK Y , PARK S , LEE S-G ,et al. Greedy filtering:a scalable algorithm for k-nearest neighbor graph construction[C]// Proceedings of the Database Systems for Advanced Applications:19th International Conference. Berlin:Springer, 2014: 327-41.
[14]	WANG M , LYU L , XU X ,et al. Navigable proximity graph-driven native hybrid queries with structured and unstructured constraints[EB]. arXiv preprint, 2022,arXiv:2203.13601.
[15]	JAYARAM SUBRAMANYA S , DEVVRIT F , SIMHADRI H V ,et al. Diskann:fast accurate billion-point nearest neighbor search on a single node[J]. Advances in Neural Information Processing Systems, 2019,32.
[16]	STREHL A , GHOSH J . Cluster ensembles:a knowledge reuse framework for combining multiple partitions[J]. Journal of Machine Learning Research, 2003,3: 583-617.
[17]	AGGARWAL C C . Data classification:algorithms and applications[M]. [S. l.]: CRC Press, 2014: 37-64.
[18]	XU X L , LI C , WANG Y X ,et al. Multiattribute approximate nearest neighbor search based on navigable small world graph[J]. Concurrency and Computation:Practice and Experience, 2020,32(24): e5970.
[19]	BECKMANN N , KRIEGEL H P , SCHNEIDER R ,et al. The R*-tree:an efficient and robust access method for points and rectangles[C]// Proceedings of the 1990 ACM SIGMOD International Conference on Management of Data. New York:ACM, 1990: 322-331.
[20]	MUNAGA H , JARUGUMALLI V . Performance evaluation:ball-tree and KDtree in the context of MST[C]// Proceedings of International Joint Conference on Advances in Signal Processing and Information Technology. Heidelberg:Springer, 2012: 225-228.
[21]	GREENSPAN M , YURICK M . Approximate k-d tree search for efficient ICP[C]// Proceedings of 4th International Conference on 3-D Digital Imaging and Modeling. Piscataway:IEEE Press, 2003: 442-448.
[22]	DOLATSHAH M , HADIAN , MINAEIBIDGOLI B . Ball*-tree:efficient spatial indexing for constrained nearestneighbor search in metric spaces[EB]. arXiv preprint, 2015,arXiv:1511.00628.
[23]	MALKOV Y A , YASHUNIN D A . Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020,42(4): 824-836.
[24]	FU C , XIANG C , WANG C X ,et al. Fast approximate nearest neighbor search with the navigating spreading-out graph[J]. Proceedings of the VLDB Endowment, 2019,12(5): 461-474.
[25]	FU C , WANG C X , CAI D . High dimensional similarity search with satellite system graph:efficiency,scalability,and unindexed query compatibility[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022,44(8): 4139-4150.
[26]	PENNINGTON J , SOCHER R , MANNING C . Glove:global vectors for word representation[C]// Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing. Stroudsburg:Association for Computational Linguistics, 2014: 1532-1543.
[27]	ERD?S P , RéNYI A . On random graphs[J]. Publications Mathematica Debrecen, 2022,6(3/4): 290-297.
[28]	WATTS D J , STROGATZ S H . Collective dynamics of “small-world” networks[J]. Nature, 1998,393(6684): 440-442.
[29]	JéGOU H , DOUZE M , SCHMID C . Improving bag-of-features for large scale image search[J]. International Journal of Computer Vision, 2010,87(3): 316-336.
[30]	YANDEX A B , LEMPITSKY V . Efficient indexing of billion-scale datasets of deep descriptors[C]// Proceedings of 2016 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway:IEEE Press, 2016: 2055-2063.

名字	发布时间	类型	规模	维数	约束属性
Deep1B	2016年	图片	1B	96	合成
GloVe.6B	2014年	文本	6B	50	合成
SIFT1M	2010年	图片	1 MB	128	合成

Q	查询方法	DEEP1B	GloVe.6B	SIFT1M	精度提升
30%	FGS	0.63	0.53	0.8	10%
	TF-FGS	0.69	0.57	1.0
60%	FGS	0.52	0.34	0.20	24%
	TF-FGS	0.64	0.54	0.60
90%	FGS	0.02	0.02	0.00	53.3%
	TF-FGS	0.73	0.41	0.5

基于容忍因子的近似最近邻混合查询算法

Approximate nearest neighbor hybrid query algorithm based on tolerance factor

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 30

相关文章 2

Metrics

推荐阅读 0

[1]	窦志成, 文继荣. 大数据时代的互联网分析引擎[J]. 大数据, 2015, 1(3): 36-47.
[2]	吴城文, 张广艳, 郑纬民. 从系统角度审视大图计算[J]. 大数据, 2015, 1(3): 48-61.