Level-aware collective spatial keyword queries

详细信息    查看全文

• 作者：Pengfei Zhang¹ ; ^a ; ^{zpf_2013zb@zju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Huaizhong Lin ; ¹ ; ^a ; ^{linhz@zju.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Bin Yao¹ ; ^b ; ^{yaobin@cs.sjtu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Dongming Lu¹ ; ^a ; ^{ldm@zju.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Collective spatial keyword query ; Keyword level ; Branch and bound strategy ; Triggered update strategy
• 刊名：Information Sciences
• 出版年：2017
• 出版时间：1 February 2017
• 年：2017
• 卷：378
• 期：Complete
• 页码：194-214
• 全文大小：2159 K

文摘

The collective spatial keyword query (CoSKQ), which takes a location and a set of keywords as arguments, finds a group of objects that collectively satisfy the query and achieve the smallest cost. However, few studies concern the keyword level (e.g., the level of hotels), which is of critical importance for decision support. Motivated by this, we study a novel query paradigm, namely Level-aware Collective Spatial Keyword (LCSK) query. The LCSK query asks for a group of objects that cover the query keywords collectively with a threshold constraint and minimize the cost function, which takes into account both the cost of objects and the spatial distance. In our settings, each keyword that appears in the textual description of objects is associated with a level for capturing the feature of keyword.

We prove the LCSK query is NP-hard, and devise exact algorithm as well as approximate algorithm with provable approximation bound to this problem. The proposed exact algorithm, namely MergeList, explores the candidate space progressively with several pruning strategies, which is based on the keyword hash table index structure. Unfortunately, this approach is not scalable to large datasets. We thus develop an approximate algorithm called MaxMargin. It finds the answer by traversing the proposed LIR-tree in the best-first fashion. Moreover, two optimizing strategies are used to improve the query performance. The experiments on real and synthetic datasets verify that the proposed approximate algorithm runs much faster than the competitor with desired accuracy.