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 volume of spatial-textual data generated from check-ins and reviews facilitates many practical applications. In these applications, similarity joins are the basic operation which further supports a wide range of similarity queries. However, this compute-intensive join operation calls for more efficient and effective algorithm to support real-time queries. Exploiting general purpose GPUs (GPGPUs) is one natural solution. Nevertheless, existing join algorithms utilizing GPGPU lack considerations on unique features of spatial-textual trajectories, especially the textual domain, thus resulting in poor performance. In this paper, we first propose a baseline spatial-textual trajectory similarity join algorithm, which is essentially based on a traditional algorithm for relational joins on GPGPUs. Then, by analyzing the bottleneck of this baseline, we further develop a fine-grained join algorithm which consists of memory access techniques and optimizations. We propose a strategy of flip to ensure coalesced memory accesses, and a batch scheduler for dividing the whole task into batches to fit the global memory while alleviating imbalanced throughput. Extensive experiments have been conducted over real-life datasets and the results show that our fine-grained algorithm performs the best and reduces the latency effectively.