Ranking continuous nearest neighbors for uncertain trajectories

Goce Trajcevski*, Roberto Tamassia, Isabel F. Cruz, Peter Scheuermann, David Hartglass, Christopher Zamierowski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Scopus citations


This article addresses the problem of performing Nearest Neighbor (NN) queries on uncertain trajectories. The answer to an NN query for certain trajectories is time parameterized due to the continuous nature of the motion. As a consequence of uncertainty, there may be several objects that have a non-zero probability of being a nearest neighbor to a given querying object, and the continuous nature further complicates the semantics of the answer. We capture the impact that the uncertainty of the trajectories has on the semantics of the answer to continuous NN queries and we propose a tree structure for representing the answers, along with efficient algorithms to compute them. We also address the issue of performing NN queries when the motion of the objects is restricted to road networks. Finally, we formally define and show how to efficiently execute several variants of continuous NN queries. Our experiments demonstrate that the proposed algorithms yield significant performance improvements when compared with the corresponding naïve approaches.

Original languageEnglish (US)
Pages (from-to)767-791
Number of pages25
JournalVLDB Journal
Issue number5
StatePublished - Oct 2011


  • Moving objects database
  • Nearest neighbor
  • Uncertainty

ASJC Scopus subject areas

  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Ranking continuous nearest neighbors for uncertain trajectories'. Together they form a unique fingerprint.

Cite this