Reverse Keyword Search for Spatio-Textual Top-k Queries in Location-Based Services

Xin Lin, Jianliang Xu, Haibo Hu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

9 Citations (Scopus)

Abstract

Spatio-textual queries retrieve the most similar objects with respect to a given location and a keyword set. Existing studies mainly focus on how to efficiently find the top-k result set given a spatio-textual query. Nevertheless, in many application scenarios, users cannot precisely formulate their keywords and instead prefer to choose them from some candidate keyword sets. Moreover, in information browsing applications, it is useful to highlight the objects with the tags (keywords) under which the objects have high rankings. Driven by these applications, we propose a novel query paradigm, namely reverse keyword search for s patio-textual top-k queries (RSTQ). It returns the keywords under which a target object will be a spatio-textual top-k result. To efficiently process the new query, we devise a novel hybrid index KcR-tree to store and summarize the spatial and textual information of objects. By accessing the high-level nodes of KcR-tree, we can estimate the rankings of the target object without accessing the actual objects. To further improve the performance, we propose three query optimization techniques, i.e., KcR∗-tree, lazy upper-bound updating, and keyword set filtering. We also extend RSTQ to allow the input location to be a spatial region instead of a point. Extensive experimental evaluation demonstrates the efficiency of our proposed query techniques in terms of both the computational cost and I/O cost.
Original languageEnglish
Article number7112142
Pages (from-to)3056-3069
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Volume27
Issue number11
DOIs
Publication statusPublished - 1 Nov 2015
Externally publishedYes

Keywords

  • location-based services
  • Reverse queries
  • spatio-textual queries
  • top-k queries

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Cite this