Spatial Data Structures for Efficient Trajectory-Based Queries

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.