臺灣博碩士論文加值系統

隨著全球定位系統 (GPS) 應用的普及，許多行動社群應用程式被開發，
人們可以利用這些社群應用程式分享所在的地點、拍攝的相片或活動資訊
至社群網站。舉例來說，人們可以利用 GPS 軌跡記錄出遊的行程，也可以
透過 Check-in 應用程式分享所拜訪過的地點。然而這些資料都包含了時間
和空間的資訊，這些使用者產生的時空資料可以形成所謂的軌跡資料。在
論文中，我們研究如何從軌跡資料中找出模式，提出相關的演算法，應用
於旅行規劃和交通分析。
目前與旅行規劃相關的研究主要從使用者分享的軌跡資料找出
Regions-of-interest (ROIs) 和旅遊路線，然而，人們規劃旅遊行程時會有不
同的偏好，因此，在論文中，我們針對使用者查詢的空間範圍和使用者的
廣度旅遊偏好或深度旅遊偏好，從現有軌跡資料中，根據不同偏好的分數，
推薦分數高的軌跡。除此，我們也提出一個有效率的線上軌跡搜尋演算法。
事實上，因為社群應用程式的特性或省電考量，使用者所分享的軌跡有些
是由較低的採樣頻率所產生，這使得軌跡中連續兩個採樣點中間的路線是
不明確的。因此，我們進一步提出可應用在旅行規劃的路線推導架構。從
這些具不確性的軌跡資料中，找出熱門的旅遊路線。當使用者查詢一些地
點和給定的空閒時間，這個架構會找出符合時間內且經過這些地點的熱門
路線。
在論文中，我們進一步利用使用者分享的軌跡資料，提出相關的路況預
估演算法。當使用者查詢一路段在某個時間的路況時，我們可以預估被查
詢路段在該時間的可能行車速度值。然而，使用者不一定都會即時分享當下的軌跡資料，因此，我們希望從歷史軌跡資料中找出時空特徵，結合即
時和歷史軌跡資料進而有效的預估車速。除此，我們可以假設，地圖上的
每一塊區域可以看成一個靜態的感測器，偵測使用者所分享的資料，這些
感測器將感測到隨著時間變化的資料串流。為了可以有效的找出時空特徵，
我們也另外發展空間資料串流的分群演算法，可應用於交通分析，找出哪
些區域在特定時間上具有相關的路況。
在本論文中，藉由使用者分享的軌跡資料，我們提出軌跡搜尋架構和路
線推導架構且可應用於旅行規劃，除此，我們還提出路況預測和分析的相
關演算法，在實驗中，我們利用真實資料和模擬資料驗證演算法的有效性
和效能。

The increasing availability of location-acquisition technology, such as GPS, leads to various mobile social applications, and thus people can share their locations, photos, and activities in socialWebs. For example, people can record and share their trips on the Web by GPS tracks or people can perform check-in services to share their visited locations. In fact, the user-generated spatio-temporal data could be viewed as trajectories. In this dissertation, we study how to explore patterns and propose algorithms from trajectories for pattern-aware trip planning and traffic analysis. Prior studies on trip planning have developed algorithms for mining regions-ofinterest (ROIs) and travel routes from user-generated trajectories. However, while planning trips, people have differen preferences. In the dissertation, given a spatial range and a user-specified preference of depth/breadth, we first develop a pattern-aware trajectory
search framework (PATS) to retrieve the top K trajectories passing through popular ROIs. In addition, we propose an efficient bounded trajectory search algorithm (BTS) to efficiently retrieve the top K trajectories. In fact, some user-contributed trajectories
are usually generated at a low or an irregular frequency due to applications' characteristics or energy saving, leaving the routes between two consecutive points of a single trajectory uncertain (called an uncertain trajectory). We further present a route inference
framework based on collective knowledge (RICK) for trip planning. The RICK is developed to construct the popular routes from uncertain trajectories. Explicitly, given a location sequence and a time span, the RICK is able to construct the top K routes which
sequentially pass through the locations within the specified time span, by aggregating such uncertain trajectories in a mutual reinforcement way.
Moreover, in this dissertation, we propose algorithms to estimate traffic from usercontributed GPS trajectories. Given a query that indicates a query road segment and a query time, we intend to accurately estimate the traffic status (i.e., the driving speed)
on the query road segment at the query time from user-generated driving trajectories. However, the real-time traffic information may not be always acquirable or may be limited. Thus, it is a challenging issue to estimate traffic status via a limited amount
of GPS data. Note that a traffic behavior in the same time usually reflects similar patterns (referring to the temporal feature), and nearby road segments have the similar traffic behaviors (referring to the spatial feature). By exploring the temporal and spatial
features, more GPS data points are retrieved. In light of these GPS data retrieved, we exploit the weighted moving average approach to estimate traffic status on road networks. In addition, to explore spatio-temporal features from traffic data in advance, we further
introduce a novel problem of clustering spatial data streams with constraints for trafficrelated applications. Previous studies have developed a dual clustering problem for spatial data by considering similarity-connected relationships in both geographic and non-geographic domains. In fact, an area on the map could be regarded as a sensor to detect user-contributed data. For sensor data, we observe that the readings from one sensor are similar for a period, and the readings refer to temporal locality features. We propose a hierarchical-based clustering algorithm (HBC) and an incremental clustering algorithm (IC) for clustering spatial data streams with constraints.
In view of the increasing amount of user-contributed data from social media, we propose a pattern-aware trip planning framework, a framework of constructing popular routes, algorithms for traffic estimation and traffic analysis. We conduct extensive experiments
in the dissertation with real datasets and synthetic datasets. The experimental results show that our proposed frameworks and algorithms are efficient and effectiveness.

1 Introduction 1
2 Exploring Pattern-Aware Travel Routes for Trajectory Search 5
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Trajectory Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 ROI Extraction and Recommendation . . . . . . . . . . . . . . . 10
2.2.3 Trip Planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Overview of PATS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Design of Travel Behavior Exploration in PATS . . . . . . . . . . . . . . 12
2.4.1 Determination of Regions-of-Interest . . . . . . . . . . . . . . . . 13
2.4.2 Construction of User Movement Graph . . . . . . . . . . . . . . . 14
2.4.3 Algorithm AS: Attractive Score for ROIs . . . . . . . . . . . . . . 17
2.5 Design of Trajectory Search in PATS . . . . . . . . . . . . . . . . . . . . 19
2.5.1 Trajectory Score Functions . . . . . . . . . . . . . . . . . . . . . . 19
2.5.2 Algorithm BTS: Bounded Trajectory Search . . . . . . . . . . . . 21
2.5.3 Analysis of algorithm BTS . . . . . . . . . . . . . . . . . . . . . . 25
2.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.1 Dataset and Setting . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.2 Effectiveness of PATS . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6.3 Efficiency of algorithm BTS in PATS . . . . . . . . . . . . . . . . 32
2.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3 Constructing Popular Routes from Uncertain Trajectories 36
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.1 Route Planning via GPS Logs . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Trip Planning via Geo-Temporal Data . . . . . . . . . . . . . . . 40
3.2.3 Uncertain Spatio-Temporal Data . . . . . . . . . . . . . . . . . . 41
3.3 System Overview of RICK . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.1 Preliminary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.3.2 Mobile Application Scenarios . . . . . . . . . . . . . . . . . . . . 42
3.3.3 Framework . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.4 Routable Graph Construction . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.1 Trajectory Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4.2 Region Construction . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.4.3 Edge Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.5 Route Inference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.1 Route Generation . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.5.2 Route Refinement . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.6 Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
3.6.1 Datasets and Settings . . . . . . . . . . . . . . . . . . . . . . . . 56
3.6.2 Visualization of Results . . . . . . . . . . . . . . . . . . . . . . . 57
3.6.3 Performance Study . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 Exploring Spatio-Temporal Features for Traffic Estimation on Road
Networks 63
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3 Traffic Estimation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.3.1 Retrieving GPS Data Points by Temporal Feature . . . . . . . . . 64
4.3.2 Aggregating GPS Data Points by Temporal Feature . . . . . . . . 65
4.3.3 Retrieving GPS Data Points by Spatial Feature . . . . . . . . . . 66
4.3.4 Aggregating GPS Data Points from Spatial Feature . . . . . . . . 67
4.3.5 Velocity Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.4 Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5 On Clustering Spatial Data Streams with Constraints 70
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
5.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.3 Dual Clustering for Spatial Data Streams . . . . . . . . . . . . . . . . . . 77
5.3.1 Graph Representation . . . . . . . . . . . . . . . . . . . . . . . . 77
5.3.2 Hierarchical-based Clustering Algorithm . . . . . . . . . . . . . . 78
5.3.3 Incremental Clustering Algorithm . . . . . . . . . . . . . . . . . . 81
5.3.4 Analysis of Algorithm IC . . . . . . . . . . . . . . . . . . . . . . . 86
5.4 Performance Study and Analysis . . . . . . . . . . . . . . . . . . . . . . . 87
5.4.1 Synthetic Dataset Generation and Analysis . . . . . . . . . . . . . 89
5.4.2 Experimental Results on Synthetic Datasets . . . . . . . . . . . . 95
5.4.3 Experimental Results on Real Datasets . . . . . . . . . . . . . . . 103
5.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
6 Conclusions and Future Directions 108
Bibliography 110

[1] G. D. Abowd, C. G. Atkeson, J. Hong, S. Long, R. Kooper, and M. Pinkerton.
Cyberguide: a mobile context-aware tour guide. Wireless Networks, 3(5):421–433,
October 1997.
[2] C. C. Aggarwal, J. Han, J.Wang, and P. S. Yu. A framework for clustering evolving
data streams. In Proc. of the 29th International Conference on Very Large Data
Bases (VLDB), pages 81–92, September 2003.
[3] C. C. Aggarwal and P. S. Yu. On clustering massive text and categorical data
streams. Knowledge and Information Systems, 24(2):171–196, August 2010.
[4] A. J. Bagnall and G. J. Janacek. Clustering time series from arma models with
clipped data. In Proc. of the Tenth ACM International Conference on Knowledge
discovery and data mining (SIGKDD), pages 49–58, August 2004.
[5] B. Bahmani, A. Chowdhury, and A. Goel. Statistical complexity of the power
method for markov chains. Journal of Complexity, 5(2):119–143, June 1989.
[6] A. Banerjee and J. Ghosh. Scalable clustering algorithms with balancing constraints.
Data Mining and Knowledge Discovery, 13(3):365–395, November 2006.
[7] J. Beringer and E. H¨ullermeier. Online clustering of parallel data streams. Data
and Knowledge Engineering, 58(2):180–204, August 2006.
[8] Bikemap, 2010. http://www.bikemap.net.
[9] Y. bing Shi, C. an Yuan, Y. Huang, and Y. guang Wen. A method of spatial clustering
based on the combination of the spatial coordinate and attributes. In Proc.
of the Sixth International Conference on Information Systems Security(ICISS),
pages 526–529, October 2010.
[10] S. Borovkova and F. J. Permana. Modelling electricity prices by the potential
jump-diffusion. In Proc. of the Autumn School and International Conference on
Stochastic Finance (StochFin), pages 239–263, September 2004.
[11] S. Brakatsoulas, D. Pfoser, R. Salas, and C. Wenk. On map-matching vehicle
tracking data. In Proc. of the 31st International Conference on Very Large Data
Bases (VLDB), pages 853–864, September 2005.
[12] S. Brin and L. Page. The anatomy of a large-scale hypertextual web search engine.
Computer Networks and ISDN Systems, 30(1-7):107–117, April 1998.
[13] F. Cao, M. Ester, W. Qian, and A. Zhou. Density-based clustering over an evolving
data stream with noise. In Proc. of the Sixth SIAM International Conference on
Data Mining (SDM), pages 326–337, April 2006.
[14] X. Cao, G. Cong, and C. S. Jensen. Mining significant semantic locations from
gps data. The Very Large Data Bases Journal, 3(1):1009–1020, September 2010.
[15] A. Cartea and M. G. Figueroa. Pricing in electricity markets a mean reverting
jump diffusion model with seasonality. Applied Mathematical Finance, 12(4):313–
335, December 2005.
[16] Carweb, 2010. http://carweb.cs.nctu.edu.tw.
[17] L. Chen, M. T. Ozsu, and V. Oria. Robust and fast similarity search for moving
object trajectories. In Proc. of the 25th ACM International Conference on
Management of Data (SIGMOD), pages 491–502, June 2005.
[18] Z. Chen, H. T. Shen, and X. Zhou. Discovering popular routes from trajectories.
In Proc. of the 27th IEEE International Conference on Data Engineering (ICDE),
pages 900–911, April 2011.
[19] Z. Chen, H. T. Shen, X. Zhou, Y. Zheng, and X. Xie. Searching trajectories by
locations: an efficiency study. In Proc. of the 30th ACM International Conference
on Management of Data (SIGMOD), pages 255–266, June 2010.
[20] M. D. Choudhury, M. Feldman, S. Amer-Yahia, N. Golbandi, R. Lempel, and
C. Yu. Automatic construction of travel itineraries using social breadcrumbs. In Proc. of the 21st ACM conference on Hypertext and hypermedia (HT), pages 35–44,
June 2010.
[21] P. Cudr´e-Mauroux, E. Wu, and S. Madden. Trajstore: An adaptive storage system
for very large trajectory data sets. In Proc. of the 26th IEEE International
Conference on Data Engineerin (ICDE), pages 109–120, March 2010.
[22] B.-R. Dai, C.-R. Lin, and M.-S. Chen. Constrained data clustering by depth
control and progressive constraint relaxation. The Very Large Data Bases Journal,
16(2):201–217, April 2007.
[23] I. Davidson, M. Ester, and S. S. Ravi. Efficient incremental constrained clustering.
In Proc. of the 13th ACM International Conference on Knowledge Discovery and
Data Mining (SIGKDD), pages 240–249, August 2007.
[24] I. Davidson and S. S. Ravi. Clustering with constraints: Feasibility issues and the
k-means algorithm. In Proc. of the Fifth SIAM International Conference on Data
Mining (SDM), pages 138–149, April 2005.
[25] M. De Choudhury, M. Feldman, S. Amer-Yahia, N. Golbandi, R. Lempel, and
C. Yu. Constructing travel itineraries from tagged geo-temporal breadcrumbs. In
Proc. of the 19th International Conference on World Wide Web (WWW), pages
1083–1084, April 2010.
[26] C. de Fabritiis, R. Ragona, and G. Valenti. Traffic estimation and prediction based
on real time floating car data. In Proc. of the 11th International IEEE Conference
on Intelligent Transportation Systems (ITS), pages 197–203, 2008.
[27] M. Ester, H.-P. Kriegel, J. Sander, M. Wimmer, and X. Xu. Incremental clustering
for mining in a data warehousing environment. In Proc. of the 24th International
Conference on Very Large Data Bases (VLDB), pages 323–333, August 1998.
[28] Everytrail, 2009. http://www.everytrail.com/.
[29] R. Ge, M. Ester, B. J. Gao, Z. Hu, B. Bhattacharya, and B. Ben-Moshe. Joint
cluster analysis of attribute data and relationship data: The connected k-center
problem, algorithms and applications. ACM Trans. on Knowledge Discovery from
Data, 2(2):7:1–7:35, July 2008.
[30] R. Ge, M. Ester, W. Jin, and I. Davidson. Constraint-driven clustering. In Proc. of
the 13th ACM International Conference on Knowledge Discovery and Data Mining
(SIGKDD), pages 320–329, August 2007.
[31] F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining.
In Proc. of the 13th ACM International Conference on Knowledge Discovery and
Data Mining (SIGKDD), pages 330–339, August 2007.
[32] G. H. Golub and C. F. V. Loan. Matrix Computations. The John Hopkins University
Press, Maryland, 1996.
[33] H. Gonzalez, J. Han, X. Li, M. Myslinska, and J. P. Sondag. Adaptive fastest
path computation on a road network: A traffic mining approach. In Proc. of the
33rd International Conference on Very Large Data Bases (VLDB), pages 794–805,
September 2007.
[34] S. Guha, A. Meyerson, N. Mishra, R. Motwani, and L. O’Callaghan. Clustering
data streams: Theory and practice. IEEE Trans. on Knowledge and Data
Engineering, 15(3):515– 528, May 2003.
[35] L. Guo, C. Ai, X. Wang, Z. Cai, and Y. Li. Real time clustering of sensory data
in wireless sensor networks. In Proc. of the 28th IEEE International Performance
Computing and Communications Conference (IPCCC), pages 33–40, December
2009.
[36] J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann,
New York, 2000.
[37] R. Hariharan and K. Toyama. Project lachesis: parsing and modeling location histories.
In Proc. of the Third International Conference on Geographic Information
Science (GIScience), pages 106–124, October 2004.
[38] J. Huang and J. Zhang. Distributed dual cluster algorithm based on grid for sensor
streams. International Journal of Digital Content Technology and its Applications,
4(9):225–233, December 2010.
[39] C. S. Jensen, D. Lin, and B. C. Ooi. Continuous clustering of moving objects.
IEEE Trans. on Knowledge and Data Engineering, 19(9):1161–1174, September
2007.
[40] H. Jeung, Q. Liu, H. T. Shen, and X. Zhou. A hybrid prediction model for moving
objects. In Proc. of the 24th IEEE International Conference on Data Engineering
(ICDE), pages 70–79, April 2008.
[41] H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen. Discovery of convoys
in trajectory databases. In Proc. of the 34th International Conference on Very
Large Data Bases (VLDB), pages 1068–1080, August 2008.
[42] J. H. Kang, W. Welbourne, B. Stewart, and G. Borriello. Extracting places from
traces of locations. In Proc. of the Second ACM International Workshop on Wire-
less Mobile Applications and Services on WLAN Hotspots (WMASH), pages 110–
118, October 2004.
[43] V. Kavitha and M. Punithavalli. Clustering time series data stream - a literature
survey. ACM Trans. on Knowledge Discovery from Data, 8(1):289–294, April 2010.
[44] Kenting national park headquarters, taiwan, 2011. http://www.ktnp.gov.tw/.
[45] D. Klein, S. D. Kamvar, and C. D. Manning. From instance-level constraints to
space-level constraints: Making the most of prior knowledge in data clustering. In
Proc. of the 19th International Conference on Machine Learning (ICML), pages
307–314, July 2002.
[46] H.-P. Kriegel, M. Renz, M. Schubert, and A. Zuefle. Statistical density prediction
in traffic networks. In Proc. of the Eigth SIAM Conference on Data Mining (SDM),
pages 692–703, 2008.
[47] B. Kuijpers, B. Moelans, W. Othman, and A. Vaisman. Analyzing trajectories
using uncertainty and background information. In Proc. of the 11th International
Symposium on Spatial and Temporal Databases (SSTD), pages 135–152, July 2009.
[48] P. Kumar, V. Singh, and D. Reddy. Advanced traveler information system for
hyderabad city. IEEE Trans. on Intelligent Transportation Systems, 6(1):26–37,
March 2005.
[49] T. Kurashima, T. Iwata, G. Irie, and K. Fujimura. Travel route recommendation
using geotags in photo sharing sites. In Proc. of the 19th ACM International
Conference on Information and knowledge management (CIKM), pages 579–588,
October 2010.
[50] R. Lange, F. D¨urr, and K. Rothermel. Scalable processing of trajectory-based
queries in space-partitioned moving objects databases. In Proc. of the 16th ACM
SIGSPATIAL international conference on Advances in geographic information sys-
tems (GIS), pages 1–10, November 2008.
[51] J.-G. Lee, J. Han, X. Li, and H. Gonzalez. Traclass: Trajectory classification
using hierarchical region based and trajectory based clustering. In Proc. of the
34th International Conference on Very Large Data Bases (VLDB), pages 1081–
1094, August 2008.
[52] J.-G. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: a partition-and-group
framework. In Proc. of the 27th ACM International Conference on Management
of Data (SIGMOD), pages 593–604, June 2007.
[53] Q. Li, Y. Zheng, X. Xie, Y. Chen, W. Liu, and W.-Y. Ma. Mining user similarity
based on location history. In Proc. of the 16th ACM SIGSPATIAL International
Conference on Advances in Geographic Information Systems (GIS), pages 298–307,
November 2008.
[54] X. Li, J. Han, S. Kim, and H. Gonzalez. Roam: Rule- and motif-based anomaly
detection in massive moving object data sets. In Proc. of the Seventh SIAM
International Conference on Data Mining (SDM), pages 273–284, April 2007.
[55] Z. Li, B. Ding, J. Han, R. Kays, and P. Nye. Mining periodic behaviors for
moving objects. In Proc. of the 16th ACM International Conference on Knowledge
Discovery and Data Mining (SIGKDD), pages 1099–1108, July 2010.
[56] Z.-X. Liao and W.-C. Peng. Clustering spatial data with a geographic constraint:
exploring local search. Knowledge and Information Systems, 31(1):153–170,
April 2012.
[57] C.-R. Lin, K.-H. Liu, and M.-S. Chen. Dual clustering: Integrating data clustering
over optimization and constraint domains. IEEE Trans. on Knowledge and Data
Engineering, 17(5):628–637, May 2005.
[58] J. Lin, M. Vlachos, E. J. Keogh, and D. Gunopulos. Iterative incremental clustering
of time series. In Proc. of the Ninth International Conference on Extending
Database Technology (EDBT), pages 106–122, March 2004.
[59] C.-H. Lo, W.-C. Peng, C.-W. Chen, T.-Y. Lin, and C.-S. Lin. Carweb: A traffic
data collection platform. In Proc. of the Ninth International Conference on Mobile
Data Management (MDM), pages 221–222, 2008.
[60] Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y. Huang. Map-matching
for low-sampling-rate gps trajectories. In Proc. of the 17th ACM SIGSPATIAL
International Conference on Advances in Geographic Information Systems (GIS),
pages 352–361, November 2009.
[61] X. Lu, C.Wang, J.-M. Yang, Y. Pang, and L. Zhang. Photo2trip: generating travel
routes from geo-tagged photos for trip planning. In Proc. of the 18th International
Conference on Multimedea (MM), pages 143–152, October 2010.
[62] B. Mirkin. Clustering for Data Mining: A Data Recovery Approach. Taylor &
Francis, London, 2011.
[63] P. N., I. Kopanakis, E. E. Kotsifakos, E. Frentzos, and Y. Theodoridis. Clustering
trajectories of moving objects in an uncertain world. In Proc. of the Ninth
IEEE International Conference on Data Mining (ICDM), pages 417–427, December
2009.
[64] P. Newson and J. Krumm. Hidden markov map matching through noise and
sparseness. In Proc. of the 17th ACM SIGSPATIAL International Conference on
Advances in Geographic Information Systems (GIS), pages 336–343, November
2009.
[65] L. O’Callaghan, A. Meyerson, R. Motwani, N. Mishra, and S. Guha. Streamingdata
algorithms for high-quality clustering. In Proc. of the 18th IEEE International
Conference on Data Engineering (ICDE), pages 685–694, February 2002.
[66] M.-H. Park, J.-H. Hong, and S.-B. Cho. Location-based recommendation system
using bayesian user’s preference model in mobile devices. In Proc. of the Fourth
International Conference on Ubiquitous Intelligence and Computing (UIC), pages
1130–1139, July 2007.
[67] D. Pfoser and C. S. Jensen. Capturing the uncertainty of moving-object representations.
In Proc. of the Sixth International Symposium on Advances in Spatial
Databases (SSD), pages 111–132, July 1999.
[68] D. Pfoser and C. S. Jensen. Capturing the uncertainty of moving-object representations.
In Proc. of the Sixth International Symposium on Spatial Databases
(SSD), pages 111–132, July 1999.
[69] R. Praing and M. Schneider. Modeling historical and future movements of spatiotemporal
objects in moving objects databases. In Proc. of the 16th ACM Confer-
ence on Information and Knowledge Management (CIKM), pages 183–192, November
2007.
[70] C. P. Robert and G. Casella. Monte Carlo Statistical Methods. Springer-Verlag,
New York, 2004.
[71] P. P. Rodrigues, J. Gama, and L. Lopes. Clustering distributed sensor data
streams. In Proc. of the European conference on Machine Learning and Knowledge
Discovery in Databases - Part II (ECML PKDD), pages 282–297, September 2008.
[72] P. P. Rodrigues, J. Gama, and J. P. Pedroso. Hierarchical clustering of time series
data streams. IEEE Trans. on Knowledge and Data Engineering, 20(5):615–627,
May 2008.
[73] N. Roussopoulos, S. Kelley, and F. Vincent. Nearest neighbor queries. In Proc.
of the 15th ACM International Conference on Management of Data (SIGMOD),
pages 71–79, May 1995.
[74] S. B. Roy, G. Das, S. Amer-Yahia, and C. Yu. Interactive itinerary planning. In
Proc. of the 27th IEEE International Conference on Data Engineering (ICDE),
pages 15–26, April 2011.
[75] S. Sananmongkhonchai, P. Tangamchit, and P. Pongpaibool. Road traffic estimation
from multiple gps data using incremental weighted update. In Proc. of
the Eighth International Conference on ITS Telecommunications (ITST), pages
62–66, 2008.
[76] R. Sherkat and D. Rafiei. On efficiently searching trajectories and archival data
for historical similarities. In Proc. of the 34th International Conference on Very
Large Data Bases (VLDB), pages 896–908, August 2008.
[77] Y. Shi and L. Zhang. Coid: A clustervoutlier iterative detection approach to multidimensional
data analysis. Knowledge and Information Systems, 28(3):709–733,
September 2011.
[78] R. Simon and P. Fr¨ohlich. A mobile application framework for the geospatial web.
In Proc. of the 16th International Conference on World Wide Web (WWW), pages
381–390, May 2007.
[79] C.-H. Tai, B.-R. Dai, and M.-S. Chen. Incremental clustering in geography and
optimization spaces. In Proc. of the 11th Pacic-Asia Conference on Knowledge
Discovery and Data Mining (PAKDD), pages 272–283, May 2007.
[80] Taiwan area national freeway bureau, 2009. http://www.freeway.gov.tw/.
[81] Y. Takeuchi and M. Sugimoto. Cityvoyager: An outdoor recommendation system
based on user location history. In Proc. of the Third International Conference on
Ubiquitous Intelligence and Computing (UIC), pages 625–636, September 2007.
[82] P.-N. Tan, M. Steinbach, and V. Kumar. Introduction to Data Mining. Addison-
Wesley, New York, 2006.
[83] Y. Tian, K. C. K. Lee, and W.-C. Lee. Monitoring minimum cost paths on road
networks. In Proc. of the 17th ACM SIGSPATIAL International Conference on
Advances in Geographic Information Systems (GIS), pages 217–226, November
2009.
[84] G. Trajcevski, A. N. Choudhary, O. Wolfson, L. Ye, and G. Li. Uncertain range
queries for necklaces. In Proc. of the 11th International Conference on Mobile
Data Management (MDM), pages 199–208, May 2010.
[85] G. Trajcevski, H. Ding, P. Scheuermann, R. Tamassia, and D. Vaccaro. Dynamicsaware
similarity of moving objects trajectories. In Proc. of the 15th ACM SIGSPA-
TIAL International Conference on Advances in Geographic Information Systems
(GIS), pages 1–8, November 2007.
[86] Urban and rural development department, new taipei city govement, taiwan, 2010.
http://www.planning.ntpc.gov.tw/.
[87] K. Wagstaff and C. Cardie. Clustering with instance-level constraints. In Proc. of
the 17th International Conference on Machine Learning (ICML), pages 1103–1110,
June 2000.
[88] L. Wan, W. K. Ng, X. H. Dang, P. S. Yu, and K. Zhang. Density-based clustering
of data streams at multiple resolutions. ACM Trans. on Knowledge Discovery from
Data, 3(3):1–28, July 2009.
[89] J.-W. Wang and C.-H. Cheng. An efficient method for estimating null values in
relational databases. Knowledge and Information Systems, 12(3):379–394, August
2007.
[90] L. Wang, Y. Zheng, X. Xie, and W.-Y. Ma. A flexible spatio-temporal indexing
scheme for large-scale gps track retrieval. In Proc. of the Ninth International
Conference on Mobile Data Management (MDM), pages 1–8, April 2008.
[91] L.-Y.Wei and W.-C. Peng. Clustering data streams in optimization and geography
domains. In Proc. of the 13th Pacic-Asia Conference on Knowledge Discovery
and Data Mining (PAKDD), pages 997–1005, April 2009.
[92] L.-Y.Wei, W.-C. Peng, B.-C. Chen, and T.-W. Lin. Pats: A framework of patternaware
trajectory search. In Proc. of the First Workshop on Uncertain Mobile Data
Management and Mining (UMMM), pages 372–377, May 2010.
[93] Z. Yan, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer. Semitri: a
framework for semantic annotation of heterogeneous trajectories. In Proc. of the
14th International Conference on Extending Database Technology (EDBT), pages
259–270, March 2011.
[94] Z. Yan, C. Parent, S. Spaccapietra, and D. Chakraborty. A hybrid model and computing
platform for spatio-semantic trajectories. In Proc. of the seventh Extended
Semantic Web Conference (ESWC), pages 60–75, May 2010.
[95] Z. Yan, L. Spremic, D. Chakraborty, C. Parent, S. Spaccapietra, and K. Aberer.
Automatic construction and multi-level visualization of semantic trajectories. In
Proc. of the 18th SIGSPATIAL International Conference on Advances in Geo-
graphic Information Systems (GIS), pages 524–525, November 2010.
[96] J. Yang. Dynamic clustering of evolving streams with a single pass. In Proc. of the
19th IEEE International Conference on Data Engineering (ICDE), pages 695–697,
March 2003.
[97] Z. Yin, L. Cao, J. Han, J. Luo, and T. S. Huang. Diversified trajectory pattern
ranking in geo-tagged social media. In Proc. of the 11th SIAM International
Conference on Data Mining (SDM), pages 980–991, April 2011.
[98] H. Yoon, Y. Zheng, X. Xie, and W. Woo. Social itinerary recommendation from
user-generated digital trails. Personal and Ubiquitous Computing.
[99] H. Yoon, Y. Zheng, X. Xie, and W.Woo. Triptip: A trip planning service with tagbased
recommendation. In Proc. of the 27th International Conference on Human
Factors in Computing Systems (CHI), pages 3467–3472, April 2009.
[100] H. Yoon, Y. Zheng, X. Xie, and W. Woo. Smart itinerary recommendation based
on user-generated gps trajectories. In Proc. of the Seventh International Con-
ference on Ubiquitous Intelligence and Computing (UIC), pages 19–34, October
2010.
[101] J. Yoon, B. Noble, and M. Liu. Surface street traffic estimation. In Proc. of
the Fifth International Conference on Mobile Systems, Applications and Services
(MobiSys), pages 220–232, 2007.
[102] J. Yuan, Y. Zheng, C. Zhang, W. Xie, X. Xie, G. Sun, and Y. Huang. T-drive:
Driving directions based on taxi trajectories. In Proc. of the 18th ACM SIGSPA-
TIAL International Conference on Advances in Geographic Information Systems
(GIS), pages 99–108, November 2010.
[103] K. Zheng, Y. Zheng, X. Xie, and X. Zhou. Reducing uncertainty of low-samplingrate
trajectories. In Proc. of the 28th IEEE International Conference on Data
Engineering (ICDE), April 2012.
[104] V. W. Zheng, Y. Zheng, X. Xie, and Q. Yang. Collaborative location and activity
recommendations with gps history data. In Proc. of the 19th International
Conference on World Wide Web (WWW), pages 1029–1038, April 2009.
[105] Y. Zheng, L. Liu, L. Wang, and X. Xie. Learning transportation mode from raw
gps data for geographic applications on the web. In Proc. of the 17th International
Conference on World Wide Web (WWW), pages 247–256, April 2008.
[106] Y. Zheng and X. Xie. Learning travel recommendations from user-generated gps
traces. ACM Trans. on Intelligent Systems and Technology, 2(1):2–19, January
2011.
[107] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel
sequences from gps trajectories for mobile users. In Proc. of the 18th International
Conference on World Wide Web (WWW), pages 791–800, April 2009.
[108] A. Zhou, F. Cao, Y. Yan, C. Sha, and X. He. Density-based clustering for real-time
stream data. In Proc. of the 13th ACM International Conference on Knowledge
Discovery and Data Mining (SIGKDD), pages 133–142, August 2007.
[109] A. Zhou, F. Cao, Y. Yan, C. Sha, and X. He. Distributed data stream clustering:
A fast em-based approach. In Proc. of the 23rd International Conference on Data
Engineering (ICDE), pages 736–745, April 2007.
[110] J. Zhou, J. Guan, and P. Li. Dcad: a dual clustering algorithm for distributed
spatial databases. Geo-Spatial Information Science, 10(2):137–144, June 2007.