Accelerating fine-grained spatial-Textual trajectory similarity joins with GPGPUs

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.