An Index for Moving Objects with Constant-Time Access to their Compressed
Trajectories
Nieves Brisaboa, Adrián Gómez-Brandón, Travis Gagie,
Gonzalo Navarro, and José Paramá
As the number of vehicles and devices equipped with GPS
technology has grown explosively, an urgent need has arisen for time- and
space-efficient data structures to represent their trajectories. The most
commonly desired queries are the following: queries about an object's
trajectory, range queries and nearest neighbor queries. In this paper we
consider that the objects can move freely and we present a new compressed data
structure for storing their trajectories, based on a combination of logs and
snapshots, with the logs storing sequences of the objects' relative movements
and the snapshots storing their absolute positions sampled at regular time
intervals. We call our data structure ContaCT because it provides
Constant-time access to Compressed Trajectories. Its logs are based on a compact partial-sums data structure that returns cumulative displacement in constant time, and allows us to compute in constant time any object's position at any instant, enabling a speedup when processing several other queries. We have compared ContaCT experimentally with another compact data structure for trajectories, called GraCT, and with
a classic spatio-temporal index, the MVR-tree. Our results show that ContaCT outperforms the MVR-tree
by orders of magnitude in space and also outperforms the compressed representation in time performance.