Reverse Nearest Neighbor Search in Semantic Trajectories for Location-Based Services

Xiao Pan, Shili Nie, Haibo Hu, Philip S. Yu, Jingfeng Guo

Research output: Journal article publicationJournal articleAcademic researchpeer-review

6 Citations (Scopus)


In resource planning scenarios, reverse kk nearest neighbor search plays an important role. However, the existing reverse kk nearest neighbor search on trajectories only supports spatial features of trajectories. In this article, we introduce reverse kk nearest neighbors query on semantic trajectories (RkkNNST). Given a query point from a set of geo-textual objects (e.g., POIs), the query finds those trajectories that take this query point as one of their kk nearest geo-textual correlative objects. To efficiently answer RkkNNST queries, we propose a novel index IMC-tree, which organizes the global and local geo-textual information on semantic trajectories. A branch-and-bound search algorithm DOTA is then designed to traverse IMC-tree with various pruning rules. To speed up the computation of correlative distance, we also design an inverted-file-based algorithm to compute without enumerating all combinations of geo-textual objects. Experiments on a real dataset validate the effectiveness and efficiency of our proposed algorithms.

Original languageEnglish
Article number8966480
Pages (from-to)986-999
Number of pages14
JournalIEEE Transactions on Services Computing
Issue number2
Publication statusPublished - Mar 2022


  • geo-textual objects
  • Location-based services
  • reverse nearest neighbor queries
  • semantic-enriched trajectories

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Science Applications
  • Computer Networks and Communications
  • Information Systems and Management


Dive into the research topics of 'Reverse Nearest Neighbor Search in Semantic Trajectories for Location-Based Services'. Together they form a unique fingerprint.

Cite this