Answering why-not spatial keyword top-k queries via keyword adaption

Lei Chen, Jianliang Xu, Xin Lin, Christian S. Jensen, Haibo Hu

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

44 Citations (Scopus)
21 Downloads (Pure)


Web objects, often associated with descriptive text documents, are increasingly being geo-tagged. A spatial keyword top-k query retrieves the best k such objects according to a scoring function that considers both spatial distance and textual similarity. However, it is in some cases difficult for users to identify the exact keywords that describe their query intent. After a user issues an initial query and gets back the result, the user may find that some expected objects are missing and may wonder why. Answering the resulting why-not questions can aid users in retrieving better results. However, no existing techniques are able to answer why-not questions by adapting the query keywords. We propose techniques capable of adapting an initial set of query keywords so that expected, but missing, objects enter the result along with other relevant objects. We develop a basic algorithm with a set of optimizations that sequentially examines a sequence of candidate keyword sets. In addition, we present an index-based bound-and-prune algorithm that is able to determine the best sample out of a set of candidates in just one pass of index traversal, thus speeding up the query processing. We also extend the proposed algorithms to handle multiple missing objects. Extensive experimental results offer insight into the efficiency of the proposed techniques in terms of running time and I/O cost.

Original languageEnglish
Title of host publicationProceedings of IEEE 32nd International Conference on Data Engineering, ICDE 2016
Number of pages12
ISBN (Electronic)9781509020195
Publication statusPublished - 16 May 2016
Event32nd IEEE International Conference on Data Engineering, ICDE 2016 - Helsinki, Finland
Duration: 16 May 201620 May 2016

Publication series

NameProceedings of IEEE International Conference on Data Engineering, ICDE


Conference32nd IEEE International Conference on Data Engineering, ICDE 2016

Scopus Subject Areas

  • Artificial Intelligence
  • Computational Theory and Mathematics
  • Computer Graphics and Computer-Aided Design
  • Computer Networks and Communications
  • Information Systems
  • Information Systems and Management


Dive into the research topics of 'Answering why-not spatial keyword top-k queries via keyword adaption'. Together they form a unique fingerprint.

Cite this