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.