跳到主要內容

臺灣博碩士論文加值系統

(44.192.20.240) 您好!臺灣時間:2024/02/24 01:20
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:李佳蓁
研究生(外文):Chia-Chen Lee
論文名稱:道路網上最快路徑查詢之持續評估
論文名稱(外文):Continuous Evaluation of Fastest Path Queries on Road Networks.
指導教授:陳良弼陳良弼引用關係
指導教授(外文):Arbee L. P. Chen
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:33
中文關鍵詞:道路網最快路徑連續性查詢
外文關鍵詞:road networkfastest pathcontinuous query
相關次數:
  • 被引用被引用:0
  • 點閱點閱:139
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
在空間網路資料庫中,搜尋兩點間(起點以及終點)之路徑是一個時常使用並且基本的操作。在過去的研究當中,大多著重於最短路徑的搜尋,也就是找到一條由起點出發至終點的路徑,使得其距離最短。然而,在很多如導航系統這樣的實際的應用中,交通的狀況以及行車所需要的時間不斷地改變。並且,使用者通常期望得到一條最快的路徑,也就是能夠花費最少時間,由起點抵達終點的路徑。而這個路徑可能不是最短的路徑。這促使我們注意到最快路徑查詢以及連續最快路徑查詢之持續評估的問題,以適應動態的交通狀況以及道路環境。要處理一個連續最快路徑查詢,可以採用離散時間模式,也就是在每個時間片段重新對最快路徑查詢做評估,然而這是一個計算量十分驚人的方式。當系統中有大量的查詢同時存在時,這個重新評估的花費會更高。在本論文中,我們提出了ㄧ個新的方法,這個方法採用了影響區塊、容忍參數的內涵,以及一個網格式索引結構。藉由容忍參數,只要一個查詢的最快路徑與答案接近,系統不需要對此查詢做重新評估。另外,當系統要處理多重查詢時,網格式索引結構可以加速查詢之評估。最後,我們利用真實的道路資料以及模擬的交通狀況來做實驗。實驗結果顯示本論文提出之方法有非常好的表現。
Finding the shortest path between two given positions (the origin and the destination) is an essential operation in spatial network databases. Previous studies focus on evaluating the shortest path query, which will find the path with the shortest network distance. However, in the applications on road networks such as the guided driving, the traffic conditions often vary as time goes and the user is actually interested in the path with the minimum travel time (called the fastest path), which may not have the shortest network distance. This motivates us to study the issues of continuously evaluating the fastest path query in order to capture the dynamics of road networks. Repeatedly evaluating the fastest path query at every moment is infeasible due to its computationally expensive cost. The cost is higher if more queries are evaluated at the same time. In this paper, we propose a novel approach that employs the concepts of the affecting area and the tolerance parameter, and a grid-based index structure. With the tolerance parameter, a query is not reevaluated as long as the travel time of the current answer is close enough to that of the fastest path. Furthermore, with the grid-based index, the dynamics of road networks and the queries are fused together to achieve the efficient re-evaluation of multiple queries. Experiments based on real road networks are performed and the results show the great performance of our approach.
摘 要 .........................................i
Abstract ........................................ii
Acknowledgement ................................iii
Contents ........................................iv
List of Figures ..................................v
1. Introduction...................................1
2. Preliminaries .................................6
2.1 Problem Definition .........................6
2.2 Basic Storage ..............................8
3. Ellipse Bounding Method ......................10
3.1 Ellipse Bounding Property ..................10
3.2 Single Query Processing ....................13
3.3 Multiple Query Processing ..................15
3.4 Maintenance of Index .......................21
4. Experiment ....................................25
4.1 Experiment Setup ...........................25
4.2 Experimental Results .......................26
5. Related Works .................................28
5.1 Shortest Path Query in Large Road Networks .29
5.2 Fastest Path Query on Dynamic Networks ....29
6. Conclusion and Future Works ...................31
Reference ........................................32
[1] R. Agrawal and H. Jagadish. Materialization and Incremental Update of Path Information. In Proc. Fifth Int’l Conf. Data Eng., pp. 374-383, 1989.
[2] T. Cormen, C. Lieserson, and R. Rivest. Introduction to algorithms. 1990.
[3] J. Esser and M. Schrechenberg. Microscopic Simulation of Urban Traffic Based on Cellular Automata. International Journal of Modern Physics, Vol. 8, pp. 1025-1036, 1997.
[4] E. Dijkstra. A Note on Two Problems in Connection with Graphs. Numeriche Mathematik, Vol. 1, pp. 269-271, 1959.
[5] D. Frigioni, A. Marchetti-Spaccamela, and U. Nanni. Lifelong planning A*. Artificial Intelligence, Vol. 155, pp. 93-146, 2004.
[6] L. Fu, and L. Rilett. Expected shortest paths in dynamic and stochastic traffic networks, Transportation Research, Methodological, vol. 32, pp. 499-516.
[7] S. Gupta, S. Kopparty, and C. Ravishankar. Roads, Codes, and Spatiotemporal Queries. In Proc. of the 19th ACM Symp. on Principles of Database Systems (PODS), pp. 13-18, 2004.
[8] Y. Huang, N. Jing, and E. Rundensteiner. A Semi-Materialized View Approach for Route Maintenance in Intelligent Vehicle Highway Systems. In Proc. Second ACM Workshop Geographic Information Systems, pp. 144-151, 1994.
[9] Y. Huang, N. Jing, and E. Rundensteiner. Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Types. In Proc. Third ACM Workshop Geographic Information Systems, pp. 93-100, 1995.
[10] N. Jing, Y. Huang, and E. Rundensteiner. Hierarchical Encoded Path Views for Path Query Processing: An Optimal Model and Its Performance Evaluation. IEEE Transactions on Knowledge and Data Engineering, Vol. 10, pp. 409-432, 1998.
[11] W. Ku, R. Zimmermann, H. Wang, and C. Wan. Adaptive Nearest Neighbor Queries in Travel Time Networks. In Proc. of the 13th annual ACM international workshop on Geographic information systems, 2005
[12] E. Kanoulas, Y. Du, T. Xia, and D. Zhang. Finding Fastest Paths on A Road Network with Speed Patterns. 22nd International Conference on Data Engineering, 2006
[13] N. Nilsson. Problem-Solving Methods. Artificial Intelligence, 1971.
[14] S. Pallottino and M. Scutella. Shortest Path Algorithms in Transportation Models: Classical and Innovative Aspects. Equilibrium and Advanced Transportation Modeling. 1998.
[15] S. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. 2003
[16] S. Shekhar, A. Fetterer, and B. Goyal. Materialization Trade-Offs in Hierarchical Shortest Path Algorithms. In Proc. Of 4th Advances in Spatial and Temporal Databases, 1997.
[17] C. Shahabl, M. Kolahdouzan, and M. Sharifzadeh. A road network embedding technique for k-nearest neighbor search in moving object databases. GeoInformatica, Vol.7, pp. 255-273, 2003.
[18] J. Sankaranarayanan, H. Alborzi, and H. Samet. Efficient Query Processing on Spatial Networks. In Proc. of the 13th annual ACM international workshop on Geographic information systems, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top