# 臺灣博碩士論文加值系統

(44.192.20.240) 您好！臺灣時間：2024/02/24 01:20

:::

### 詳目顯示

:

• 被引用: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.
 摘 要 .........................................iAbstract ........................................iiAcknowledgement ................................iiiContents ........................................ivList of Figures ..................................v1. Introduction...................................12. Preliminaries .................................6 2.1 Problem Definition .........................6 2.2 Basic Storage ..............................83. 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 .......................214. Experiment ....................................25 4.1 Experiment Setup ...........................25 4.2 Experimental Results .......................265. Related Works .................................28 5.1 Shortest Path Query in Large Road Networks .29 5.2 Fastest Path Query on Dynamic Networks ....296. Conclusion and Future Works ...................31Reference ........................................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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 馬軍，〈恩怨話江湖：長江中下游濕地生態憂思〉，《中國國家地理雜誌（2004/5）》。台北：牛頓出版。

 1 在多重資料串流環境中探勘序列性段落規則及其後繼之延遲時間 2 一個有效處理多個連續性Top-K查詢的方法 3 國際油價對台灣股價預測表現之研究 4 不動產課稅對房價影響之研究 5 利用社群媒體,問卷和公開資料建立兩階段的憂鬱症預測模型 6 智慧型手機之使用者軌跡探勘 7 尋找一條符合使用者需求的最短路徑 8 在圖上尋找最大的並包含目標點的類完全子圖 9 無線感測網路之多重路徑感測器區域同步化 10 大眾運輸系統最短路徑之研究 11 於空間資料庫考量雙資料型態的反向最近點Top-N查詢處理 12 DynamicSkylinesConsideringRangeQueries 13 具不確定性資料串流之連續型機率天際線查詢 14 針對複合式競賽挑選最佳球員組合的方法 15 個人化部落格搜尋

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室