Indoor spatial keyword path query method based on time awareness and exclusion preference

Abstract

Existing indoor spatial keyword path queries have not yet addressed user exclusion preferences, and research that simultaneously considers time constraints and exclusion preferences remains unexplored. To address this issue, this paper proposes an indoor spatial keyword path query method based on time awareness and exclusion preference (TEISKPQ). The method introduces a novel and purpose-built Time-awareness and Exclusion-preference Indoor Spatial Keyword tree (TEISK-tree) index structure, specifically designed to organize and manage indoor spatial keyword objects and their associated information. Based on the TEISK-tree index, an index-driven pruning algorithm is developed to rapidly eliminate nodes that do not meet user requirements, significantly reducing computational complexity and enhancing query efficiency. Furthermore, a greedy-based initial path generation algorithm is proposed, which employs a weighted evaluation function to comprehensively assess spatial, textual, and temporal factors between nodes, thereby generating multiple locally optimal initial paths. Finally, an improved genetic algorithm is designed to perform global search-based optimization of the initial paths, thereby better satisfying user requirements by helping to escape local optima and increasing the likelihood of finding high-quality solutions. Experimental results demonstrate that the proposed method exhibits high efficiency and good convergence speed in complex indoor environments, which can improve the efficiency and practicality of indoor path query in urban smart environments and provide support for efficient and intelligent spatial information retrieval.

Keywords

Indoor spatial keyword query / Path query / Exclusion preference / Time awareness

References

[1] Akindele O, Ajayi S, Oyegoke AS, Alaka HA, Omotayo T. Application of geographic information system (gis) in construction: a systematic review. Smart and Sustainable Built Environment, 2025, 14(1): 210-236.

[2] Alamri S, Taniar D, Nguyen K, Alamri A. C-tree: Efficient cell-based indexing of indoor mobile objects. Journal of Ambient Intelligence and Humanized Computing, 2020, 11: 2841-2857.

[3] Asaduzzaman M, Geok TK, Hossain F, Sayeed S, Abdaziz A, Wong H, Tso CP, Ahmed S, Bari MA. An efficient shortest path algorithm: Multi-destinations in an indoor environment. Symmetry, 2021, 13(3): 421.

[4] Ben T, Qin X, Xu J. Index of indoor moving objects for multiple queries. Journal of Computer Research and Development, 2015, 52(9): 2002-2013

[5] Chan, H. K., Liu, T., Li, H., & Lu, H. (2021). Time-constrained indoor keyword-aware routing. In Proceedings of the 17th International Symposium on Spatial and Temporal Databases (pp. 74–84).

[6] Chan HK, Liu T, Li H, Lu H. Time-constrained indoor keyword-aware routing: foundations and extensions. GeoInformatica, 2023, 27(3): 375-426.

[7] Feng, Z., Liu, T., Li, H., Lu, H., Shou, L., & Xu, J. (2020). Indoor top-k keyword-aware routing query. In 2020 IEEE 36th International Conference on Data Engineering (ICDE) (pp. 1213–1224). IEEE.

[8] Han B, Qu T, Tong X, Jiang J, Zlatanova S, Wang H, Cheng C. Grid-optimized uav indoor path planning algorithms in a complex environment. International Journal of Applied Earth Observation and Geoinformation, 2022, 111: 102857.

[9] Jin P, Wang N, Zhang X, Yue L. Moving object data management for indoor spaces. Chinese Journal of Computers, 2015, 38(9): 1777-1795

[10] Kim, I. (2025). Recent advancements in indoor electronic travel aids for the blind or visually impaired: a comprehensive review of technologies and implementations. Universal Access in the Information Society, 24(1), 173–193.

[11] Lee K, Lee J, Kwan M. Location-based service using ontology-based semantic queries: A study with a focus on indoor activities in a university context. Computers, Environment and Urban Systems, 2017, 62: 41-52.

[12] Li B, Zhang C, Li D. A dsp-topk query optimization algorithm supporting indoor obstacle space. Journal of Computer Research and Development, 2017, 54(3): 557-569

[13] Liu, T., Feng, Z., Li, H., Lu, H., Cheema, M. A., Cheng, H., & Xu, J. (2021a). Towards indoor temporal-variation aware shortest path query. IEEE Transactions on Knowledge and Data Engineering,35(1), 998–1012.

[14] Liu, T., Li, H., Lu, H., Cheema, M. A., & Shou, L. (2021b). Towards crowd-aware indoor path planning. Proceedings of the VLDB Endowment,14(8), 1365–1377.

[15] Liu M, Niu B, Yang R. A segmented parallel expansion algorithm for keyword-aware optimal route query. GeoInformatica, 2023, 27(4): 681-707.

[16] Liu X, Wan C, Liu D, Liao G. Survey on spatial keyword search. Journal of Software, 2016, 27(2): 329-347. DOI:

[17] Luo C, Wang P, Li Y, Zheng B, Li G. Efficient time-interval augmented spatial keyword queries on road networks. Information Sciences, 2022, 593: 505-526.

[18] Miao C, Chen G, Yan C, Wu Y. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm. Computers & Industrial Engineering, 2021, 156: 107230.

[19] Miao Y, Yang Y, Li X, Wei L, Liu Z, Deng RH. Efficient privacy-preserving spatial data query in cloud computing. IEEE Transactions on Knowledge and Data Engineering, 2023, 36(1): 122-136.

[20] Negi D, Ray S, Lu R. Pystin: Enabling secure lbs in smart cities with privacy-preserving top-k spatial-textual query. IEEE Internet of Things Journal, 2019, 6(5): 7788-7799.

[21] Peng L, He L, Zhang Y, Zhou Y, Xiao H, Wang R. Planning urban underground space from urban emergency evacuation: A digital layout planning method. Tunnelling and Underground Space Technology, 2023, 140: 105271.

[22] Pu L, Lin C, Chen B, He D. User-friendly public-key authenticated encryption with keyword search for industrial internet of things. IEEE Internet of Things Journal, 2023, 10(15): 13544-13555.

[23] Salgado, C. (2018). Keyword-aware skyline routes search in indoor venues. In Proceedings of the 9th ACM SIGSPATIAL International Workshop on Indoor Spatial Awareness (pp. 25–31).

[24] Shao Z, Cheema MA, Taniar D, Lu H, Yang S. Efficiently processing spatial and keyword queries in indoor venues. IEEE Transactions on Knowledge and Data Engineering, 2021, 33(9): 3229-3244.

[25] Villeneuve H, O’Brien W. Listen to the guests: Text-mining airbnb reviews to explore indoor environmental quality. Building and Environment, 2020, 169: 106555.

[26] Yan J, Zlatanova S, Lee JB, Liu Q. Indoor traveling salesman problem (itsp) path planning. ISPRS International Journal of Geo-Information, 2021, 10(9): 616.

[27] Yang H, Vijayakumar P, Shen J, Gupta BB. A location-based privacy-preserving oblivious sharing scheme for indoor navigation. Future Generation Computer Systems, 2022, 137: 42-52.

[28] Zhang, L., Li, J., & Li, S. (2023a). Research on approximate spatial keyword group queries based on differential privacy and exclusion preferences in road networks. ISPRS International Journal of Geo-Information,12(12), 480.

[29] Zhang, L., Li, J., & Li, S. (2023b). Research on time-aware group query method with exclusion keywords. ISPRS International Journal of Geo-Information,12(10), 438.

[30] Zhang, L., Li, C., & Li, S. (2024a). A personalized query method for spatial keywords in indoor environments. Computational Urban Science,4(1), 38.

[31] Zhang, L., Li, C., & Li, S. (2024b). Research on spatial keyword query methods for indoor fire emergency response. Journal of Safety Science and Technology,20(11), 118–123.

[32] Zhou, Y., Zhang, Y., & Zhang, Y. (2025). Hmlpa*: a hierarchical multi-target lpa* pathfinding algorithm designed for dynamic indoor path network. International Journal of Geographical Information Science, 39(7), 1484–1517.

Funding

Natural Science Foundation of Heilongjiang Province(LH2023F031)

RIGHTS & PERMISSIONS

The Author(s)