Efficient processing of moving collective spatial keyword queries

作     者：Xu, Hongfei Gu, Yu Sun, Yu Qi, Jianzhong Yu, Ge Zhang, Rui 

作者机构：Northeastern Univ Coll Comp Sci & Engn Shenyang Liaoning Peoples R China Twitter Inc San Francisco CA USA Univ Melbourne Dept Comp & Informat Syst Melbourne Vic Australia 

出 版 物：《VLDB JOURNAL》 (国际大型数据库杂志)

年 卷 期：2020年第29卷第4期

页      面：841-865页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key R&D Program of China [2018YFB1003404] National Natural Science Foundation of China [61872070, U1811261] Fundamental Research Funds for the Central Universities [N171605001] Liao Ning Revitalization Talents Program [XLYC1807158] 

主　　题：Moving query Collective spatial keyword query Safe region Query processing algorithms 

摘      要：As a major type of continuous spatial queries, the moving spatial keyword queries have been studied extensively. Most existing studies focus on retrieving single objects, each of which is close to the query object and relevant to the query keywords. Nevertheless, a single object may not satisfy all the needs of a user, e.g., a user who is driving may want to withdraw money, wash her car, and buy some medicine, which could only be satisfied by multiple objects. We thereby formulate a new type of queries named the moving collective spatial keyword query (MCSKQ). This type of queries continuously reports a set of objects that collectively cover the query keywords as the query moves. Meanwhile, the returned objects must also be close to the query object and close to each other. Computing the exact result set is an NP-hard problem. To reduce the query processing costs, we propose algorithms, based on safe region techniques, to maintain the exact result set while the query object is moving. We further propose two approximate algorithms to obtain even higher query efficiency with precision bounds. All the proposed algorithms are also applicable to MCSKQ with weighted objects and MCSKQ in the domain of road networks. We verify the effectiveness and efficiency of the proposed algorithms both theoretically and empirically, and the results confirm the superiority of the proposed algorithms over the baseline algorithms.