QQ-SPM: spatial keyword search based on qualitative and quantitative spatial patterns
DOI:
https://doi.org/10.5753/jidm.2025.4182Keywords:
Geo-textual Object Retrieval, Spatial Keyword Search, Spatial Pattern Matching, POI Search, Topological RelationsAbstract
The search for Points of Interest (POIs) based on keywords and user preferences is a daily need for many people. One way of representing this kind of search is the Spatial Pattern Matching (SPM) query, which allows for the retrieval of geo-textual objects based on spatial patterns defined by keywords and distance criteria. However, SPM is not able to represent qualitative requirements, such as connectivity relations between the searched objects. In this context, this work proposes the Qualitative and Quantitative Spatial Pattern Matching (QQ-SPM) query, which allows searches with qualitative connectivity constraints in addition to keywords and distance criteria. We also propose the QQESPM algorithm which combines an efficient use of geo-textual indexing with a top-down search strategy inspired in the Efficient Spatial Pattern Matching (ESPM) algorithm. Through a performance evaluation, QQESPM algorithm proved to be more than 1000 times faster in average execution time than simple approaches for the QQ-SPM search. Furthermore, it achieved slower execution time growth when facing the increase of the dataset size, showcasing its efficienty and efficacy for handling geo-textual searches in a quantitative and qualitative setting.
Downloads
References
Cao, X., Cong, G., Jensen, C. S., and Ooi, B. C. (2011). Collective spatial keyword querying. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 373–384.
Chen, H., Fang, Y., Zhang, Y., Zhang, W., and Wang, L. (2019). Espm: Efficient spatial pattern matching. IEEE Transactions on Knowledge and Data Engineering, 32(6):1227–1233.
Chen, Y., Feng, K., Cong, G., and Kiah, H. M. (2022). Example-based spatial pattern matching. Proceedings of the VLDB Endowment, 15(11):2572–2584.
Chen, Z., Chen, L., Cong, G., and Jensen, C. S. (2021). Location-and keyword-based querying of geo-textual data: a survey. The VLDB Journal, 30:603–640.
Choi, D.-W., Pei, J., and Lin, X. (2016). Finding the minimum spatial keyword cover. In 2016 IEEE 32nd International Conference on Data Engineering (ICDE), pages 685–696. IEEE.
Choi, D.-W., Pei, J., and Lin, X. (2020). On spatial keyword covering. Knowledge and Information Systems, 62(7):2577–2612.
Clementini, E., Di Felice, P., and Van Oosterom, P. (1993). A small set of formal topological relationships suitable for end-user interaction. In International symposium on spatial databases, pages 277–295. Springer.
Clementini, E., Sharma, J., and Egenhofer, M. J. (1994). Modelling topological spatial relations: Strategies for query processing. Computers & graphics, 18(6):815–822.
Cohn, A. G., Bennett, B., Gooday, J., and Gotts, N. M. (1997). Qualitative spatial representation and reasoning with the region connection calculus. geoinformatica, 1:275–316.
Egenhofer, M. J. and Herring, J. (1990). Categorizing binary topological relations between regions, lines, and points in geographic databases. The, 9(94-1):76.
Fang, Y., Cheng, R., Cong, G., Mamoulis, N., and Li, Y. (2018a). On spatial pattern matching. In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pages 293–304. IEEE.
Fang, Y., Cheng, R., Wang, J., Budiman, L., Cong, G., and Mamoulis, N. (2018b). Spacekey: Exploring patterns in spatial databases. In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pages 1577–1580. DOI: 10.1109/ICDE.2018.00180.
Fang, Y., Li, Y., Cheng, R., Mamoulis, N., and Cong, G. (2019). Evaluating pattern matching queries for spatial databases. The VLDB Journal, 28:649–673.
Finkel, R. A. and Bentley, J. L. (1974). Quad trees a data structure for retrieval on composite keys. Acta informatica, 4:1–9.
Guo, T., Cao, X., and Cong, G. (2015). Efficient algorithms for answering the m-closest keywords query. In Proceedings of the 2015 ACM SIGMOD international conference on management of data, pages 405–418.
Hermoso, R., Trillo-Lado, R., and Ilarri, S. (2019). Recoskq: Towards pois recommendation using collective spatial keyword queries. In CEUR workshop proc., number ART-2019-114041.
Li, Y., Fang, Y., Cheng, R., and Zhang, W. (2019). Spatial pattern matching: A new direction for finding spatial objects. SIGSPATIAL Special, 11(1):3–12. DOI: 10.1145/3355491.3355493.
Long, Z., Duckham, M., Li, S., and Schockaert, S. (2016). Indexing large geographic datasets with compact qualitative representation. International Journal of Geographical Information Science, 30(6):1072–1094.
Minervino, C., Campelo, C., Oliveira, M., and Silva, S. (2023). Qqespm: A quantitative and qualitative spatial pattern matching algorithm. arXiv preprint arXiv:2312.08992.
Rafael, G. J. R. (2021). Busca por grupos de pontos de interesse usando processamento qualitativo de regiões espaciais. Master’s thesis, Universidade Federal de Campina Grande, Centro de Engenharia Elétrica e Informática, Programa de Pós-Graduação em Ciência da Computação, Campina Grande, Paraíba, Brasil.
Randell, D. A., Cui, Z., and Cohn, A. G. (1992). A spatial logic based on regions and connection. KR, 92:165–176.
Zhang, C., Zhang, Y., Zhang, W., and Lin, X. (2016). Inverted linear quadtree: Efficient top k spatial keyword search. IEEE Transactions on Knowledge and Data Engineering, 28(7):1706–1721.
Zhang, D., Tan, K.-L., and Tung, A. K. (2013). Scalable top-k spatial keyword search. In Proceedings of the 16th international conference on extending database technology, pages 359–370.
