Retrieving k-nearest neighboring trajectories by a set of point locations

Lu An Tang, Yu Zheng, Xing Xie, Jing Yuan, Xiao Yu, Jiawei Han

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The advance of object tracking technologies leads to huge volumes of spatio-temporal data accumulated in the form of location trajectories. Such data bring us new opportunities and challenges in efficient trajectory retrieval. In this paper, we study a new type of query that finds the k Nearest Neighboring Trajectories (k-NNT) with the minimum aggregated distance to a set of query points. Such queries, though have a broad range of applications like trip planning and moving object study, cannot be handled by traditional k-NN query processing techniques that only find the neighboring points of an object. To facilitate scalable, flexible and effective query execution, we propose a k-NN trajectory retrieval algorithm using a candidate-generation-and-verification strategy. The algorithm utilizes a data structure called global heap to retrieve candidate trajectories near each individual query point. Then, at the verification step, it refines these trajectory candidates by a lower-bound computed based on the global heap. The global heap guarantees the candidate's completeness (i.e., all the k-NNTs are included), and reduces the computational overhead of candidate verification. In addition, we propose a qualifier expectation measure that ranks partial-matching candidate trajectories to accelerate query processing in the cases of non-uniform trajectory distributions or outlier query locations. Extensive experiments on both real and synthetic trajectory datasets demonstrate the feasibility and effectiveness of proposed methods.

Original languageEnglish (US)
Title of host publicationAdvances in Spatial and Temporal Databases - 12th International Symposium, SSTD 2011, Proceedings
Number of pages19
StatePublished - 2011
Event12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011 - Minneapolis, MN, United States
Duration: Aug 24 2011Aug 26 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6849 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other12th International Symposium on Advances in Spatial and Temporal Databases, SSTD 2011
Country/TerritoryUnited States
CityMinneapolis, MN

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Retrieving k-nearest neighboring trajectories by a set of point locations'. Together they form a unique fingerprint.

Cite this