基于層次結構網(wǎng)絡的近似最短路徑查詢研究
發(fā)布時間：2018-08-09 16:34
【摘要】：隨著大數(shù)據(jù)時代的到來,網(wǎng)絡數(shù)據(jù)規(guī)模的迅速增長以及數(shù)據(jù)拓撲結構的日益復雜,大規(guī)模網(wǎng)絡數(shù)據(jù)的分析與操作存在著空間消耗過大以及快速響應需求也越來越難滿足的問題,網(wǎng)絡數(shù)據(jù)的簡化與層次結構網(wǎng)絡的構建是解決該問題的有效途徑。最短路徑查詢問題是網(wǎng)絡分析研究的核心內容之一,分層技術是實現(xiàn)最短路徑查詢的一種加速技術,網(wǎng)絡層次結構模型保存了部分節(jié)點、邊及其他中間信息,將原始網(wǎng)絡中的分析問題轉移到相對稀疏的高層網(wǎng)絡中,能夠在保證查詢精度的同時達到高效、快速實現(xiàn)特定查詢的目的。本文以大規(guī)模復雜網(wǎng)絡的層次結構研究為主線,重點圍繞網(wǎng)絡層次結構模型以及最短路徑查詢問題中的預處理與查詢兩個方面進行研究。同時,以道路網(wǎng)數(shù)據(jù)構建層次結構網(wǎng)絡并實現(xiàn)近似最短路徑查詢,從而為方法應用提供參考示范。主要研究內容如下:(1)針對大規(guī)模復雜網(wǎng)絡中層次結構分析不足的問題,系統(tǒng)分析了最短路徑查詢、k最近鄰查詢以及網(wǎng)絡中心性等研究中層次結構網(wǎng)絡的構建方法,總結了網(wǎng)絡層次結構模型的一般性理論,包括基本概念與定義、分層模型描述以及網(wǎng)絡的劃分方案。(2)針對現(xiàn)有網(wǎng)絡劃分方法中僅考慮以單一指標作為網(wǎng)絡劃分策略,而產(chǎn)生的網(wǎng)絡劃分規(guī)模不均衡和時間開銷大等問題,基于分割思想和覆蓋的地標點選擇方法提出了中心距離均衡的網(wǎng)絡劃分方法,并設計了相應的網(wǎng)絡劃分與簡化算法,為非平面結構網(wǎng)絡的劃分及網(wǎng)絡分割質量的衡量提供了一種思路。(3)為了提高查詢速度與預處理效率,在中心距離均衡法的基礎上,迭代實現(xiàn)網(wǎng)絡劃分與化簡,設計實現(xiàn)了基于BCD的層次結構網(wǎng)絡構建方法,以及節(jié)點樹形結構的表示方法。多層級的層次結構網(wǎng)絡降低了原始網(wǎng)絡的規(guī)模,降低了分層網(wǎng)絡中搜索算法的復雜度。(4)構建了基于層次結構網(wǎng)絡的近似查詢處理方案。采用關系模型表達并存儲網(wǎng)絡的層次結構,在層次結構網(wǎng)絡中引入reach*剪枝算法,實現(xiàn)了最短路徑的快速查詢;同時,設計實現(xiàn)了節(jié)點近似最短路徑值范圍的估計方法,并在該算法設計的基礎上實現(xiàn)基于樹形結構的近似最短路徑值的實時估計。(5)針對紐約道路網(wǎng)數(shù)據(jù)進行實證分析,重點對地標點選擇、層次結構網(wǎng)絡構建以及近似查詢結果進行分析。利用隨機策略與基于度的選擇策略進行地標點選取,分析比較6層層次結構網(wǎng)的地標點分布、網(wǎng)絡規(guī)模與構建時間;利用reach*算法實時計算不同層次結構網(wǎng)絡的最短路徑;利用范圍約束的最短路徑值查詢方法估算任意節(jié)點間的最短距離范圍,從而為方法應用提供參考和借鑒。
[Abstract]:With the arrival of big data era, the rapid growth of network data scale and the increasing complexity of data topology, the analysis and operation of large-scale network data has the problems of excessive space consumption and rapid response to the needs of more and more difficult to meet. The simplification of network data and the construction of hierarchical network are effective ways to solve this problem. The shortest path query problem is one of the core contents of network analysis and research. Hierarchical technology is an accelerated technology to realize the shortest path query. The network hierarchy model preserves some nodes, edges and other intermediate information. The problem of analysis in the original network can be transferred to the relatively sparse high-level network, which can ensure the accuracy of the query and achieve high efficiency and fast realization of the purpose of the specific query. In this paper, the hierarchical structure of large-scale complex networks is the main line, focusing on the network hierarchy model and the shortest path query problem in the preprocessing and query two aspects. At the same time, the hierarchical network is constructed from the road network data and the approximate shortest path query is realized, which provides a reference example for the application of the method. The main research contents are as follows: (1) aiming at the problem of insufficient analysis of hierarchical structure in large-scale complex networks, this paper systematically analyzes the methods of constructing hierarchical networks in the research of shortest path query, nearest neighbor query and network centrality. This paper summarizes the general theory of the network hierarchy model, including the basic concepts and definitions, the description of the hierarchical model and the partition scheme of the network. (2) considering that only a single index is considered as the network partition strategy in the existing network partitioning methods, However, the network partition scale is unbalanced and the time cost is large. Based on the idea of segmentation and the coverage of the ground punctuation selection method, the center distance equalization network partition method is proposed, and the corresponding network partition and simplification algorithm is designed. In order to improve the query speed and preprocessing efficiency, the network partition and simplification are implemented iteratively on the basis of the central distance equalization method. The method of constructing hierarchical network based on BCD and the representation of node tree structure are designed and implemented. The hierarchical network reduces the scale of the original network and reduces the complexity of the search algorithm in the hierarchical network. (4) the approximate query processing scheme based on the hierarchical network is constructed. The relational model is used to express and store the hierarchical structure of the network, and the reach-pruning algorithm is introduced into the hierarchical network to realize the fast query of the shortest path, and at the same time, a method to estimate the approximate value range of the shortest path is designed and implemented. On the basis of the design of the algorithm, the approximate shortest path value can be estimated in real time based on tree structure. (5) based on the empirical analysis of New York road network data, the emphasis is placed on the selection of ground punctuation points. Hierarchical network construction and approximate query results are analyzed. The random strategy and the degree based selection strategy are used to select the land punctuation points, to analyze and compare the land punctuation distribution, the network size and the construction time of the six-layer hierarchical network, and to calculate the shortest path of the different hierarchical network in real time by using the algorithm of reach*. The shortest path value query method with range constraint is used to estimate the shortest distance range between arbitrary nodes, which provides a reference for the application of the method.
【學位授予單位】：中國測繪科學研究院
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5
，
本文編號：2174681
[Abstract]:With the arrival of big data era, the rapid growth of network data scale and the increasing complexity of data topology, the analysis and operation of large-scale network data has the problems of excessive space consumption and rapid response to the needs of more and more difficult to meet. The simplification of network data and the construction of hierarchical network are effective ways to solve this problem. The shortest path query problem is one of the core contents of network analysis and research. Hierarchical technology is an accelerated technology to realize the shortest path query. The network hierarchy model preserves some nodes, edges and other intermediate information. The problem of analysis in the original network can be transferred to the relatively sparse high-level network, which can ensure the accuracy of the query and achieve high efficiency and fast realization of the purpose of the specific query. In this paper, the hierarchical structure of large-scale complex networks is the main line, focusing on the network hierarchy model and the shortest path query problem in the preprocessing and query two aspects. At the same time, the hierarchical network is constructed from the road network data and the approximate shortest path query is realized, which provides a reference example for the application of the method. The main research contents are as follows: (1) aiming at the problem of insufficient analysis of hierarchical structure in large-scale complex networks, this paper systematically analyzes the methods of constructing hierarchical networks in the research of shortest path query, nearest neighbor query and network centrality. This paper summarizes the general theory of the network hierarchy model, including the basic concepts and definitions, the description of the hierarchical model and the partition scheme of the network. (2) considering that only a single index is considered as the network partition strategy in the existing network partitioning methods, However, the network partition scale is unbalanced and the time cost is large. Based on the idea of segmentation and the coverage of the ground punctuation selection method, the center distance equalization network partition method is proposed, and the corresponding network partition and simplification algorithm is designed. In order to improve the query speed and preprocessing efficiency, the network partition and simplification are implemented iteratively on the basis of the central distance equalization method. The method of constructing hierarchical network based on BCD and the representation of node tree structure are designed and implemented. The hierarchical network reduces the scale of the original network and reduces the complexity of the search algorithm in the hierarchical network. (4) the approximate query processing scheme based on the hierarchical network is constructed. The relational model is used to express and store the hierarchical structure of the network, and the reach-pruning algorithm is introduced into the hierarchical network to realize the fast query of the shortest path, and at the same time, a method to estimate the approximate value range of the shortest path is designed and implemented. On the basis of the design of the algorithm, the approximate shortest path value can be estimated in real time based on tree structure. (5) based on the empirical analysis of New York road network data, the emphasis is placed on the selection of ground punctuation points. Hierarchical network construction and approximate query results are analyzed. The random strategy and the degree based selection strategy are used to select the land punctuation points, to analyze and compare the land punctuation distribution, the network size and the construction time of the six-layer hierarchical network, and to calculate the shortest path of the different hierarchical network in real time by using the algorithm of reach*. The shortest path value query method with range constraint is used to estimate the shortest distance range between arbitrary nodes, which provides a reference for the application of the method.
【學位授予單位】：中國測繪科學研究院
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：O157.5
，
本文編號：2174681
本文鏈接：http://sikaile.net/kejilunwen/yysx/2174681.html
最近更新
教材專著
