MDTK: Bandwidth-saving framework for distributed top-k similar trajectory query

During the past decade, with the popularity of smartphones and other mobile devices, big trajectory data is generated and stored in a distributed way. In this work, we focus on the DTW distance based top-k query over the distributed trajectory data. Processing such a query is challenging due to the limited network bandwidth and the computation overhead. To overcome these challenges, we propose a communication-saving framework MDTK (Multi-resolution based Distributed Top-K). MDTK sends the bounding envelopes of the reference trajectory from coarse to finer-grained resolutions and devises a level-increasing communication strategy to gradually tighten the proposed upper and lower bound. Then, distance bound based pruning strategies are imported to reduce both the computation and communication cost. Besides, we embed techniques including: indexing, early-stopping and cascade pruning, to improve the query efficiency. Extensive experiments on real datasets show that MDTK outperforms the state-of-the-art method.