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

doi:10.11959/j.issn.2096-0271.2024010

Abstract

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

CLC Number:

TP391.3，TP18

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.

Figures/Tables 10

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

名字	发布时间	类型	规模	维数	约束属性
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

RichHTML

PDF下载

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 30

Related Articles 1

Metrics

Recommended 0