Spatial Data Structures for Efficient Trajectory-Based Queries
by Jeremy Kubica, Andrew Moore, Andrew Connolly, and Robert Jedicke
BibTeX:
@techreport{kubica_2004_0461,
author = "Jeremy Kubica and Andrew Moore and Andrew 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"
}
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.
- Download PDF