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

1000 软件学报 2026 年第 37 卷第 3 期

[32] Qin JB, Wang YS, Xiao C, Wang W, Lin XM, Ishikawa Y. GPH: Similarity search in Hamming space. In: Proc. of the 34th IEEE Int’l
Conf. on Data Engineering (ICDE). Paris: IEEE, 2018. 29–40. [doi: 10.1109/ICDE.2018.00013]
[33] Jégou H, Douze M, Schmid C. Product quantization for nearest neighbor search. IEEE Trans. on Pattern Analysis and Machine
Intelligence, 2011, 33(1): 117–128. [doi: 10.1109/TPAMI.2010.57]
[34] Gao JY, Long C. RaBitQ: Quantizing high-dimensional vectors with a theoretical error bound for approximate nearest neighbor search.
Proc. of the ACM on Management of Data, 2024, 2(3): 167. [doi: 10.1145/3654970]
[35] Aguerrebere C, Bhati IS, Hildebrand M, Tepper M, Willke T. Similarity search in the blink of an eye with compressed indices. Proc. of
the VLDB Endowment, 2023, 16(11): 3433–3446. [doi: 10.14778/3611479.3611537]
[36] Subramanya SJ, Devvrit, Kadekodi R, Krishaswamy R, Simhadri HV. DiskANN: Fast accurate billion-point nearest neighbor search on
a single node. In: Proc. of the 33rd Int’l Conf. on Neural Information Processing Systems. Vancouver: Curran Associates Inc., 2019. 1233.
[37] Wang JD, Li SP. Query-driven iterated neighborhood graph search for large scale indexing. In: Proc. of the 20th ACM Int’l Conf. on
Multimedia. Nara: ACM, 2012. 179–188. [doi: 10.1145/2393347.2393378]
[38] Zhao X, Tian Y, Huang K, Zheng BL, Zhou XF. Towards efficient index construction and approximate nearest neighbor search in high-
dimensional spaces. Proc. of the VLDB Endowment, 2023, 16(8): 1979–1991. [doi: 10.14778/3594512.3594527]
[39] Jégou H, Tavenard R, Douze M, Amsaleg L. Searching in one billion vectors: Re-rank with source coding. In: Proc. of the 2011 IEEE
Int’l Conf. on Acoustics, Speech and Signal Processing (ICASSP). Prague: IEEE, 2011. 861–864. [doi: 10.1109/ICASSP.2011.5946540]
[40] Sun YF, Wang W, Qin JB, Zhang Y, Lin XM. SRS: Solving c-approximate nearest neighbor queries in high dimensional Euclidean
space with a tiny index. Proc. of the VLDB Endowment, 2014, 8(1): 1–12. [doi: 10.14778/2735461.2735462]
[41] Malkov Y, Ponomarenko A, Logvinov A, Krylov V. Approximate nearest neighbor algorithm based on navigable small world graphs.
Information Systems, 2014, 45: 61–68. [doi: 10.1016/j.is.2013.10.006]
[42] Dong W, Moses C, Li K. Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proc. of the 20th Int’l
Conf. on World Wide Web. Hyderabad: ACM, 2011. 577–586. [doi: 10.1145/1963405.1963487]
[43] Peng Y, Choi B, Chan TN, Yang JY, Xu JL. Efficient approximate nearest neighbor search in multi-dimensional databases. Proc. of the
ACM on Management of Data, 2023, 1(1): 54. [doi: 10.1145/3588908]
[44] Harwood B, Drummond T. FANNG: Fast approximate nearest neighbour graphs. In: Proc. of the 2016 IEEE Conf. on Computer Vision
and Pattern Recognition (CVPR). Las Vegas: IEEE, 2016. 5713–5722. [doi: 10.1109/CVPR.2016.616]
[45] Fu C, Wang CX, Cai D. High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query
compatibility. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2022, 44(8): 4139–4150. [doi: 10.1109/TPAMI.2021.
3067706]
[46] Zhang JR, Ma RH, Song T, Hua Y, Xue ZG, Guan CY, Guan HB. Hierarchical satellite system graph for approximate nearest neighbor
search on big data. ACM/IMS Trans. on Data Science, 2021, 2(4): 32. [doi: 10.1145/3488377]
[47] Muñoz JV, Gonçalves MA, Dias Z, Torres RDS. Hierarchical clustering-based graphs for large scale approximate nearest neighbor
search . Pattern Recognition, 2019, 96: 106970. [doi: 10.1016/j.patcog.2019.106970]
[48] Chen M, Zhang K, He ZY, Jing YN, Wang XS. RoarGraph: A projected bipartite graph for efficient cross-modal approximate nearest
neighbor search. Proc. of the VLDB Endowment, 2024, 17(11): 2735–2749. [doi: 10.14778/3681954.3681959]
[49] Singh A, Subramanya SJ, Krishnaswamy R, Simhadri HV. FreshDiskANN: A fast and accurate graph-based ANN index for streaming
similarity search. arXiv:2105.09613, 2021.
[50] Silpa-Anan C, Hartley R. Optimised KD-trees for fast image descriptor matching. In: Proc. of the 2008 IEEE Conf. on Computer Vision
and Pattern Recognition. Anchorage: IEEE, 2008. 1–8. [doi: 10.1109/CVPR.2008.4587638]
[51] Guttman A. R-trees: A dynamic index structure for spatial searching. In: Proc. of the 1984 ACM SIGMOD Int’l Conf. on Management
of Data. Boston: ACM, 1984. 47–57. [doi: 10.1145/602259.602266]
[52] Sproull RF. Refinements to nearest-neighbor searching ink-dimensional trees. Algorithmica, 1991, 6(1–6): 579–589. [doi: 10.1007/
BF01759061]
[53] Dasgupta S, Freund Y. Random projection trees and low dimensional manifolds. In: Proc. of the 40th Annual ACM Symp. on Theory of
Computing. Columbia: ACM, 2008. 537–546. [doi: 10.1145/1374376.1374452]
[54] Dasgupta S, Sinha K. Randomized partition trees for exact nearest neighbor search. In: Proc. of the 26th Annual Conf. on Learning
Theory. 2013. 317–337.
[55] Ciaccia P, Patella M, Zezula P. M-tree: An efficient access method for similarity search in metric spaces. In: Proc. of the 23rd Int’l Conf.
on Very Large Data Bases. San Francisco: Morgan Kaufmann Publishers Inc., 1997. 426–435.
[56] Yianilos PN. Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proc. of the 4th Annual ACM-