Advanced GPU Query

Performing similarity analysis on trajectories consisting of massive numbers of tracking points is computationally challenging. We introduce a progressive minimum bounding rectangle (MBR) and minimum distance (MINDIST) approach to process K Best Connected Trajectory (K-BCT) query which aims to find the top K similarity trajectories to a given query trajectory. Our approach has three unique features to speed up the query:
1. Progressive Minimum Bounding Rectanges (MBRs)
2. Grid-Based Search method
3. Many-core computing power of GPU

Power of GPU

This approach further leverages the many-core computing power of Graphical Processing Unit (GPU) devices to perform the query in a parallel manner. Preliminary results indicate that a) parallel computing has greatly improved the efficiency of the query and b) our optimized approach can further speedup the computation compared to parallel implementations.

Progressive MBRs

This approach builds a series of progressive MBRs from the query trajectory to determine the order of reference trajectories to identify the target top K reference trajectories at an earlier stage.

Grid-based Searching

This method introduces a grid-based search method to speed up the matched point detection between two trajectories for similarity measures.