VID Join: Mapping Trajectories to Points of Interest to Support Location-Based Services

Variable Influence Duration (VID) join is a novel spatio-temporal join operation between a set T of trajectories and a set P of spatial points. Here, trajectories are traveling history of moving objects (e.g., travelers), and spatial points are POIs (e.g., restaurants). VID join returns all pairs of (τ_s, p) if τ_s is spatially close to p for a long period of time, where τ_s is a segment of trajectory τ∈T and p∈P. Each returned (τ_s, p) implies that the moving object associated with τ_s stayed at p (e.g., having dinner at a restaurant). Such information is useful in many aspects, such as targeted advertising, social security, and social activity analysis. The concepts of influence and influence duration are introduced to measure the spatial closeness between τ_s and p, and the time spanned, respectively. Compared to the conventional spatio-temporal join, the VID join is more challenging since the join condition varies for different POIs, and the additional temporal requirement cannot be indexed effectively. To process the VID join efficiently, three algorithms are developed and several optimization techniques are applied, including spatial duplication reuse and time duration based pruning. The performance of the developed algorithms is verified by extensive experiments on real spatial data.