{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:45Z","timestamp":1779174825436,"version":"3.51.4"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61832017"],"award-info":[{"award-number":["61832017"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["The VLDB Journal"],"published-print":{"date-parts":[[2025,1]]},"DOI":"10.1007\/s00778-024-00894-5","type":"journal-article","created":{"date-parts":[[2025,1,4]],"date-time":"2025-01-04T03:32:06Z","timestamp":1735961526000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient top-k spatial-range-constrained approximate nearest neighbor search on geo-tagged high-dimensional vectors"],"prefix":"10.1007","volume":"34","author":[{"given":"Yitong","family":"Song","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6478-4209","authenticated-orcid":false,"given":"Bin","family":"Yao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhida","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiong","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mengshi","family":"Chen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,4]]},"reference":[{"key":"894_CR1","unstructured":"Abedi, H.: Large dataset of geotagged images. https:\/\/www.kaggle.com\/datasets\/habedi\/large-dataset-of-geotagged-images (2022)"},{"key":"894_CR2","doi-asserted-by":"crossref","unstructured":"Andr\u00e9, F., Kermarrec, A.M., Le\u00a0Scouarnec, N.: Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In: VLDB. 9, 12 (2016)","DOI":"10.14778\/2856318.2856324"},{"issue":"10","key":"894_CR3","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/B978-044482537-7\/50006-1","volume":"5","author":"F Aurenhammer","year":"2000","unstructured":"Aurenhammer, F., Klein, R.: Voronoi diagrams. Handb. Computational Geom. 5(10), 201\u2013290 (2000)","journal-title":"Handb. Computational Geom."},{"issue":"6","key":"894_CR4","first-page":"1548","volume":"16","author":"I Azizi","year":"2023","unstructured":"Azizi, I., Echihabi, K., Palpanas, T.: Elpis: graph-based similarity search for scalable data science. PVLDB 16(6), 1548\u20131559 (2023)","journal-title":"PVLDB"},{"key":"894_CR5","unstructured":"Babenko, A., Lempitsky, V.: Efficient indexing of billion-scale datasets of deep descriptors. In: CVPR, pp. 2055\u20132063 (2016)"},{"key":"894_CR6","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Kriegel, H.P., Schneider, R., Seeger, B.: The r*-tree: An efficient and robust access method for points and rectangles. In: SIGMOD, pp. 322\u2013331 (1990)","DOI":"10.1145\/93605.98741"},{"key":"894_CR7","doi-asserted-by":"crossref","unstructured":"Beckmann, N., Seeger, B.: A revised r*-tree in comparison with related index structures. In: SIGMOD, pp. 799\u2013812 (2009)","DOI":"10.1145\/1559845.1559929"},{"issue":"9","key":"894_CR8","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Commun. ACM 18(9), 509\u2013517 (1975)","journal-title":"Commun. ACM"},{"key":"894_CR9","unstructured":"Chen, Q., Zhao, B., Wang, H., Li, M., Liu, C., Li, Z., Yang, M., Wang, J.: Spann: Highly-efficient billion-scale approximate nearest neighbor search. arXiv preprint arXiv:2111.08566 (2021)"},{"key":"894_CR10","doi-asserted-by":"crossref","unstructured":"Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In: SIGKDD, pp. 1082\u20131090 (2011)","DOI":"10.1145\/2020408.2020579"},{"key":"894_CR11","unstructured":"Christian\u00a0Safka, M.C.: Image 2 vec with pytorch. https:\/\/github.com\/christiansafka\/img2vec (2022). Accessed: 2023-03-15"},{"key":"894_CR12","unstructured":"Delaunay, B., et\u00a0al.: Sur la sphere vide. Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7(793-800), 1\u20132 (1934)"},{"key":"894_CR13","doi-asserted-by":"crossref","unstructured":"Devillers, O.: Improved incremental randomized delaunay triangulation. In: Proceedings of the fourteenth annual symposium on computational geometry, pp. 106\u2013115 (1998)","DOI":"10.1145\/276884.276896"},{"key":"894_CR14","doi-asserted-by":"crossref","unstructured":"Ding, J., Nathan, V., Alizadeh, M., Kraska, T.: Tsunami: A learned multi-dimensional index for correlated data and skewed workloads. arXiv preprint arXiv:2006.13282 (2020)","DOI":"10.14778\/3425879.3425880"},{"key":"894_CR15","unstructured":"Ding, X.: A comprehensive jmh-based benchmark on various rtree configurations for dave moten\u2019s rtree implementation. https:\/\/github.com\/ambling\/rtree-benchmark (2016). Accessed: 2022-10-31"},{"issue":"3","key":"894_CR16","first-page":"403","volume":"13","author":"K Echihabi","year":"2019","unstructured":"Echihabi, K., Zoumpatianos, K., Palpanas, T., Benbrahim, H.: Return of the lernaean hydra: experimental evaluation of data series approximate similarity search. PVLDB 13(3), 403\u2013420 (2019)","journal-title":"PVLDB"},{"key":"894_CR17","unstructured":"FilterFAISS Contributors: Filterfaiss. https:\/\/python.langchain.com\/docs\/integrations\/vectorstores\/faiss. Accessed: 2024-05-28"},{"key":"894_CR18","doi-asserted-by":"crossref","unstructured":"Fu, C., Wang, C., Cai, D.: High dimensional similarity search with satellite system graph: efficiency, scalability, and unindexed query compatibility. TPAMI (2021)","DOI":"10.1109\/TPAMI.2021.3067706"},{"issue":"5","key":"894_CR19","first-page":"416","volume":"12","author":"C Fu","year":"2019","unstructured":"Fu, C., Xiang, C., Wang, C., Cai, D.: Fast approximate nearest neighbor search with the navigating spreading-out graph. PVLDB 12(5), 416\u2013474 (2019)","journal-title":"PVLDB"},{"key":"894_CR20","doi-asserted-by":"crossref","unstructured":"Gollapudi, S., Karia, N., Sivashankar, V., Krishnaswamy, R., Begwani, N., Raz, S., Lin, Y., Zhang, Y., Mahapatro, N., Srinivasan, P., et\u00a0al.: Filtered-diskann: Graph algorithms for approximate nearest neighbor search with filters. In: WWW, pp. 3406\u20133416 (2023)","DOI":"10.1145\/3543507.3583552"},{"key":"894_CR21","doi-asserted-by":"crossref","unstructured":"Gong, L., Wang, H., Ogihara, M., Xu, J.: idec: indexable distance estimating codes for approximate nearest neighbor search. PVLDB 13(9) (2020)","DOI":"10.14778\/3397230.3397243"},{"key":"894_CR22","unstructured":"Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., Kumar, S.: Accelerating large-scale inference with anisotropic vector quantization. In: ICML, pp. 3887\u20133896 (2020)"},{"key":"894_CR23","doi-asserted-by":"crossref","unstructured":"Guttman, A.: R-trees: A dynamic index structure for spatial searching. In: SIGMOD, pp. 47\u201357 (1984)","DOI":"10.1145\/971697.602266"},{"issue":"1","key":"894_CR24","first-page":"1","volume":"9","author":"Q Huang","year":"2015","unstructured":"Huang, Q., Feng, J., Zhang, Y., Fang, Q., Ng, W.: Query-aware locality-sensitive hashing for approximate nearest neighbor search. PVLDB 9(1), 1\u201312 (2015)","journal-title":"PVLDB"},{"key":"894_CR25","unstructured":"Jayaram\u00a0Subramanya, S., Devvrit, F., Simhadri, H.V., Krishnawamy, R., Kadekodi, R.: Diskann: Fast accurate billion-point nearest neighbor search on a single node. Advances in neural information processing Systems 32 (2019)"},{"issue":"1","key":"894_CR26","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.: Product quantization for nearest neighbor search. TPAMI 33(1), 117\u2013128 (2010)","journal-title":"TPAMI"},{"key":"894_CR27","doi-asserted-by":"crossref","unstructured":"J\u00e9gou, H., Tavenard, R., Douze, M., Amsaleg, L.: Searching in one billion vectors: re-rank with source coding. In: ICASSP, pp. 861\u2013864 (2011)","DOI":"10.1109\/ICASSP.2011.5946540"},{"issue":"3","key":"894_CR28","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1109\/TBDATA.2019.2921572","volume":"7","author":"J Johnson","year":"2019","unstructured":"Johnson, J., Douze, M., J\u00e9gou, H.: Billion-scale similarity search with gpus. IEEE Trans. Big Data 7(3), 535\u2013547 (2019)","journal-title":"IEEE Trans. Big Data"},{"key":"894_CR29","unstructured":"Laurent\u00a0Amsaleg, H.J.: Gist dataset. http:\/\/corpus-texmex.irisa.fr\/. Accessed: 2023-10-25"},{"key":"894_CR30","unstructured":"Leutenegger, S.T., Lopez, M.A., Edgington, J.: Str: A simple and efficient algorithm for r-tree packing. In: ICDE, pp. 497\u2013506 (1997)"},{"issue":"8","key":"894_CR31","first-page":"1475","volume":"32","author":"W Li","year":"2019","unstructured":"Li, W., Zhang, Y., Sun, Y., Wang, W., Li, M., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data-experiments, analyses, and improvement. TKDE 32(8), 1475\u20131488 (2019)","journal-title":"TKDE"},{"issue":"2","key":"894_CR32","first-page":"246","volume":"15","author":"K Lu","year":"2021","unstructured":"Lu, K., Kudo, M., Xiao, C., Ishikawa, Y.: Hvs: hierarchical graph structure based on voronoi diagrams for solving approximate nearest neighbor search. PVLDB 15(2), 246\u2013258 (2021)","journal-title":"PVLDB"},{"key":"894_CR33","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.: Approximate nearest neighbor algorithm based on navigable small world graphs. Inf. Syst. 45, 61\u201368 (2014)","journal-title":"Inf. Syst."},{"issue":"4","key":"894_CR34","doi-asserted-by":"publisher","first-page":"824","DOI":"10.1109\/TPAMI.2018.2889473","volume":"42","author":"YA Malkov","year":"2018","unstructured":"Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. TPAMI 42(4), 824\u2013836 (2018)","journal-title":"TPAMI"},{"key":"894_CR35","doi-asserted-by":"crossref","unstructured":"Mohoney, J., Pacaci, A., Chowdhury, S.R., Mousavi, A., Ilyas, I.F., Minhas, U.F., Pound, J., Rekatsinas, T.: High-throughput vector similarity search in knowledge graphs. In: SIGMOD, pp. 1\u201325 (2023)","DOI":"10.1145\/3589777"},{"issue":"11","key":"894_CR36","doi-asserted-by":"publisher","first-page":"2227","DOI":"10.1109\/TPAMI.2014.2321376","volume":"36","author":"M Muja","year":"2014","unstructured":"Muja, M., Lowe, D.G.: Scalable nearest neighbor algorithms for high dimensional data. TPAMI 36(11), 2227\u20132240 (2014)","journal-title":"TPAMI"},{"issue":"1","key":"894_CR37","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/348.318586","volume":"9","author":"J Nievergelt","year":"1984","unstructured":"Nievergelt, J., Hinterberger, H., Sevcik, K.C.: The grid file: an adaptable, symmetric multikey file structure. TODS 9(1), 38\u201371 (1984)","journal-title":"TODS"},{"key":"894_CR38","unstructured":"OpenStreetMap Contributors: Openstreetmap project. https:\/\/www.openstreetmap.org (2017). Accessed: 2022-05-30"},{"key":"894_CR39","doi-asserted-by":"crossref","unstructured":"Patel, L., Kraft, P., Guestrin, C., Zaharia, M.: Acorn: Performant and predicate-agnostic search over vector embeddings and structured data. arXiv preprint arXiv:2403.04871 (2024)","DOI":"10.1145\/3654923"},{"key":"894_CR40","first-page":"10672","volume":"33","author":"J Ren","year":"2020","unstructured":"Ren, J., Zhang, M., Li, D.: Hm-ann: efficient billion-point nearest neighbor search on heterogeneous memory. Adv. Neural Inf. Proc. Syst. 33, 10672\u201310684 (2020)","journal-title":"Adv. Neural Inf. Proc. Syst."},{"issue":"1","key":"894_CR41","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1006\/jvci.1999.0413","volume":"10","author":"Y Rui","year":"1999","unstructured":"Rui, Y., Huang, T.S., Chang, S.F.: Image retrieval: current techniques, promising directions, and open issues. J. Visual Commun. Image Represent. 10(1), 39\u201362 (1999)","journal-title":"J. Visual Commun. Image Represent."},{"issue":"2","key":"894_CR42","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1145\/356924.356930","volume":"16","author":"H Samet","year":"1984","unstructured":"Samet, H.: The quadtree and related hierarchical data structures. CSUR 16(2), 187\u2013260 (1984)","journal-title":"CSUR"},{"key":"894_CR43","doi-asserted-by":"crossref","unstructured":"Schroff, F., Kalenichenko, D., Philbin, J.: Facenet: A unified embedding for face recognition and clustering. In: CVPR, pp. 815\u2013823 (2015)","DOI":"10.1109\/CVPR.2015.7298682"},{"key":"894_CR44","unstructured":"Sellis, T., Roussopoulos, N., Faloutsos, C.: The r+-tree: A dynamic index for multi-dimensional objects. Tech. rep. (1987)"},{"key":"894_CR45","doi-asserted-by":"crossref","unstructured":"Sheng, Y., Cao, X., Fang, Y., Zhao, K., Qi, J., Cong, G., Zhang, W.: Wisk: A workload-aware learned index for spatial keyword queries. arXiv preprint arXiv:2302.14287 (2023)","DOI":"10.1145\/3589332"},{"key":"894_CR46","doi-asserted-by":"crossref","unstructured":"Sun, Y., Wang, W., Qin, J., Zhang, Y., Lin, X.: Srs: solving c-approximate nearest neighbor queries in high dimensional euclidean space with a tiny index. PVLDB (2014)","DOI":"10.14778\/2735461.2735462"},{"issue":"2","key":"894_CR47","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1145\/2812802","volume":"59","author":"Thomee Bart","year":"2016","unstructured":"Bart, Thomee, Shamma, David A., et al.: Yfcc100m: The new data in multimedia research. Commun. ACM 59(2), 64\u201373 (2016)","journal-title":"Commun. ACM"},{"key":"894_CR48","doi-asserted-by":"crossref","unstructured":"Wang, J., Yi, X., Guo, R., Jin, H., Xu, P., Li, S., Wang, X., Guo, X., Li, C., Xu, X., et\u00a0al.: Milvus: A purpose-built vector data management system. In: SIGMOD, pp. 2614\u20132627 (2021)","DOI":"10.1145\/3448016.3457550"},{"key":"894_CR49","unstructured":"Wang, M., Lv, L., Xu, X., Wang, Y., Yue, Q., Ni, J.: Navigable proximity graph-driven native hybrid queries with structured and unstructured constraints. arXiv preprint arXiv:2203.13601 (2022)"},{"key":"894_CR50","doi-asserted-by":"crossref","unstructured":"Wang, M., Xu, X., Yue, Q., Wang, Y.: A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. arXiv preprint arXiv:2101.12631 (2021)","DOI":"10.14778\/3476249.3476255"},{"key":"894_CR51","doi-asserted-by":"crossref","unstructured":"Wang, X., Zhang, Y., Zhang, W., Lin, X., Wang, W.: Ap-tree: Efficiently support continuous spatial-keyword queries over stream. In: ICDE, pp. 1107\u20131118 (2015)","DOI":"10.1109\/ICDE.2015.7113360"},{"key":"894_CR52","unstructured":"Weber, R., Schek, H.J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: VLDB, vol.\u00a098, pp. 194\u2013205 (1998)"},{"issue":"12","key":"894_CR53","first-page":"3152","volume":"13","author":"C Wei","year":"2020","unstructured":"Wei, C., Wu, B., Wang, S., Lou, R., Zhan, C., Li, F., Cai, Y.: Analyticdb-v: A hybrid analytical engine towards query fusion for structured and unstructured data. PVLDB 13(12), 3152\u20133165 (2020)","journal-title":"PVLDB"},{"key":"894_CR54","doi-asserted-by":"crossref","unstructured":"Wu, W., He, J., Qiao, Y., Fu, G., Liu, L., Yu, J.: Hqann: Efficient and robust similarity search for hybrid queries with structured and unstructured constraints. In: CIKM, pp. 4580\u20134584 (2022)","DOI":"10.1145\/3511808.3557610"},{"key":"894_CR55","unstructured":"Yury Malkov, et al.: hnswlib. https:\/\/github.com\/nmslib\/hnswlib. Accessed: 2024-05-30"},{"issue":"10","key":"894_CR56","first-page":"2645","volume":"16","author":"C Zuo","year":"2023","unstructured":"Zuo, C., Deng, D.: Arkgraph: All-range approximate k-nearest-neighbor graph. PVLDB 16(10), 2645\u20132658 (2023)","journal-title":"PVLDB"}],"container-title":["The VLDB Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00894-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00778-024-00894-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00778-024-00894-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,27]],"date-time":"2025-01-27T05:53:25Z","timestamp":1737957205000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00778-024-00894-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":56,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["894"],"URL":"https:\/\/doi.org\/10.1007\/s00778-024-00894-5","relation":{},"ISSN":["1066-8888","0949-877X"],"issn-type":[{"value":"1066-8888","type":"print"},{"value":"0949-877X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"22 December 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 November 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 January 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"14"}}