Spatial Data Structures for Efficient Trajectory-Based Queries

Jeremy Martin Kubica, Andrew Moore, Andrew J. Connolly, and Robert Jedicke
tech. report CMU-RI-TR-04-61, Robotics Institute, Carnegie Mellon University, December, 2004


Download
  • Adobe portable document format (pdf) (511KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract
Spatial queries involving trajectories of moving objects are fundamental in a variety of domains. For example, we may wish to determine which points or regions to which an object passes "close." In this paper, we consider a large-scale version of this type of problem. Given many trajectories and spatial regions, we want to efficiently find all pairs of regions and trajectories such that the trajectory passes through the region.

Below we present several data structures and algorithms to efficiently solve this problem. We adapt data structures and algorithms from tracking and computer graphics to work on higher dimensional data sets with nonlinear tracks. These algorithms provide a significant speedup over a simple brute force approach. We also introduce a new data structure and algorithm that can significantly outperform previous approaches for queries with many tracks. Further, we introduce a novel dual-tree approach that combines the advantages of both an observation-based data structure and a track-based data structure to provide consistently good performance over a wide range of queries.


Notes
Associated Lab(s) / Group(s): Auton Lab
Associated Project(s): Auton Project
Number of pages: 23

Text Reference
Jeremy Martin Kubica, Andrew Moore, Andrew J. Connolly, and Robert Jedicke, "Spatial Data Structures for Efficient Trajectory-Based Queries," tech. report CMU-RI-TR-04-61, Robotics Institute, Carnegie Mellon University, December, 2004

BibTeX Reference
@techreport{Kubica_2004_4832,
   author = "Jeremy Martin Kubica and Andrew Moore and Andrew J Connolly and Robert Jedicke",
   title = "Spatial Data Structures for Efficient Trajectory-Based Queries",
   booktitle = "",
   institution = "Robotics Institute",
   month = "December",
   year = "2004",
   number= "CMU-RI-TR-04-61",
   address= "Pittsburgh, PA",
}