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.
