The increasing amount of trajectory data facilitates a wide spectrum of practical applications in which large numbers of trajectory range and similarity queries are issued continuously. This calls for high-throughput trajectory query processing. Traditional in-memory databases lack considerations of the unique features of trajectories, while specialized trajectory query processing systems are typically designed for only one type of trajectory queries. This paper introduces GAT, a unified GPU-accelerated framework to process batch trajectory queries with the objective of high throughput. GAT follows the filtering-and-verification paradigm where we develop a novel index GTIDX for effectively filtering invalid trajectories on the CPU, and exploit the massive parallelism of the GPU for verification. To optimize the performance of GAT, we first greedily partition batch queries to reduce the amortized query processing latency. We then apply the Morton-based encoding method to coalesce data access requests from the GPU cores, and maintain a hash table to avoid redundant data transfer between CPU and GPU. To achieve load balance, we group size-varying cells into balanced blocks with similar numbers of trajectory points. Extensive experiments have been conducted over real-life trajectory datasets. The results show that GAT is efficient, scalable, and achieves high throughput with acceptable indexing cost.

The increasing amount of trajectory data facilitates a wide spectrum of practical applications. In many such applications, large numbers of trajectory range and similarity queries are issued continuously, which calls for high-throughput trajectory query processing. Traditional in-memory databases lack considerations of the unique features of trajectories, thus suffering from inferior performance. Existing trajectory query processing systems are typically designed for only one type of trajectory queries, i.e., either range or similarity query, but not for both. Inspired by the massive parallelism on GPUs, in this paper, we develop a GPU-accelerated framework, named GAT, to support both types of trajectory queries (i.e., both range and similarity queries) with high throughput. For similarity queries, we adopt the Edit Distance on Real sequence (EDR) as the similarity measure which is accurate and robust to noise in real-world trajectories. GAT employs a GPU-friendly index called GTIDX to effectively filter invalid trajectories for both range and similarity queries, and exploits the GPU to perform parallel verifications. To accelerate the verification process on the GPU, we apply the Morton-based encoding method to reorganize trajectory points and facilitate coalesced data accesses for individual point data in global memory, which reduces the global memory bandwidth requirement significantly. We also propose a technique of grouping size-varying cells into balanced blocks with similar numbers of trajectory points, to achieve load balancing among the Streaming Multiprocessors (SMs) of the GPU. We conduct extensive experiments to evaluate the performance of GAT using two real-life trajectory datasets. The results show that GAT is scalable and achieves high throughput with acceptable indexing cost.