close
Skip to main content
Springer Nature Link
Log in

LIST: learning to index spatio-textual data for embedding based spatial keyword queries

  • Regular Paper
  • Published:
Save article
View saved research
The VLDB Journal Aims and scope Submit manuscript

Abstract

With the proliferation of spatio-textual data, Top-k KNN spatial keyword queries (TkQs), which return a list of objects based on a ranking function that considers both spatial and textual relevance, have found many real-life applications. To efficiently handle TkQs, many indexes have been developed, but the effectiveness of TkQ is limited. To improve effectiveness, several deep learning models have recently been proposed, but they suffer severe efficiency issues and there are no efficient indexes specifically designed to accelerate the top-k search process for these deep learning models. To tackle these issues, we consider embedding based spatial keyword queries, which capture the semantic meaning of query keywords and object descriptions in two separate embeddings to evaluate textual relevance. Although various models can be used to generate these embeddings, no indexes have been specifically designed for such queries. To fill this gap, we propose LIST, a novel machine learning based Approximate Nearest Neighbor Search index that Learns to Index the Spatio-Textual data. LIST utilizes a new learning-to-cluster technique to group relevant queries and objects together while separating irrelevant queries and objects. There are two key challenges in building an effective and efficient index, i.e., the absence of high-quality labels and the unbalanced clustering results. We develop a novel pseudo-label generation technique to address the two challenges. Additionally, we introduce a learning based spatial relevance model that can integrate with various text relevance models to form a lightweight yet effective relevance for reranking objects retrieved by LIST. Experimental results show that (1) our lightweight embedding based relevance model significantly outperforms state-of-the-art relevance models; (2) LIST outperforms state-of-the-art indexes, providing a better trade-off between effectiveness and efficiency.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+
from $39.99 /Month
  • Starting from 10 chapters or articles per month
  • Access and download chapters and articles from more than 300k books and 2,500 journals
  • Cancel anytime
View plans

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Algorithm 1
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

Notes

  1. https://www.openstreetmap.org/.

  2. https://github.com/facebookresearch/faiss/issues/148.

  3. https://github.com/onnx/onnx.

  4. https://huggingface.co/bert-base-chinese.

  5. https://huggingface.co/clue/roberta_chinese_base.

References

  1. Babenko, A., Lempitsky, V.S.: The inverted multi-index. IEEE Trans. Pattern Anal. Mach. Intell. 37(6), 1247–1260 (2015)

    Article  Google Scholar 

  2. Cary, A., Wolfson, O., Rishe, N.: Efficient and scalable method for processing top-k spatial boolean queries. In: SSDBM 2010, vol. 6187, pp. 87–95 (2010)

  3. Chen, X., Xu, J., Zhou, R., Zhao, P., Liu, C., Fang, J., Zhao, L.: S\( ^{\text{2 }}\)r-tree: a pivot-based indexing structure for semantic-aware spatial keyword search. GeoInformatica 24(1), 3–25 (2020)

    Article  Google Scholar 

  4. Chen, Y., Li, X., Cong, G., Long, C., Bao, Z., Liu, S., Gu, W., Zhang, F.: Points-of-interest relationship inference with spatial-enriched graph neural networks. Proc. VLDB Endow. 15(3), 504–512 (2021)

    Article  Google Scholar 

  5. Chen, Y., Suel, T., Markowetz, A.: Efficient query processing in geographic web search engines. In: ACM SIGMOD, pp. 277–288 (2006)

  6. Chen, Z., Chen, L., Cong, G., Jensen, C.S.: Location- and keyword-based querying of geo-textual data: a survey. VLDB J. 30(4), 603–640 (2021)

    Article  Google Scholar 

  7. Cong, G., Jensen, C.S., Wu, D.: Efficient retrieval of the top-k most relevant spatial web objects. Proc. VLDB Endow. 2(1), 337–348 (2009)

    Article  Google Scholar 

  8. Devlin, J., Chang, M., Lee, K., Toutanova, K.: BERT: pre-training of deep bidirectional transformers for language understanding. In: NAACL-HLT, pp. 4171– 4186 (2019)

  9. Ding, R., Chen, B., Xie, P., Huang, F., Li, X., Zhang, Q., Xu, Y.: Mgeo: Multi-modal geographic language model pre-training. In: SIGIR, pp. 185–194 (2023)

  10. Dong, Y., Xiao, C., Chen, H., Yu, J.X., Takeoka, K., Oyamada, M., Kitagawa, H.: Continuous top-k spatial-keyword search on dynamic objects. VLDB J. 30(2), 141–161 (2021)

    Article  Google Scholar 

  11. Felipe, I.D., Hristidis, V., Rishe, N.: Keyword search on spatial databases. In: ICDE, pp. 656–665 (2008)

  12. Gao, L., Zhu, X., Song, J., Zhao, Z., Shen, H.T.: Beyond product quantization: deep progressive quantization for image retrieval. In: IJCAI, pp. 723–729 (2019)

  13. Ge, T., He, K., Ke, Q., Sun, J.: Optimized product quantization. IEEE Trans. Pattern Anal. Mach. Intell. 36(4), 744–755 (2014)

    Article  Google Scholar 

  14. Göbel, R., Henrich, A., Niemann, R., Blank, D.: A hybrid index structure for geo-textual searches. In: CIKM, pp. 1625–1628 (2009)

  15. Guo, J., Cai, Y., Fan, Y., Sun, F., Zhang, R., Cheng, X.: Semantic models for the first-stage retrieval: a comprehensive review. ACM Trans. Inf. Syst. 40(4), 66:1-66:42 (2022)

    Article  Google Scholar 

  16. Guo, J., Fan, Y., Pang, L., Yang, L., Ai, Q., Zamani, H., Wu, C., Croft, W.B., Cheng, X.: A deep look into neural ranking models for information retrieval. Inf. Process. Manag. 57(6), 102067 (2020)

    Article  Google Scholar 

  17. Guo, R., Sun, P., Lindgren, E., Geng, Q., Simcha, D., Chern, F., Kumar, S.: Accelerating large-scale inference with anisotropic vector quantization. In: ICML, vol. 119, pp. 3887– 3896 (2020)

  18. He, X., Liao, L., Zhang, H., Nie, L., Hu, X., Chua, T.: Neural collaborative filtering. In: WWW, pp. 173–182 (2017)

  19. Hsu, Y., Lv, Z., Kira, Z.: Learning to cluster in order to transfer across domains and tasks. In: ICLR (2018)

  20. Hsu, Y., Lv, Z., Schlosser, J., Odom, P., Kira, Z.: Multi-class classification without multi-class labels. In: ICLR (2019)

  21. Hsu, Y.C., Kira, Z.: Neural network-based clustering using pairwise constraints. arXiv:1511.06321 (2015)

  22. Hu, B., Lu, Z., Li, H., Chen, Q.: Convolutional neural network architectures for matching natural language sentences. In: NIPS, pp. 2042–2050 (2014)

  23. Huang, P., He, X., Gao, J., Deng, L., Acero, A., Heck, L.P.: Learning deep structured semantic models for web search using clickthrough data. In: CIKM, pp. 2333–2338 (2013)

  24. Huang, P.S., He, X., Gao, J., Deng, L., Acero, A., Heck, L.: Learning deep structured semantic models for web search using clickthrough data. In: CIKM, pp. 2333–2338 (2013)

  25. Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC, pp. 2333–2338 (2013)

  26. Jégou, H., Douze, M., Schmid, C.: Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1), 117–128 (2011)

    Article  Google Scholar 

  27. Joachims, T.: Optimizing search engines using clickthrough data. In: SIGKDD, pp. 133–142 (2002)

  28. Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. IEEE Trans. Big Data 7(3), 535–547 (2019)

    Article  Google Scholar 

  29. Karpukhin, V., Oguz, B., Min, S., Lewis, P.S.H., Wu, L., Edunov, S., Chen, D., Yih, W.t.: Dense passage retrieval for open-domain question answering. In: EMNLP, pp. 6769–6781 (2020)

  30. Li, D., Ding, R., Zhang, Q., Li, Z., Chen, B., Xie, P., Xu, Y., Li, X., Guo, N., Huang, F., He, X.: Geoglue: a geographic language understanding evaluation benchmark. arXiv:2305.06545 (2023)

  31. Li, Z., Lee, K.C.K., Zheng, B., Lee, W., Lee, D.L., Wang, X.: Ir-tree: an efficient index for geographic document search. IEEE Trans. Knowl. Data Eng. 23(4), 585–599 (2011)

    Article  Google Scholar 

  32. Lin, S.C., Yang, J.H., Lin, J.: In-batch negatives for knowledge distillation with tightly-coupled teachers for dense retrieval. In: RepL4NLP, pp. 163–173 (2021)

  33. Liu, S., Cong, G., Feng, K., Gu, W., Zhang, F.: Effectiveness perspectives and a deep relevance model for spatial keyword queries. In: ACM SIGMOD, vol. 1, Nol. 1, pp. 1–25 (2023)

  34. Liu, W., Wang, H., Zhang, Y., Wang, W., Qin, L.: I-lsh: Ispso efficient c-approximate nearest neighbor search in high-dimensional space. In: 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1670–1673. IEEE (2019)

  35. Liu, Y., Cui, J., Huang, Z., Li, H., Shen, H.T.: Sk-lsh: an efficient index structure for approximate nearest neighbor search. Proc. VLDB Endow. 7(9), 745–756 (2014)

    Article  Google Scholar 

  36. Liu, Y., Magdy, A.: U-ASK: a unified architecture for knn spatial-keyword queries supporting negative keyword predicates. In: SIGSPATIAL, pp. 40:140:11 (2022)

  37. Lu, J., Lu, Y., Cong, G.: Reverse spatial and textual k nearest neighbor search. In: ACM SIGMOD, pp. 349–360 (2011)

  38. Luo, X., Wang, H., Wu, D., Chen, C., Deng, M., Huang, J., Hua, X.S.: A survey on deep hashing methods. ACM Trans. Knowl. Discov. Data 17(1), 1–50 (2023)

    Article  Google Scholar 

  39. Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Trans. Pattern Anal. Mach. Intell. 42(4), 824–836 (2020)

    Article  Google Scholar 

  40. Mikolov, T.: Efficient estimation of word representations in vector space. arXiv:1301.3781 (2013)

  41. Pang, L., Lan, Y., Guo, J., Xu, J., Wan, S., Cheng, X.: Text matching as image recognition. In: AAAI, pp. 2793–2799 (2016)

  42. Qian, Z., Xu, J., Zheng, K., Zhao, P., Zhou, X.: Semantic-aware top-k spatial keyword queries. WWW 21(3), 573–594 (2018)

  43. Qin, J., Wang, W., Xiao, C., Zhang, Y., Wang, Y.: High-dimensional similarity query processing for data science. In: SIGKDD, pp. 4062–4063 (2021)

  44. Qu, Y., Ding, Y., Liu, J., Liu, K., Ren, R., Zhao, W.X., Dong, D., Wu, H., Wang, H.: Rocketqa: An optimized training approach to dense passage retrieval for open-domain question answering. In: NAACL-HLT, pp. 5835–5847 (2021)

  45. Ren, R., Qu, Y., Liu, J., Zhao, W.X., She, Q., Wu, H., Wang, H., Wen, J.: Rocketqav2: A joint training method for dense passage retrieval and passage re-ranking. In: EMNLP, pp. 2825–2835 (2021)

  46. Robertson, S.E., Zaragoza, H.: The probabilistic relevance framework: BM25 and beyond. Found. Trends Inf. Retr. 3(4), 333–389 (2009)

    Article  Google Scholar 

  47. Rocha-Junior, J.B., Gkorgkas, O., Jonassen, S., Nørvåg, K.: Efficient processing of top-k spatial keyword queries. In: SSTD, vol. 6849, pp. 205–222 (2011)

  48. Sheng, Y., Cao, X., Fang, Y., Zhao, K., Qi, J., Cong, G., Zhang, W.: WISK: a workload-aware learned index for spatial keyword queries. Proc. ACM Manag. Data 1(2), 187:1-187:27 (2023)

    Article  Google Scholar 

  49. Tao, Y., Sheng, C.: Fast nearest neighbor search with keywords. IEEE Trans. Knowl. Data Eng. 26(4), 878–888 (2014)

    Article  Google Scholar 

  50. Vaid, S., Jones, C.B., Joho, H., Sanderson, M.: Spatio-textual indexing for geographical search on the web. In: SSTD, vol. 3633, pp. 218–235 (2005)

  51. Wang, J., Shen, H.T., Song, J., Ji, J.: Hashing for similarity search: a survey. arXiv:1408.2927 (2014)

  52. Wang, J., Zhang, T., Song, J., Sebe, N., Shen, H.T.: A survey on learning to hash. IEEE Trans. Pattern Anal. Mach. Intell. 40(4), 769–790 (2018)

    Article  Google Scholar 

  53. Wang, M., Xu, X., Yue, Q., Wang, Y.: A comprehensive survey and experimental comparison of graph-based approximate nearest neighbor search. Proc. VLDB Endow. 14(11), 1964–1978 (2021)

    Article  Google Scholar 

  54. Wang, R., Deng, D.: Deltapq: lossless product quantization code compression for high dimensional similarity search. Proc. VLDB Endow. 13(13), 3603–3616 (2020)

    Article  Google Scholar 

  55. Wen, X., Chen, X., Chen, X., He, B., Sun, L.: Offline pseudo relevance feedback for efficient and effective single-pass dense retrieval. In: SIGIR, pp. 2209–2214 (2023)

  56. Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., Brew, J.: Huggingface’s transformers: State-of-the-art natural language processing. arXiv:1910.03771 (2019)

  57. Wu, H.C., Luk, R.W.P., Wong, K., Kwok, K.: Interpreting TF-IDF term weights as making relevance decisions. ACM Trans. Inf. Syst. 26(3), 13:1-13:37 (2008)

    Article  Google Scholar 

  58. Yao, S., Tan, J., Chen, X., Yang, K., Xiao, R., Deng, H., Wan, X.: Learning a product relevance model from click-through data in e-commerce. In: Proceedings of the Web Conference 2021, pp. 2890–2899 (2021)

  59. Yuan, Z., Liu, H., Liu, Y., Zhang, D., Yi, F., Zhu, N., Xiong, H.: Spatio-temporal dual graph attention network for query-poi matching. In: SIGIR, pp. 629–638 (2020)

  60. Zhang, C., Zhang, Y., Zhang, W., Lin, X.: Inverted linear quadtree: Efficient top k spatial keyword search. In: ICDE, pp. 901–912 (2013)

  61. Zhang, D., Chee, Y.M., Mondal, A., Tung, A.K.H., Kitsuregawa, M.: Keyword search in spatial databases: Towards searching by document. In: ICDE, pp. 688–699 (2009)

  62. Zhang, D., Ooi, B.C., Tung, A.K.H.: Locating mapped resources in web 2.0. In: ICDE, pp. 521–532 (2010)

  63. Zhang, D., Tan, K., Tung, A.K.H.: Scalable top-k spatial keyword search. In: EDBT, pp. 359–370 (2013)

  64. Zhao, J., Peng, D., Wu, C., Chen, H., Yu, M., Zheng, W., Ma, L., Chai, H., Ye, J., Qie, X.: Incorporating semantic similarity with geographic correlation for query-poi relevance learning. In: AAAI, pp. 1270–1277 (2019)

  65. Zhao, W.X., Liu, J., Ren, R., Wen, J.: Dense text retrieval based on pretrained language models: a survey. arXiv:2211.14876 (2022)

  66. Zhao, W.X., Liu, J., Ren, R., Wen, J.R.: Dense text retrieval based on pretrained language models: a survey. ACM Trans. Inf. Syst. 42(4), 1–60 (2024)

    Article  Google Scholar 

  67. Zheng, B., Xi, Z., Weng, L., Hung, N.Q.V., Liu, H., Jensen, C.S.: Pm-lsh: a fast and accurate lsh framework for high-dimensional approximate nn search. Proc. VLDB Endow. 13(5), 643–655 (2020)

    Article  Google Scholar 

  68. Zhou, K., Liu, X., Gong, Y., Zhao, W.X., Jiang, D., Duan, N., Wen, J.: MASTER: multi-task pre-trained bottlenecked masked autoencoders are better dense retrievers. In: ECML PKDD, vol. 14170, pp. 630–647 (2023)

  69. Zhou, Y., Xie, X., Wang, C., Gong, Y., Ma, W.: Hybrid index structures for location-based web search. In: CIKM, pp. 155–162 (2005)

Download references

Acknowledgements

This research is supported in part by Singapore MOE AcRF Tier-2 grants MOE-T2EP20221-0015 and MOE-T2EP20223-0004, and a Singapore MOE AcRF Tier-1 project RT6/23. This work is supported in part by the National Natural Science Foundation of China (U23B2048, U22B2037) and the High-performance Computing Platform of Peking University.

Author information

Authors and Affiliations

  1. College of Computing and Data Science, Nanyang Technological University, Singapore, Singapore

    Ziqi Yin, Shang Liu, Gao Cong & Yew Soon Ong

  2. Centre for Frontier AI Research A*STAR, Singapore, Singapore

    Shanshan Feng

  3. School of Computer Science & Key Lab of High Confidence Software Technologies (MOE), Peking University, Beijing, China

    Bin Cui

Authors
  1. Ziqi Yin
    View author publications

    Search author on:PubMed Google Scholar

  2. Shanshan Feng
    View author publications

    Search author on:PubMed Google Scholar

  3. Shang Liu
    View author publications

    Search author on:PubMed Google Scholar

  4. Gao Cong
    View author publications

    Search author on:PubMed Google Scholar

  5. Yew Soon Ong
    View author publications

    Search author on:PubMed Google Scholar

  6. Bin Cui
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Gao Cong.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yin, Z., Feng, S., Liu, S. et al. LIST: learning to index spatio-textual data for embedding based spatial keyword queries. The VLDB Journal 34, 33 (2025). https://doi.org/10.1007/s00778-024-00886-5

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Version of record:

  • DOI: https://doi.org/10.1007/s00778-024-00886-5

Keywords

Profiles

  1. Gao Cong View author profile