An Efficient Algorithm Supporting Batch Trajectory Similarity Query Processing

Trajectory similarity query processing is one of the hot issues in the field of trajectory data analysis, and it is widely used in many aspects. In a large-scale online system, a large number of trajectory similarity queries request may be received in a short period of time. An excellent batch processing algorithm is urgently needed to reduce system load and improve throughput. At present, the studies on batch trajectory similarity query processing lacks consideration of the similarity between query trajectories in query grouping, which cannot meet the needs of high-throughput trajectory similarity query processing. In response to the above problems, a series of new query processing methods are proposed in this paper, which follow two steps of filtering and verification. First, a new index supporting Accelerated Trajectory Query (ATQ) is proposed to effectively filter useless trajectories. Second, on the basis of the ATQ index, we propose a Batch Query Trajectory Grouping (BQTG) algorithm. BQTG divides the received queries into several groups. Queries in the same group have high similarity and can share intermediate results as much as possible. Then, a Basic Algorithm for Batch Trajectory Similarity Query Processing( BABTSQP) is proposed. In each group, BABTSQP continuously selects the main query, which can share lots of intermediate results to answer other queries in the group and reduce many calculations. We also propose an Optimization Algorithm for Batch Trajectory Similarity Query Processing(OABTSQP), which preferentially calculates the trajectories that are close to the query trajectories in the group, so as to obtain a better threshold and achieve a better pruning effect. Finally, the effectiveness of the proposed BABTSQP and OABTSQP algorithms is verified through lots of experiments.