Collectively Simplifying Trajectories in a Database: A Query Accuracy Driven Approach

Abstract—Increasing and massive volumes of trajectory
data are being accumulated that may serve a variety of
applications, such as mining popular routes or identifying
ridesharing candidates. As storing and querying massive
trajectory data is costly, trajectory simplification techniques
have been introduced that intuitively aim to reduce the
sizes of trajectories, thus reducing storage and speeding up
querying, while preserving as much information as possible.
Existing techniques rely mainly on hand-crafted error measures when deciding which point to drop when simplifying
a trajectory. While the hope may be that such simplification
affects the subsequent usability of the data only minimally,
the usability of the simplified data remains largely unexplored. Instead of using error measures that indirectly may to
some extent yield simplified trajectories with high usability,
we adopt a direct approach to simplification and present the
first study of query accuracy driven trajectory simplification,
where the direct objective is to achieve a simplified trajectory
database that preserves the query accuracy of the original
database as much as possible. Specifically, we propose a multiagent reinforcement learning based solution with two agents
working cooperatively to collectively simplify trajectories
in a database while optimizing query usability. Extensive
experiments on four real-world trajectory datasets show that
the solution is capable of consistently outperforming baseline
solutions over various query types and dynamics.
Index Terms—trajectory data, trajectory simplification,
query processing, reinforcement learning