跳到主要內容

臺灣博碩士論文加值系統

(44.192.48.196) 您好!臺灣時間:2024/06/26 01:34
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:郭柏辰
研究生(外文):Bo-Chen Guo
論文名稱:探討使用Network Voronoi Diagram在資料廣播環境中進行道路網路最短路徑查詢的方法
論文名稱(外文):Exploring the Shortest Path Query on Road Network using Network Voronoi Diagram in Data Broadcasting Environments
指導教授:劉傳銘劉傳銘引用關係
口試委員:陳震宇王正豪
口試日期:2014-07-09
學位類別:碩士
校院名稱:國立臺北科技大學
系所名稱:資訊工程系研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:中文
論文頁數:53
中文關鍵詞:資料廣播最短路徑查詢時間聽取時間Network Voronoi Diagram
外文關鍵詞:Data BroadcastingShortest PathAccess LatencyTuning TimeNetwork Voronoi Diagram
相關次數:
  • 被引用被引用:0
  • 點閱點閱:180
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
近年來行動裝置以及無線網路的普及化,使得行動裝置上出現眾多衍生服務,其中的適地性服務為最常見也最被廣泛使用的服務之一。使用者得以藉著行動裝置進行以地理資訊方面的查詢,其中最短路徑查詢方法為一個重要的項目。隨著地圖資料越來越龐大,在行動裝置的計算能力以及記憶體容量受限的狀況下,如何提供一個有效率的最短路徑查詢方法為一個值得討論的議題。在無線網路環境下,資料廣播提供複數使用者同時接收資料,且不會隨著使用者的增減對伺服器造成影響,適合解決上述問題的。在資料廣播環境下的兩項效能指標:查詢經歷時間及聽取時間。從客戶端在開始查詢到結束查詢結束這段時間稱為查詢經歷時間;而聽取時間則是實際擷取資料的時間之加總。伺服端提供處理過後的資訊於廣播頻道中,使用者端依照廣播內容自行接收相關資料。本論文研究探討伺服端如何有效運用NVD的結構,觀察使用者端執行最短路徑查詢時在經歷時間以及聽取時間上的影響。

The mobile device and the condition of the wireless mobile network are popular in recent year, and the router problem also solved as quick as possible when we use the services with mobile device. In the above describe, the service are compute the shortest path for response answer to user. It has a serious issue with the wireless mobile environment is the service performance will be decreasing with service user increasing. Data-Broadcasting is a proper structure to solving the problem. Under this consideration, the performance factors considered are tuning time and access latency. Tuning time is the number of the packets of the data from server that is necessary for the query. Access latency is the time between the client query and the time when all the required data are received. Before the service provided for user, the server has to partitions the data for channel to broadcast. In this paper, we observe the effect of the performance on the different road networks, partition method, packet size, and broadcasting methods. Finally, use experiments to prove the performance of tuning time and access latency.

摘 要 i
ABSTRACT ii
誌謝 iii
圖目錄 v
第一章 緒論 1
1.1 研究動機 1
1.2 研究目的 4
1.3 論文架構 4
第二章 文獻探討 5
2.1 資料廣播環境 5
2.2 Push base環境下搜尋最短路徑方法 7
2.3 廣播環境底下搜尋最短路徑方法 8
2.4 Network Voronoi Diagram(NVD) 11
2.5 R*-tree 12
2.6 超圖(super graph) 14
第三章 現有廣播方法之比較與討論 15
3.1 廣播環境底下搜尋最短路徑方法 15
第四章 廣播環境使用NVD的最短路徑搜尋 19
4.1 NVD圖資於廣播中排程 19
4.2 廣播排程使用不同方式之探討 25
第五章 模擬實驗 26
5.1 環境設定 26
5.2 廣播環境中最短路徑查詢比較 29
5.3 廣播排程使用不同方式索引之表現 36
第六章 結論 50
參考文獻 51


[1]E. Kaplan and C. Hegarty. Understanding GPS: Principles and Applications Second Edition, Artech House, 2006.
[2]J. Spinney, A brief history of LBS and How OpenLS Fits Into the New Value Chain, Location-Based Services ESRI, 2003.
[3]S. Acharya, R. Alonso, M. Franklin and S. Zdonik, “Broadcast Disk: Data Management for Asymmetric Communication Environments”, In Proceeding of the 1995 ACM SIGMOD International Conference on Management of Data, pp. 199-210, 1995.
[4]S. Acharya, R. Alonso, M. Franklin and S. Zdonik, “Balancing Push and Pull for Data Broadcasts”, In Proceedings of the ACM SIGMOD International Conference on Management of Data, pp. 183-194, 1997.
[5]C.-M. Liu, Broadcasting and Blocking Large Data Sets with an Index Tree, PhD thesis, Purdue University, West Lafayette, 2002.
[6]K.-F. Lin and C.-M. Liu, “Efficient Scheduling Algorithms for Disseminating Dependent Data in Wireless Mobile Environments”, In Proceedings of the IEEE International Conference on Wireless Networks, communications and Mobile Computing, 2005.
[7]K.-F. Lin and C.-M. Liu, “Schedules with Minimized Access Latency for Disseminating Dependent Information on Multiple Channels”, In Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing, pp. 344-351, 2006.
[8]T. Imielinski, S. Viswanathan and B.R. Badrinath, “Data on Air: Organization and Access”, IEEE Transactions on Knowledge and Data Engineering, 9(3):353-372, 1997.
[9]S. Hambrusch, C.-M. Liu, W. Aref and S. Prabhakar. “Efficient Query Execution on Broadcasted Index Tree Structures”, Data and Knowledge Engineering, 60(3):511-529, 2007.
[10]S. Hambrusch, C.-M. Liu and S. Prabhakar. “Broadcasting and Querying Multi-dimensional Index Trees in a Multi-channel Environment”, Information System,32(8): 870-886, 2006.
[11]T. Imielinski, S. Viswanathan, and B.R. Badrinath, “Power efficient filtering of data on air”, In Proceedings of the 4th International Conference on Extending Database Technology on Advances in Database Technology, pp.245-258, 1994.
[12]W.-C. Lee and D.L. Lee. “Using Signature Techniques for Information Filtering in Wireless and Mobile Environments”, Distributed and Parallel Databases,4(3):205-227, 1996.
[13]Dijkstra E. W., “A Note on Two Problems in Connection With Graphs”, Numerische Mathematik, pp.269-271, 1959.
[14]I. Phol, “Bi-Directional Search”, Machine Intelligence, pp.127-170, 1971.
[15]R. Sedgewick and J.S. Vitter, “Shortest Paths in Euclidean Graphs”, Algorithmica, 1(1):31-48, 1986.
[16]R. Agrawal and H.V. Jagadish, “Materialization and Incremental Update of Path Information”, In Proceedings of the Fifth International Conference Data Engineering, pp.374-383, 1989.
[17]Y.-W. Huang, N. Jing and E. A. Rundensteiner, “A Semi-Materialized View Approach for Route Maintenance in Intelligent Vehicle Highway Systems”, In Proceeding of the Second ACM Workshop Geographic Information Systems, pp.144-151, 1994.
[18]S. Shekhar, A. Kohli and M. Coyle, “Path Computation Algorithms for Advanced Traveler Information System”, In Proceedings of the Ninth International Conference of Data Engineering, pp.31-39, 1993.
[19]S. Jung and S. Pramanik, “HiTi Graph Model of Topological Road Maps in Navigation Systems”, In Proceedings of the 12th International Conference Data Engineering, pp.76-84, 1996.
[20]Y.-W. Huang, N. Jing and E. A. Rundensteiner, “Hierarchical Path Views: A Model Based on Fragmentation and Transportation Road Type”, In Proceeding of the Third ACM Workshop Geographic Information Systems, pp.93-100, 1995
[21]N. Jing, Y.-H. Huang and E. A. Rundensteiner, “Hierarchical Optimization of Optimal Path Finding for Transportation Application”, In Proceeding of the Fifth International Conference on Information and Knowledge Management, pp.261-268, 1996.
[22]E. W. Dijkstra. “A note on two problems in connexion with graphs”, In Proceeding of NUMERISCHE MATHEMATIK, pp.269-271, 1959.
[23]P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths”, In Proceeding of IEEE Transactions on Systems, Science, and Cybernetics, pp.100-107, 1968
[24]EKKehard Kohler, Rolf H. Mohring, and Heiko Schilling*, “Fast Point-to-Point Shortest Path Computations with Arc-Flags”, In Proceedings of 9th DIMACS Implementation Challenge - Shortest Paths, 2007.
[25]A. V. Goldberg and C. Harrelson, “Computing the Shortest Path : A* search meets graph theory”, In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pp.156- 165, 2005.
[26]Georgios Kellaris, Kyriakos Mouratidis, “Shortest Path Computation on Air Indexes”, In Proceedings of the VLDB Endowment, Vol. 3, No. 1, pp.747-757, 2010.
[27]T.-C. Su, Y.-T. Hsieh, and C.-M. Liu, “Shortest Path Queries in Mobile Broadcast Environments”, In Proceeding of the 17th International Conference on Geoinformatics, 2009.
[28]Y.-W. Huang, N. Jing and E. A. Rundensteiner, “Efficient Graph Clustering for Path Queries in Digital Map Databases”, In Proceedings of International Symposium on Algorithms and Computation, 1999.
[29]R. H. Mohring, H. Schilling, B. Schutz, D. Wagner, and T. Willhalm, “Partitioning graphs to speedup Dijkstra’s algorithm”, In Journal of Experimental Algorithmics, 11(2.8):1-29, 2006.
[30]交通路網數值地圖, http://www.iot.gov.tw, (view available: July, 2008)
[31]A. Okabe, T. Satoh, T. Furuta, A. Suzuki and K. Okano. Generalized network Voronoi diagrams: Concepts, computational methods, and applications. In International Journal of Geographical Information Science Archive, 22 (9):965-994, 2008.
[32]A. Guttman, “R-Tree: A Dynamic Index Structure for Spatial Searching”, In Proceedings of ACM SIGMODE, pp.47-57, 1984.
[33]TIGER Products – Geography –U.S. Census Bureau, https://www.census.gov/geo/maps-data/data/tiger.html, 2014.


電子全文 電子全文(本篇電子全文限研究生所屬學校校內系統及IP範圍內開放)
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關期刊