Ranking continuous nearest neighbors for uncertain trajectories

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

*Corresponding author for this work

Research output: Contribution to journalArticle

20 Scopus citations

Abstract

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
Volume20
Issue number5
DOIs
StatePublished - Oct 1 2011

Keywords

  • Moving objects database
  • Nearest neighbor
  • Uncertainty

ASJC Scopus subject areas

  • Information Systems
  • Hardware and Architecture

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

  • Cite this

    Trajcevski, G. P., Tamassia, R., Cruz, I. F., Scheuermann, P. I., Hartglass, D., & Zamierowski, C. (2011). Ranking continuous nearest neighbors for uncertain trajectories. VLDB Journal, 20(5), 767-791. https://doi.org/10.1007/s00778-011-0249-3