Trajectory structure-based moving object hotspots discovery

doi:10.11772/j.issn.1001-9081.2017.01.0054

Abstract

Abstract: Focused on the issue that the existing algorithms are unable to accurately detect active hotspots from trajectory data, a novel Trajectory Structure-based Hotspots discovery (TS_HS) algorithm was proposed. TS_HS consisted of the following two algorithms:Candidate Hotspots Discovery (CHSD) algorithm and Hotspots Filter (HSF) algorithm. First, trajectory dense regions were detected by the grid based clustering method CHSD as candidate hotspots. Second, the active hotspots region of moving objects were filtered by using HSF algorithm according to moving feature and time-varying characteristic of trajectories. The experiments on the Geolife dataset show that TS_HS is an effective solution for multi-density active hotspot problem, compared with Global Density threshold based Hot Region discovery (GD_HR) and Spatio-temporal Hot Spot Region Discovering (SDHSRD). The simulation results show that the proposed framework can detect active hotspots effectively based on the structure feature and time-varying characteristic of trajectory.

Key words: moving object, trajectory structure, hotspot, trajectory data, data mining

摘要： 针对现有热点区域发现算法难以从轨迹数据集中准确识别活动热点的问题，提出了基于轨迹结构的热点区域发现框架（TS_HS）。TS_HS由候选区域发现（CHSD）算法和热点区域过滤（HSF）算法组成。首先，使用基于网格相对密度的CHSD识别空间上的轨迹密集区域作为候选热点区域；然后，利用HSF根据候选区域中轨迹的活动特征和时间变化特征，筛选出移动对象活动频繁的热点区域。在Geolife数据集上进行的实验表明，与基于全局密度的热门区域发现算法（GD_HR）以及移动轨迹时空热点区域发现算法（SDHSRD）相比，TS_HS能更有效地解决多密度热点区域的识别问题。实验结果表明，TS_HS能够根据轨迹的活动特征准确发现移动对象的活动热点区域。

关键词: 移动对象, 轨迹结构, 热点区域, 轨迹数据, 数据挖掘

CLC Number:

TP391.4

LYU Shaoqian, MENG Fanrong, YUAN Guan. Trajectory structure-based moving object hotspots discovery[J]. Journal of Computer Applications, 2017, 37(1): 54-59.

吕绍仟, 孟凡荣, 袁冠. 基于轨迹结构的移动对象热点区域发现[J]. 计算机应用, 2017, 37(1): 54-59.

References

[1] WEI W, QI Y. Information potential fields navigation in wireless Ad-Hoc sensor networks[J]. Sensors, 2011, 11(5):4794-4807.
[2] WEI W, XU Q, WANG L, et al. GI/Geom/1 queue based on communication model for mesh networks[J]. International Journal of Communication Systems, 2014, 27(11):3013-3029.
[3] WEI W, YANG X L, SHEN P Y, et al. Holes detection in anisotropic sensornets:topological methods[J]. International Journal of Distributed Sensor Networks, 2012, 8(10):135054.
[4] SONG H, BRANDT-PEARCE M. A 2-D discrete-time model of physical impairments in wavelength-division multiplexing systems[J]. Journal of Lightwave Technology, 2012, 30(5):713-726.
[5] SONG H, BRANDT-PEARCE M. Range of influence and impact of physical impairments in long-haul DWDM systems[J]. Journal of Lightwave Technology, 2013, 31(15):846-854.
[6] SONG H, BRANDT-PEARCE M. Model-centric nonlinear equalizer for coherent long-haul fiber-optic communication systems[C]//GLOBECOM 2013:Proceedings of the 2013 IEEE Global Communications Conference. Piscataway, NJ:IEEE, 2013:2394-2399.
[7] JEUNG H, LIU Q, SHEN H T, et al. A hybrid prediction model for moving objects[C]//Proceedings of the 2008 IEEE International Conference on Data Engineering. Piscataway, NJ:IEEE, 2008:70-79.
[8] YANG J, HU M. TrajPattern:mining sequential patterns from imprecise trajectories of mobile objects[M]//EDBT 2006:Proceedings of the 10th International Conference on Extending Database Technology, LNCS 3896. Berlin:Springer, 2006:664-681.
[9] KAMI N, ENOMOTO N, BABA T, et al. Algorithm for detecting significant locations from raw GPS data[C]//Proceedings of the 2010 International Conference on Discovery Science. Berlin:Springer, 2010:221-235.
[10] ZHENG Y, ZHANG L, XIE X, et al. Mining interesting locations and travel sequences from GPS trajectories[C]//WWW 2009:Proceedings of the 18th International Conference on World Wide Web. New York:ACM, 2009:791-800.
[11] CAO X, CONG G, JENSEN C S. Mining significant semantic locations from GPS data[J]. Proceedings of the VLDB Endowment, 2010, 3(1):1009-1020.
[12] ZHOU C, FRANKOWSKI D, LUDFORD P, et al. Discovering personally meaningful places:an interactive clustering approach[J]. ACM Transactions on Information Systems, 2007, 25(3):1-31.
[13] KHETARPAUL S, CHAUHAN R, GUPTA S K, et al. Mining GPS data to determine interesting locations[C]//Proceedings of the 8th International Workshop on Information Integration on the Web:in Conjunction with WWW 2011. New York:ACM, 2011:1-6.
[14] GIANNOTTI F, NANNI M, PINELLI F, et al. Trajectory pattern mining[C]//KDD' 07 Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2007:330-339.
[15] 刘奎恩,肖俊超,丁治明,等.轨迹数据库中热门区域的发现[J].软件学报,2013,24(8):1816-1835.(LIU K E, XIAO J C, DING Z M, et al. Discovery of hot region in trajectory databases[J]. Journal of Software, 2013, 24(8):1816-1835.)
[16] 袁冠,夏士雄,张磊,等.基于结构相似度的轨迹聚类算法[J].通信学报,2011,32(9):103-110.(YUAN G, XIA S X, ZHANG L, et al. Trajectory clustering algorithm based on structural similarity[J]. Journal on Communications, 2011, 32(9):103-110.)
[17] 袁冠.移动对象轨迹数据挖掘方法研究[D].徐州:中国矿业大学,2012:39-59.(YUAN G. Research on the mining methods of trajectory data for moving objects[D]. Xuzhou:China University of Mining and Technology, 2012:39-59.)
[18] HADJIELEFTHERIOU M, KOLLIOS G, GUNOPULOS D, et al. On-line discovery of dense areas in spatio-temporal databases[C]//Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases. Berlin:Springer, 2003:306-324.
[19] JENSEN C S, LIN D, OOI B C, et al. Effective density queries on continuously moving objects[C]//Proceedings of the 22nd International Conference on Data Engineering. Piscataway, NJ:IEEE, 2006:71-71.
[20] VERHEIN F, CHAWLA S. Mining spatio-temporal association rules, sources, sinks, stationary regions and thoroughfares in object mobility databases[C]//Proceedings of the 2010 International Conference on Database Systems for Advanced Applications. Berlin:Springer, 2010:187-201.
[21] ASHBROOK D, STARNER T. Using GPS to learn significant locations and predict movement across multiple users[J]. Personal & Ubiquitous Computing, 2003, 7(5):275-286.
[22] PALMA A T, BOGORNY V, KUIJPERS B, et al. A clustering-based approach for discovering interesting places in trajectories[C]//SAC' 08:Proceedings of the 2008 ACM Symposium on Applied Computing. New York:ACM, 2008:863-868.
[23] LIAO L, PATTERSON D J, FOX D, et al. Building personal maps from GPS data[J]. Annals of the New York Academy of Sciences, 2006, 1093(1):249-65.
[24] LIAO L, FOX D, KAUTZ H. Extracting places and activities from GPS traces using hierarchical conditional random fields[J]. International Journal of Robotics Research, 2007, 26(1):119-134.
[25] ALVARES L O, BOGORNY V, KUIJPERS B, et al. A model for enriching trajectories with semantic geographical information[C]//GIS' 07:Proceedings of the 15th Annual ACM International Symposium on Advances in Geographic Information Systems. New York:ACM, 2007:Article No. 22.
[26] CHENG G Q. Clustering algorithm for multi-density based on grid relative density[J]. Computer Engineering & Applications, 2009, 45(1):156-158.
[27] 王亮,胡琨元,库涛,等.随机采样移动轨迹时空热点区域发现及模式挖掘[J].吉林大学学报:工学版,2015,45(3):913-920.(WANG L, HU K Y, KU T, et al. Discovering spatiotemporal hot spot region and mining patterns from moving trajectory random sampling[J]. Journal of Jilin University Engineering and Technology Edition, 2015, 45(3):913-920.)