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

作　　者：商烁 谢珂心 郑凯 刘家俊 文继荣 

机构地区：[1]Department of Computer Science, China University of Petroleum, Beijing 102249, China [2]School of Information Technology and Electrical Engineering, The University of Queensland Brisbane, QLD 4072, Australia [3]School of Computer Science and Technology, Soochow University, Suzhou 215006, China [4]Commonwealth Scientific and Industrial Research Organisation, Kenmore, QLD 4069, Australia [5]Key Laboratory of Data Engineering and Knowledge Engineering, Renmin University of China, Beijing 100080, China

出　　处：《Journal of Computer Science & Technology》2015年第4期725-744,共20页计算机科学技术学报（英文版）

基　　金：This work is partly supported by the National Natural Science Foundation of China under Grant No. 61402532, the Science Foundation of China University of Petroleum （Beijing） under Grant No. 2462013YJRC031, and the Excellent Talents of Beijing Program under Grant No. 2013D009051000003.

摘　　要：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 histories of moving objects （e.g., travelers）, and spatial points are points of interest （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 τ 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 e？ciently, 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.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 histories of moving objects （e.g., travelers）, and spatial points are points of interest （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 τ 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 e？ciently, 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.

关 键 词：TRAJECTORY spatial database spatial join spatio-temporal join 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论] TP393[自动化与计算机技术—计算机科学与技术]