Indexing Future Trajectories of Moving Objects in a Constrained Network

Advances in wireless sensor networks and positioning technologies enable newapplications monitoring moving objects. Some of theseapplications, such as traffic management, require the possibilityto query the future trajectories of the objects. In this paper,we propose an original data access method, the ANR-tree, which supports predictivequeries. We focus on real life environments, where the objects movewithin constrained networks, such as vehicles on roads. We introduce asimulation-based prediction model based on graphs of cellular automata,which makes full use of the network constraints and the stochastictraffic behavior. Our technique differs strongly from the linearprediction model, which has low prediction accuracy and requiresfrequent updates when applied to real traffic with velocity changingfrequently. The data structure extends the R-tree with adaptive unitswhich group neighbor objects moving in the similar moving patterns. Thepredicted movement of the adaptive unit is not given by a singletrajectory, but instead by two trajectory bounds based ondifferent assumptions on the traffic conditions and obtained fromthe simulation. Our experiments, carried on two differentdatasets, show that the ANR-tree is essentially one order ofmagnitude more efficient than the TPR-tree, and is much more scalable.