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

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

on Machine Learning. 2024. 33177–33195.
[107] Chen Q, Zhao B, Wang HD, Li MQ, Liu CJ, Li ZZ, Yang M, Wang JD. SPANN: Highly-efficient billion-scale approximate nearest
neighbor search. In: Proc. of the 35th Int’l Conf. on Neural Information Processing Systems. New York: Curran Associates Inc., 2021. 398.
[108] Gou YT, Gao JY, Xu YX, Long C. SymphonyQG: Towards symphonious integration of quantization and graph for approximate nearest
neighbor search. Proc. of the ACM on Management of Data, 2025, 3(1): 80. [doi: 10.1145/3709730]
[109] Deng SY, Yan X, Kelvin KWN, Jiang CY, Cheng J. Pyramid: A general framework for distributed similarity search on large-scale
datasets. In: Proc. of the 2019 IEEE Int’l Conf. on Big Data. Angeles: IEEE, 2019. 1066–1071. [doi: 10.1109/BigData47090.2019.
9006219]
[110] Zhang ZL, Jin C, Tang LP, Liu XZ, Jin X. Fast, approximate vector queries on very large unstructured datasets. In: Proc. of the 20th
USENIX Symp. on Networked Systems Design and Implementation. Boston: USENIX, 2023. 995–1011.
[111] Gollapudi S, Karia N, Sivashankar V, Krishnaswamy R, Begwani N, Raz S, Lin YY, Zhang Y, Mahapatro N, Srinivasan P, Singh A,
Simhadri HV. Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters. In: Proc. of the 2023 ACM
Web Conf. Austin: ACM, 2023. 3406–3416. [doi: 10.1145/3543507.3583552]
[112] Patel L, Kraft P, Guestrin C, Zaharia M. ACORN: Performant and predicate-agnostic search over vector embeddings and structured data.
Proc. of the ACM on Management of Data, 2024, 2(3): 120. [doi: 10.1145/3654923]
[113] Zuo CJ, Qiao M, Zhou WC, Li FF, Deng D. SeRF: Segment graph for range-filtering approximate nearest neighbor search. Proc. of the
ACM on Management of Data, 2024, 2(1): 69. [doi: 10.1145/3639324]
[114] Indyk P, Xu HK. Worst-case performance of popular approximate nearest neighbor search implementations: Guarantees and limitations.
In: Proc. of the 37th Int’l Conf. on Neural Information Processing Systems. New Orleans: Curran Associates Inc., 2023. 2891.
[115] Aumüller M, Ceccarello M. The role of local dimensionality measures in benchmarking nearest neighbor search. Information Systems,
2021, 101: 101807. [doi: 10.1016/j.is.2021.101807]
[116] Wang ZY, Wang QT, Cheng XX, Wang P, Palpanas T, Wang W. Steiner-hardness: A query hardness measure for graph-based ANN
indexes. Proc. of the VLDB Endowment, 2024, 17(13): 4668–4682. [doi: 10.14778/3704965.3704974]
[117] Intel advanced vector extensions. 2025. https://www.intel.cn/content/www/cn/zh/support/articles/000005779/processors.html
[118] Introducing NEON Development Article. 2025. https://developer.arm.com/documentation/dht0002/a/Introducing-NEON
[119] Manohar MD, Shen ZQ, Blelloch G, Dhulipala L, Gu Y, Simhadri HV, Sun YH. ParlayANN: Scalable and deterministic parallel graph-
based approximate nearest neighbor search algorithms. In: Proc. of the 29th ACM SIGPLAN Annual Symp. on Principles and Practice
of Parallel Programming. Edinburgh: ACM, 2024. 270–285. [doi: 10.1145/3627535.3638475]
[120] Peng Z, Zhang MJ, Li K, Jin RM, Ren B. iQAN: Fast and accurate vector search with efficient intra-query parallelism on multi-core
architectures. In: Proc. of the 28th ACM SIGPLAN Annual Symp. on Principles and Practice of Parallel Programming. Montreal: ACM,
2023. 313–328. [doi: 10.1145/3572848.3577527]
[121] Zhao WJ, Tan SL, Li P. SONG: Approximate nearest neighbor search on GPU. In: Proc. of the 36th IEEE Int’l Conf. on Data
Engineering (ICDE). Dallas: IEEE, 2020. 1033–1044. [doi: 10.1109/ICDE48307.2020.00094]
[122] Yu YH, Wen D, Zhang Y, Qin L, Zhang WJ, Lin XM. GPU-accelerated proximity graph approximate nearest neighbor search and
construction. In: Proc. of the 38th IEEE Int’l Conf. on Data Engineering (ICDE). Kuala Lumpur: IEEE, 2022. 552–564. [doi: 10.1109/
ICDE53745.2022.00046]
[123] Zhou JB, Guo Q, Jagadish HV, Krcal L, Liu SY, Luan WH, Tung AKH, Yang YJ, Zheng YX. A generic inverted index framework for
similarity search on the GPU. In: Proc. of the 34th IEEE Int’l Conf. on Data Engineering (ICDE). Paris: IEEE, 2018. 893–904. [doi: 10.
1109/ICDE.2018.00085]
[124] Wieschollek P, Wang O, Sorkine-Hornung A, Lensch HPA. Efficient large-scale approximate nearest neighbor search on the GPU. In:
Proc. of the 2016 IEEE Conf. on Computer Vision and Pattern Recognition. Las Vegas: IEEE, 2016. 2027–2035. [doi: 10.1109/CVPR.
2016.223]
[125] Johnson J, Douze M, Jégou H. Billion-scale similarity search with GPUs. IEEE Trans. on Big Data, 2021, 7(3): 535–547. [doi: 10.1109/
TBDATA.2019.2921572]
[126] Chen W, Chen JC, Zou FH, Li YF, Lu P, Zhao W. RobustiQ: A robust ANN search method for billion-scale similarity search on GPUs.
In: Proc. of the 2019 Int’l Conf. on Multimedia Retrieval. Ottawa: ACM, 2019. 132–140. [doi: 10.1145/3323873.3325018]
[127] Groh F, Ruppert L, Wieschollek P, Lensch HPA. GGNN: Graph-based GPU nearest neighbor search. IEEE Trans. on Big Data, 2023,
9(1): 267–279. [doi: 10.1109/TBDATA.2022.3161156]
[128] Zhu YF, Ma RY, Zheng BH, Ke XY, Chen L, Gao YJ. GTS: GPU-based tree index for fast similarity search. Proc. of the ACM on
Management of Data, 2024, 2(3): 142. [doi: 10.1145/3654945]