Graphics enhanced version of this site

Spatial Data Structures for Efficient Trajectory-Based Queries
J.M. Kubica, A. Moore, A.J. Connolly, and R. Jedicke
tech. report CMU-RI-TR-04-61, Robotics Institute, Carnegie Mellon University, November, 2004.

Jump to: Download | Abstract | Notes | Text Reference | BibTeX Reference

Adobe portable document format (pdf) [510 KB]
Compressed postscript (ps.gz) [278 KB]

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.

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.

Associated lab/group: Auton Lab
Associated project: Auton Project

Number of pages: 23

J.M. Kubica, A. Moore, A.J. Connolly, and R. Jedicke, Spatial Data Structures for Efficient Trajectory-Based Queries, tech. report CMU-RI-TR-04-61, Robotics Institute, Carnegie Mellon University, November, 2004.

@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",
   institution = "Robotics Institute, Carnegie Mellon University",
   month = "November",
   year = "2004",
   number = "CMU-RI-TR-04-61",
   address = "Pittsburgh, PA"
}