|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(s) / Group(s):
Associated Project(s): Auton Project
Number of pages: 23
|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, November, 2004|
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 = "November",
year = "2004",
address= "Pittsburgh, PA",
|The Robotics Institute is part of the School of Computer Science, Carnegie Mellon University.|
Contact Us | Update Instructions