Answering Non-Answer Questions on Reverse Top-k Geo-Social Keyword Queries

Due to the wide-spread use of geo-positioning technologies and geo-social networks, the reverse top-k geo-social keyword query has attracted considerable attention from both industry and research communities. A reverse top-k geosocial keyword (RkGSK) query finds the users who are spatially near, textually similar, and socially relevant to a specified point of interest. RkGSK queries are useful in many real-life applications. For example, they can help the query issuer identify potential customers in marketing decisions. However, the query constraints could be too strict sometimes, making it hard to find any result for the RkGSK query. The query issuers may wonder how to modify their original queries to get a certain number of query results. In this paper, we study non-answer questions on reverse top-k geo-social keyword queries (NARGSK). Given an RkGSK query and the required number $\mathcal{M}$ of query results, NARGSK aim to find the refined RkGSK query having $\mathcal{M}$ users in its result set. To efficiently answer NARGSK, we propose two algorithms (ERQ and NRG) based on query relaxation. As this is the first work to address NARGSK to the best of our knowledge, ERQ is the baseline extended from the state-of-the-art method, while NRG further improves the efficiency of ERQ. Extensive experiments using real-life datasets demonstrate the efficiency of our proposed algorithms, and the performance of NRG is improved by a factor of 1–2 on average compared with ERQ.