Reverse keyword-based location search

Xike Xie, Xin Lin, Jianliang XU, Christian S. Jensen

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

14 Citations (Scopus)


The proliferation of geo-Textual data gives prominence to spatial keyword search. The basic top-k spatial keyword query, returns k geo-Textual objects that rank the highest according to their textual relevance and spatial proximity to query keywords and a query location. We define, study, and provide means of computing the reverse top-k keyword-based location query. This new type of query takes a set of keywords, a query object q, and a number k as arguments, and it returns a spatial region such that any top-k spatial keyword query with the query keywords and a location in this region would contain object q in its result. This query targets applications in market analysis, geographical planning, and location optimization, and it may support applications related to safe zones and influence zones that are used widely in location-based services. We show that computing an exact query result requires evaluating and merging a set of weighted Voronoi cells, which is expensive. We therefore devise effective algorithms that approximate result regions with quality guarantees. We develop novel pruning techniques on top of an index, and we offer a series of optimization techniques that aim to further accelerate query processing. Empirical studies suggest that the proposed query processing is efficient and scalable.

Original languageEnglish
Title of host publicationProceedings - 2017 IEEE 33rd International Conference on Data Engineering, ICDE 2017
PublisherIEEE Computer Society
Number of pages12
ISBN (Electronic)9781509065431
Publication statusPublished - 16 May 2017
Event33rd IEEE International Conference on Data Engineering, ICDE 2017 - San Diego, United States
Duration: 19 Apr 201722 Apr 2017

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Conference33rd IEEE International Conference on Data Engineering, ICDE 2017
Country/TerritoryUnited States
CitySan Diego

Scopus Subject Areas

  • Software
  • Signal Processing
  • Information Systems


Dive into the research topics of 'Reverse keyword-based location search'. Together they form a unique fingerprint.

Cite this