Page 38 - 《软件学报》2026年第3期

宋子文 等: 向量数据库中近似最近邻搜索关键技术综述 1001

SIAM Symp. on Discrete Algorithms. Austin: Society for Industrial and Applied Mathematics, 1993. 311–321.
[57] Tavallali P, Tavallali P, Singhal M. K-means tree: An optimal clustering tree for unsupervised learning. The Journal of Supercomputing,
2021, 77(5): 5239–5266. [doi: 10.1007/s11227-020-03436-2]
[58] Fukunaga K, Narendra PM. A branch and bound algorithm for computing k-nearest neighbors. IEEE Trans. on Computers, 1975, C-
24(7): 750–753. [doi: 10.1109/T-C.1975.224297]
[59] spotify/annoy. 2025. https://github.com/spotify/annoy
[60] FLANN—Fast library for approximate nearest neighbors. 2025. https://github.com/flann-lib/flann
[61] Ma HZ, Li JZ, Zhang Y. Reconsidering tree based methods for k-maximum inner-product search: The LRUS-covertree. In: Proc. of the
40th IEEE Int’l Conf. on Data Engineering. Utrecht: IEEE, 2024. 4671–4684. [doi: 10.1109/ICDE60146.2024.00355]
[62] Voronoi diagram. 2025. https://en.wikipedia.org/wiki/Voronoi_diagram
[63] Milvus. 2025. https://milvus.io/zh
[64] Xu Q, Yang J, Zhang F, Pan JD, Chen K, Shen YR, Zhou AC, Du XY. Tribase: A vector data query engine for reliable and lossless
pruning compression using triangle inequalities. Proc. of the ACM on Management of Data, 2025, 3(1): 82. [doi: 10.1145/3709743]
[65] Wei JQ, Lee X, Liao ZY, Palpanas T, Peng BT. Subspace collision: An efficient and accurate framework for high-dimensional
approximate nearest neighbor search. Proc. of the ACM on Management of Data, 2025, 3(1): 79. [doi: 10.1145/3709729]
[66] Bruch S, Nardini FM, Rulli C, Venturini R. Efficient inverted indexes for approximate retrieval over learned sparse representations. In:
Proc. of the 47th Int’l ACM SIGIR Conf. on Research and Development in Information Retrieval. Washington: ACM, 2024. 152–162.
[doi: 10.1145/3626772.3657769]
[67] Xu YM, Liang HY, Li J, Xu ST, Chen Q, Zhang QX, Li C, Yang ZY, Yang F, Yang YQ, Cheng P, Yang M. SPFresh: Incremental in-
place update for billion-scale vector search. In: Proc. of the 29th Symp. on Operating Systems Principles. Koblenz: ACM, 2023.
545–561. [doi: 10.1145/3600006.3613166]
[68] Jafari O, Maurya P, Nagarkar P, Islam KM, Crushev C. A survey on locality sensitive hashing algorithms and their applications.
arXiv:2102.08942, 2021.
[69] Datar M, Immorlica N, Indyk P, Mirrokni VS. Locality-sensitive hashing scheme based on p-stable distributions. In: Proc. of the 20th
Annual Symp. on Computational Geometry. New York: ACM, 2004. 253–262. [doi: 10.1145/997817.997857]
[70] Gan JH, Feng JL, Fang Q, Ng W. Locality-sensitive hashing scheme based on dynamic collision counting. In: Proc. of the 2012 ACM
SIGMOD Int’l Conf. on Management of Data. Scottsdale: ACM, 2012. 541–552. [doi: 10.1145/2213836.2213898]
[71] Zhao X, Chen ZH, Huang K, Zhang RY, Zheng BL, Zhou XF. Efficient approximate maximum inner product search over sparse
vectors. In: Proc. of the 40th IEEE Int’l Conf. on Data Engineering. Utrecht: IEEE, 2024. 3961–3974. [doi: 10.1109/ICDE60146.2024.
00303]
[72] Zhao X, Zheng BL, Yi XM, Luan XF, Xie C, Zhou XF, Jensen CS. FARGO: Fast maximum inner product search via global multi-
probing. Proc. of the VLDB Endowment, 2023, 16(5): 1100–1112. [doi: 10.14778/3579075.3579084]
[73] Norouzi M, Punjani A, Fleet DJ. Fast search in Hamming space with multi-index hashing. In: Proc. of the 2012 IEEE Conf. on
Computer Vision and Pattern Recognition. Providence: IEEE, 2012. 3108–3115. [doi: 10.1109/CVPR.2012.6248043]
[74] Qin JB, Xiao C, Wang YS, Wang W, Lin XM, Ishikawa Y, Wang GR. Generalizing the pigeonhole principle for similarity search in
Hamming space. IEEE Trans. on Knowledge and Data Engineering, 2021, 33(2): 489–505. [doi: 10.1109/TKDE.2019.2899597]
[75] Liu QY, Shen YY, Chen L. HAP: An efficient Hamming space index based on augmented pigeonhole principle. In: Proc. of the 2022 Int’l
Conf. on Management of Data. Philadelphia: ACM, 2022. 917–930. [doi: 10.1145/3514221.3517880]
[76] Ge TZ, He KM, Ke QF, Sun J. Optimized product quantization. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2014, 36(4):
744–755. [doi: 10.1109/TPAMI.2013.240]
[77] Norouzi M, Fleet DJ. Cartesian K-means. In: Proc. of the 2013 IEEE Conf. on Computer Vision and Pattern Recognition. Portland:
IEEE, 2013. 3017–3024. [doi: 10.1109/CVPR.2013.388]
[78] Babenko A, Lempitsky V. Additive quantization for extreme vector compression. In: Proc. of the 2014 IEEE Conf. on Computer Vision
and Pattern Recognition. Columbus: IEEE, 2014. 931–938. [doi: 10.1109/CVPR.2014.124]
[79] Martinez J, Clement J, Hoos HH, Little JJ. Revisiting additive quantization. In: Proc. of the 14th European Conf. on Computer Vision.
Amsterdam: Springer, 2016. 137–153. [doi: 10.1007/978-3-319-46475-6_9]
[80] Zhang T, Du C, Wang JD. Composite quantization for approximate nearest neighbor search. In: Proc. of the 31st Int’l Conf. on Machine
Learning. 2014. II-838–II-846.
[81] Wang JF, Wang JD, Song JK, Xu XS, Shen HT, Li SP. Optimized cartesian K-means. IEEE Trans. on Knowledge and Data
Engineering, 2015, 27(1): 180–192. [doi: 10.1109/TKDE.2014.2324592]