Efficient Algorithms for Answering the m-Closest Keywords Query

Tao Guo, Xin Cao, Gao Cong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

59 Citations (Scopus)

Abstract

As an important type of spatial keyword query, the m-closest keywords (mCK) query finds a group of objects such that they cover all query keywords and have the smallest diameter, which is defined as the largest distance between any pair of objects in the group. The query is useful in many applications such as detecting locations of web resources. However, the existing work does not study the intractability of this problem and only provides exact algorithms, which are computationally expensive.

In this paper, we prove that the problem of answering mCK queries is NP-hard. We first devise a greedy algorithm that has an approximation ratio of 2. Then, we observe that an mCK query can be approximately answered by finding the circle with the smallest diameter that encloses a group of objects together covering all query keywords. We prove that the group enclosed in the circle can answer the mCK query with an approximation ratio of 2 over 3. Based on this, we develop an algorithm for finding such a circle exactly, which has a high time complexity. To improve efficiency, we propose another two algorithms that find such a circle approximately, with a ratio of 2 over √3 + ε. Finally, we propose an exact algorithm that utilizes the group found by the 2 over √3 + ε)-approximation algorithm to obtain the optimal group. We conduct extensive experiments using real-life datasets. The experimental results offer insights into both efficiency and accuracy of the proposed approximation algorithms, and the results also demonstrate that our exact algorithm outperforms the best known algorithm by an order of magnitude.
Original languageEnglish
Title of host publicationSIGMOD '15 Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data
Place of PublicationNew York
PublisherACM
Pages405-418
Number of pages14
ISBN (Electronic)9781450327589
DOIs
Publication statusPublished - 2015
EventSIGMOD'15 - Melbourne, Australia
Duration: 31 May 201504 Jun 2015

Conference

ConferenceSIGMOD'15
CountryAustralia
CityMelbourne
Period31/05/201504/06/2015

Fingerprint Dive into the research topics of 'Efficient Algorithms for Answering the m-Closest Keywords Query'. Together they form a unique fingerprint.

Cite this