{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:17:26Z","timestamp":1750173446645},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T00:00:00Z","timestamp":1691452800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Neural Comput &amp; Applic"],"published-print":{"date-parts":[[2024,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The quantization-based approaches not only are the effective methods for solving the problems of approximate nearest neighbor search, but also effectively reduce storage space. However, many quantization-based approaches usually employ fixed nprobes to the search process for each query. This will lead to extra query consumption. Additionally, we observed that as the number of points in each cluster center of product quantization increases, the query cost also increases. To address this issue, we propose an acceleration strategy based on the IVF-HNSW framework to further speed up the query process. This strategy involves introducing an adaptive termination condition for queries and reducing the number of data points accessed by building HNSW results. Through extensive experiments, we have shown that our proposed method significantly accelerates the nearest neighbor search process.<\/jats:p>","DOI":"10.1007\/s00521-023-08920-3","type":"journal-article","created":{"date-parts":[[2023,8,8]],"date-time":"2023-08-08T11:02:27Z","timestamp":1691492547000},"page":"2303-2313","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Quantization to speedup approximate nearest neighbor search"],"prefix":"10.1007","volume":"36","author":[{"given":"Hao","family":"Peng","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,8]]},"reference":[{"issue":"1","key":"8920_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H Jegou","year":"2010","unstructured":"Jegou H, Douze M, Schmid C (2010) Product quantization for nearest neighbor search. IEEE Trans Pattern Anal Mach Intell 33(1):117\u2013128","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"8920_CR2","doi-asserted-by":"crossref","unstructured":"Baranchuk D, Babenko A, Malkov Y (2018) Revisting the inverted indices for billion-scale approximate nearest neighbors. In: Proceedings of the ECCV, pp 202\u2013216","DOI":"10.1007\/978-3-030-01258-8_13"},{"issue":"4","key":"8920_CR3","first-page":"823","volume":"42","author":"Y-A Malkov","year":"2018","unstructured":"Malkov Y-A, Yashunin D-A (2018) Efcient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans Pattern Anal Mach Intell 42(4):823\u2013836","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"8920_CR4","doi-asserted-by":"crossref","unstructured":"Sivic J, Zisserman A (2003) Video Google: a text retrieval approach to object matching in videos. In: Proceedings of the CVPR, pp 1470\u20131477","DOI":"10.1109\/ICCV.2003.1238663"},{"key":"8920_CR5","doi-asserted-by":"crossref","unstructured":"Li C, Zhang M, Andersen D-G, He, Y (2020) Improving approximate nearest neighbor search through learned adaptive early termination. In: Proceedings of the ACM SIGMOD, pp 2539\u20132554","DOI":"10.1145\/3318464.3380600"},{"issue":"9","key":"8920_CR6","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"J-L Bentley","year":"1975","unstructured":"Bentley J-L (1975) Multidimensional binary search trees used for associative searching. ACM Commun 18(9):509\u2013517","journal-title":"ACM Commun"},{"key":"8920_CR7","unstructured":"Yianilos P-N (1993) Data structures and algorithms for nearest neighbor search in general metric spaces, pp 311\u2013323"},{"key":"8920_CR8","doi-asserted-by":"crossref","unstructured":"Guttmann R (1984) A dynamic index structure for spatial searching. In: Proceedings of the ACM SIGMOD, pp 47\u201357","DOI":"10.1145\/971697.602266"},{"key":"8920_CR9","unstructured":"Sebastian TB, Kimia BB (2002) Metric-based shape retrieval in large databases. In: Proceedings of the pattern recognition, pp. 291\u2013296"},{"key":"8920_CR10","doi-asserted-by":"crossref","unstructured":"Chen L, Gao Y, Li X, Jensen C, Chen G (2017) Efficient metric indexing for similarity search. IEEE Trans Knowl Data Eng 556\u2013571","DOI":"10.1109\/TKDE.2015.2506556"},{"issue":"2","key":"8920_CR11","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/1071610.1071612","volume":"30","author":"H Jagadish","year":"2005","unstructured":"Jagadish H, Ooi B, Tan K, Yu C, Zhang R (2005) iDistance: an adaptive B+-tree based indexing method for nearest neighbor search. ACM Trans Database Syst 30(2):361\u2013397","journal-title":"ACM Trans Database Syst"},{"key":"8920_CR12","unstructured":"Gionis A, Indyk P, Motwani R (1999) Similarity search in high dimensions via hashing. In: Proceedings of the VLDB, pp 518\u2013529"},{"key":"8920_CR13","doi-asserted-by":"crossref","unstructured":"Datar M, Immorlica N, Indyk P, Mirrokni V (2004) Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the SCG, pp 253\u2013262","DOI":"10.1145\/997817.997857"},{"key":"8920_CR14","unstructured":"Lv Q, Josephson W, Wang Z, Charikar M, Li K (2007) Multi-probe LSH: Efficient indexing for high-dimensional similarity search. In: Proceedings of the VLDB, pp 950\u2013961"},{"key":"8920_CR15","doi-asserted-by":"crossref","unstructured":"Huang Q, Feng J, Zhang Y, Fang Q, Ng W (2015) Query-aware locality-sensitive hashing for approximate nearest neighbor search. In: Proceedings of the VLDB, pp 1\u201312","DOI":"10.14778\/2850469.2850470"},{"key":"8920_CR16","doi-asserted-by":"crossref","unstructured":"Lu K, Wang H, Wang W, Kudo M (2020) VHP: approximate nearest neighbor search via virtual hypersphere partitioning. In: Proceedings of the VLDB, pp 1443\u20131455","DOI":"10.14778\/3397230.3397240"},{"key":"8920_CR17","doi-asserted-by":"crossref","unstructured":"Lei Y, Huang Q, Kankanhalli M et al (2020) Locality-sensitive hashing scheme based on longest circular co-substring. In: Proceedings of the SIGMOD, pp 2589\u20132599","DOI":"10.1145\/3318464.3389778"},{"key":"8920_CR18","doi-asserted-by":"crossref","unstructured":"Zheng B, Xi Z, Weng L et al (2020) PM-LSH: a fast and accurate LSH framework for high-dimensional approximate NN search. In: Proceedings of the VLDB, pp 643\u2013655","DOI":"10.14778\/3377369.3377374"},{"key":"8920_CR19","doi-asserted-by":"crossref","unstructured":"Lu K, Kudo M (2020) R2LSH: A nearest neighbor search scheme based on two-dimensional projected spaces. In: Proceedings of the ICDE, pp 1045\u20131056","DOI":"10.1109\/ICDE48307.2020.00095"},{"key":"8920_CR20","doi-asserted-by":"crossref","unstructured":"Fu C, Xiang C, Wang C-X, Cai D (2019) Fast Approximate nearest neighbor search with the navigating spreadingout graph. In: Proceedings of the VLDB, pp 461\u2013474","DOI":"10.14778\/3303753.3303754"},{"key":"8920_CR21","unstructured":"Fu C, Cai D (2016) Efanna: an extremely fast approximate nearest neighbor search algorithm based on knn graph. arXiv:1609.07228"},{"key":"8920_CR22","unstructured":"KGraph. https:\/\/github.com\/aaalgo\/kgraph"},{"issue":"8","key":"8920_CR23","doi-asserted-by":"publisher","first-page":"1475","DOI":"10.1109\/TKDE.2019.2909204","volume":"32","author":"W Li","year":"2019","unstructured":"Li W, Zhang Y, Sun Y, Wang W, Li M, Zhang W, Lin X (2019) Approximate nearest neighbor search on high dimensional data\u2014experiments, analyses, and improvement. IEEE Trans Knowl Data Eng 32(8):1475\u20131488","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"8920_CR24","doi-asserted-by":"publisher","first-page":"108356","DOI":"10.1016\/j.patcog.2021.108356","volume":"122","author":"AJ Gallego","year":"2022","unstructured":"Gallego AJ, Rico-Juan JR, Valero-Mas JJ (2022) Efficient k-nearest neighbor search based on clustering and adaptive k values. Pattern Recognit 122:108356","journal-title":"Pattern Recognit"},{"key":"8920_CR25","unstructured":"Baranchuk D, Persiyanov D, Sinitsin A et al (2019) Learning to route in similarity graphs. In: Proceedings of the ICML, pp 475\u2013484"},{"key":"8920_CR26","unstructured":"Dong Y, Indyk P, Razenshteyn I et al (2019) Learning space partitions for nearest neighbor search. In: Proceedings of the ICLR, pp 1\u201320"},{"key":"8920_CR27","unstructured":"Baranchuk D, Babenko A (2019) Towards similarity graphs constructed by deep reinforcement learning. In: Proceedings of the CoRR"},{"key":"8920_CR28","doi-asserted-by":"crossref","unstructured":"Lee N, Lee J, Park C (2022) Augmentation-free self-supervised learning on graphs. In: Proceedings of the AAAI conference on artificial intelligence, pp 7372\u20137380","DOI":"10.1609\/aaai.v36i7.20700"},{"key":"8920_CR29","doi-asserted-by":"publisher","first-page":"102123","DOI":"10.1016\/j.is.2022.102123","volume":"112","author":"RS Oyamada","year":"2023","unstructured":"Oyamada RS, Shimomura LC, Barbon S Jr et al (2023) A meta-learning configuration framework for graph-based similarity search indexes. Inf Syst 112:102123","journal-title":"Inf Syst"},{"issue":"1","key":"8920_CR30","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1109\/TBDATA.2022.3161156","volume":"9","author":"F Groh","year":"2022","unstructured":"Groh F et al (2022) Ggnn: graph-based gpu nearest neighbor search. IEEE Trans Big Data 9(1):267\u2013279","journal-title":"IEEE Trans Big Data"},{"issue":"4","key":"8920_CR31","doi-asserted-by":"publisher","first-page":"744","DOI":"10.1109\/TPAMI.2013.240","volume":"36","author":"T Ge","year":"2013","unstructured":"Ge T, He K, Ke Q, Sun J (2013) Optimized product quantization. IEEE Trans Pattern Anal Mach Intell 36(4):744\u2013755","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"8920_CR32","doi-asserted-by":"crossref","unstructured":"Babenko A, Lempitsky V (2014) Additive quantization for extreme vector compression. In: Proceedings of the CVPR, pp 931\u2013938","DOI":"10.1109\/CVPR.2014.124"},{"key":"8920_CR33","doi-asserted-by":"crossref","unstructured":"Babenko A, Lempitsky V (2015) Tree quantization for large-scale similarity search and classification. In: Proceedings of the CVPR, pp 4240\u20134248","DOI":"10.1109\/CVPR.2015.7299052"},{"key":"8920_CR34","unstructured":"Zhang T, Du C, Wang J (2014) Composite quantization for approximate nearest neighbor search. In: Proceedings of the ICML, pp 838\u2013846"},{"key":"8920_CR35","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.is.2013.10.006","volume":"45","author":"Y Malkov","year":"2014","unstructured":"Malkov Y, Ponomarenko A, Logvinov A, Krylov V (2014) Approximate nearest neighbor algorithm based on navigable small world graphs. Inf Syst 45:61\u201368","journal-title":"Inf Syst"},{"key":"8920_CR36","doi-asserted-by":"crossref","unstructured":"Nister D, Stewenius H (2006) Scalable recognition with a vocabulary tree. In: Proceedings of the CVPR, pp 2161\u20132168","DOI":"10.1109\/CVPR.2006.264"},{"key":"8920_CR37","doi-asserted-by":"crossref","unstructured":"Arora A, Sinha S, Kumar P, Bhattacharya A (2018) Hd-index: pushing the scalability-accuracy boundary for approximate knn search in high-dimensional spaces. In: Proceedings of the VLDB, pp 906\u2013919","DOI":"10.14778\/3204028.3204034"}],"container-title":["Neural Computing and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00521-023-08920-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00521-023-08920-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00521-023-08920-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,19]],"date-time":"2024-01-19T15:04:52Z","timestamp":1705676692000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00521-023-08920-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,8]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,2]]}},"alternative-id":["8920"],"URL":"https:\/\/doi.org\/10.1007\/s00521-023-08920-3","relation":{},"ISSN":["0941-0643","1433-3058"],"issn-type":[{"value":"0941-0643","type":"print"},{"value":"1433-3058","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,8]]},"assertion":[{"value":"15 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"These no potential competing interests in our paper. And all authors have seen the manuscript and approved to submit to your journal. We confirm that the content of the manuscript has not been published or submitted for publication elsewhere.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}