Collective spatial keyword queries: A distance owner-driven approach
Refereed conference paper presented and published in conference proceedings

Times Cited
Altmetrics Information

Other information
AbstractRecently, spatial keyword queries become a hot topic in the literature. One example of these queries is the collective spatial keyword query (CoSKQ) which is to find a set of objects in the database such that it covers a set of given keywords collectively and has the smallest cost. Unfortunately, existing exact algorithms have severe scalability problems and existing approximate algorithms, though scalable, cannot guarantee near-to-optimal solutions. In this paper, we study the CoSKQ problem and address the above issues. Firstly, we consider the CoSKQ problem using an existing cost measurement called the maximum sum cost. This problem is called MaxSum-CoSKQ and is known to be NP-hard. We observe that the maximum sum cost of a set of objects is dominated by at most three objects which we call the distance owners of the set. Motivated by this, we propose a distance owner-driven approach which involves two algorithms: one is an exact algorithm which runs faster than the best-known existing algorithm by several orders of magnitude and the other is an approximate algorithm which improves the best-known constant approximation factor from 2 to 1.375. Secondly, we propose a new cost measurement called diameter cost and CoSKQ with this measurement is called Dia-CoSKQ. We prove that Dia-CoSKQ is NP-hard. With the same distance owner-driven approach, we design two algorithms for Dia-CoSKQ: one is an exact algorithm which is efficient and scalable and the other is an approximate algorithm which gives a V3-factor approximation. We conducted extensive experiments on real datasets which verified that the proposed exact algorithms are scalable and the proposed approximate algorithms return near-to-optimal solutions. Copyright © 2013 ACM.
All Author(s) ListLong C., Wong R.C.-W., Wang K., Fu A.W.-C.
Name of Conference2013 ACM SIGMOD Conference on Management of Data, SIGMOD 2013
Start Date of Conference22/06/2013
End Date of Conference27/06/2013
Place of ConferenceNew York, NY
Country/Region of ConferenceUnited States of America
Detailed descriptionorganized by ACM,
Pages689 - 700
LanguagesEnglish-United Kingdom
KeywordsDistance owner-driven approach, Spatial keyword querying

Last updated on 2020-14-10 at 01:58