臺灣博碩士論文加值系統

With the advance of location positioning technology and some geo-Web services (e.g., EveryTrail), users can easily use mobile Apps to record their travel experiences via photos and trip trajectories. Prior works have elaborated on trip planning in mining travel routes from a huge number of trajectories. However, most of the travel routes mined may have some overlapping Regions-Of-Interest (ROIs) information, which incur some redundant travel information. Moreover, each ROI may have its appropriate visiting time, and users may also have their own preferred must-see ROIs (referred to as a set of query points). The above two factors are not considered in prior works. Thus, in this paper, given a spatial range $Q$ and a set of query points specified by users, the goal of this paper is to return the travel routes that fulfill two requirements: 1.) travel routes should contain all those query points specified, and 2.) travel routes should be within the spatial range Q. Furthermore, we claim that each query point may have its proper visiting time. As such, the travel routes should go through these query points at their corresponding proper visiting time. To avoid some redundant information in the travel routes, we utilize the skyline concept to retrieve travel routes with more diversity. Specifically, in our paper, we consider some factors, such as the visiting time information of POIs and the set of query points, in retrieving travel routes. These factors could be mapped into dimensional spaces. Then, each travel route is viewed as a data point in the dimensional space. Thus, skyline data points (referred to as skyline travel routes) are returned as the query result. To evaluate our proposed methods, we conducted extensive experiments on real datasets. The experimental results show that skyline travel routes indeed provide more diversity in the query result. In addition, we evaluate the efficiency of retrieving skyline travel routes.

With the advance of location positioning technology and some geo-Web services (e.g., EveryTrail), users can easily use mobile Apps to record their travel experiences via photos and trip trajectories. Prior works have elaborated on trip planning in mining travel routes from a huge number of trajectories. However, most of the travel routes mined may have some overlapping Regions-Of-Interest (ROIs) information, which incur some redundant travel information. Moreover, each ROI may have its appropriate visiting time, and users may also have their own preferred must-see ROIs (referred to as a set of query points). The above two factors are not considered in prior works. Thus, in this paper, given a spatial range $Q$ and a set of query points specified by users, the goal of this paper is to return the travel routes that fulfill two requirements: 1.) travel routes should contain all those query points specified, and 2.) travel routes should be within the spatial range Q. Furthermore, we claim that each query point may have its proper visiting time. As such, the travel routes should go through these query points at their corresponding proper visiting time. To avoid some redundant information in the travel routes, we utilize the skyline concept to retrieve travel routes with more diversity. Specifically, in our paper, we consider some factors, such as the visiting time information of POIs and the set of query points, in retrieving travel routes. These factors could be mapped into dimensional spaces. Then, each travel route is viewed as a data point in the dimensional space. Thus, skyline data points (referred to as skyline travel routes) are returned as the query result. To evaluate our proposed methods, we conducted extensive experiments on real datasets. The experimental results show that skyline travel routes indeed provide more diversity in the query result. In addition, we evaluate the efficiency of retrieving skyline travel routes.

1 Introduction 1
2 Framework Overview 8
3 O-Line Pattern Discovery and scoring Mo dule 11
3.1 Determining the attractiveness scores of tra jectories . . . . . . 11
3.2 Prop er visiting time decision . . . . . . . . . . . . . . . . . . . 13
4 on-line exploring skyline travel routes mo dule 17
4.1 Sewing Query Points into Tra jectories (SQPT) . . . . . . . . . 18
4.1.1 Matched pair decision . . . . . . . . . . . . . . . . . . 18
4.1.2 Decision of the ROI order . . . . . . . . . . . . . . . . 20
4.2 Skyline Travel Routes search . . . . . . . . . . . . . . . . . . . 21
5 Tra jectory Reconstruction 24
6 Exp eriments 29
6.1 Visiting time accuracy . . . . . . . . . . . . . . . . . . . . . . 29
6.2 Evaluation of aggregating query p oints to existing tra jectories 32
6.3 Result of skyline travel route and eciency . . . . . . . . . . . 34
6.4 Results of Tra jectory Reconstruction . . . . . . . . . . . . . . 36
6.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Bibliography 39

[1] Z. Chen, H. T. Shen, X. Zhou, Y. Zheng, and X. Xie, Searching trajectories by lo cations: an eciency study. in SIGMOD Conference, 2010,
pp. 255266.
[2] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi, Tra jectory pattern mining, in Proceedings of the 13th ACM SIGKDD International Conference on Know ledge Discovery and Data Mining (SIGKDD) , 2007,pp. 330339.
[3] V. S. Tseng, E. H.-C. Lu, and C.-H. Huang, Mining temp oral mobile sequential patterns in lo cation-based service environments, in Proceedings of the 13th International Conference on Paral lel and Distributed Systems (ICPADS) , 2007, pp. 18.
[4] H.-P. Tsai, D.-N. Yang, W.-C. Peng, and M.-S. Chen, Exploring group moving pattern for an energy-constrained ob ject tracking sensor network, in Proceedings of the 11th Pacic-Asia Conference on Know ledge Discovery and Data Mining (PAKDD) , 2007, pp. 825832.
[5] Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W.-Y. Ma, Mining user similarity based on lo cation history, in Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (GIS) , 2008, pp. 298307.
[6] H. Jeung, Q. Liu, H. T. Shen, and X. Zhou, A hybrid prediction model for moving ob jects, in Proceedings of the 24th IEEE International Conference on Data Engineering (ICDE) , 2008, pp. 7079.
[7] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma, Mining interesting locations and travel sequences from gps tra jectories for mobile users, in Proceedings of the 18th International Conference on World Wide Web (WWW) , 2009, pp. 791800.
[8] K. Zheng, S. Shang, N. J. Yuan, Y. Yang, and U. Computing, Towards efficient search for activity trajectories. ICDE, 2013.
[9] X. Cao, G. Cong, and C. S. Jensen, Mining signicant semantic lo cations from gps data, Proceedings of the VLDB Endowment, vol. 3, no.
1-2, pp. 10091020, 2010.
[10] Y. Arase, X. Xie, T. Hara, and S. Nishio, Mining p eople's trips from large scale geo-tagged photos, in Proceedings of the international conference on Multimedia. ACM, 2010, pp. 133142.
[11] D. J. Crandall, L. Backstrom, D. Huttenlo cher, and J. Kleinb erg, Mapping the world's photos, in Proceedings of the 18th international conference on World wide web. ACM, 2009, pp. 761770.
[12] L.-Y. Wei, W.-C. Peng, B.-C. Chen, and T.-W. Lin, Pats: A framework of pattern-aware tra jectory search, in Mobile Data Management (MDM), 2010 Eleventh International Conference on. IEEE, 2010, pp.
372377.
[13] M. Ye, P. Yin, W.-C. Lee, and D.-L. Lee, Exploiting geographical inuence for collab orative p oint-of-interest recommendation, in Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. ACM, 2011, pp. 325334.
[14] H.-P. Hsieh, C.-T. Li, and S.-D. Lin, Exploiting large-scale check-in data to recommend time-sensitive routes, in Proceedings of the ACM SIGKDD International Workshop on Urban Computing. ACM, 2012, pp. 5562.
[15] X. Lu, C. Wang, J.-M. Yang, Y. Pang, and L. Zhang, Photo2trip: generating travel routes from geo-tagged photos for trip planning, in Proceedings of the international conference on Multimedia. ACM, 2010,pp. 143152.
[16] D. Papadias, Y. Tao, G. Fu, and B. Seeger, An optimal and progressive algorithm for skyline queries, in Proceedings of the 2003 ACM SIGMOD international conference on Management of data. ACM, 2003, pp. 467-478.
[17] S. Borzsony, D. Kossmann, and K. Sto cker, The skyline op erator, in Data Engineering, 2001. Proceedings. 17th International Conference on. IEEE, 2001, pp. 421430.
[18] D. Kossmann, F. Ramsak, and S. Rost, Sho oting stars in the sky: An online algorithm for skyline queries, in Proceedings of the 28th interna-tional conference on Very Large Data Bases. VLDB Endowment, 2002, pp. 275286.
[19] K.-L. Tan, P.-K. Eng, B. C. Ooi et al. , Efficient progressive skyline computation, in VLDB , vol. 1, 2001, pp. 301310.
[20] D. Comaniciu and P. Meer, Mean shift: A robust approach toward feature space analysis, Pattern Analysis and Machine Intel ligence, IEEE Transactions on, vol. 24, no. 5, pp. 603619, 2002.