【摘要】：隨著大數(shù)據(jù)時(shí)代的到來(lái),網(wǎng)絡(luò)數(shù)據(jù)規(guī)模的迅速增長(zhǎng)以及數(shù)據(jù)拓?fù)浣Y(jié)構(gòu)的日益復(fù)雜,大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)的分析與操作存在著空間消耗過(guò)大以及快速響應(yīng)需求也越來(lái)越難滿足的問(wèn)題,網(wǎng)絡(luò)數(shù)據(jù)的簡(jiǎn)化與層次結(jié)構(gòu)網(wǎng)絡(luò)的構(gòu)建是解決該問(wèn)題的有效途徑。最短路徑查詢問(wèn)題是網(wǎng)絡(luò)分析研究的核心內(nèi)容之一,分層技術(shù)是實(shí)現(xiàn)最短路徑查詢的一種加速技術(shù),網(wǎng)絡(luò)層次結(jié)構(gòu)模型保存了部分節(jié)點(diǎn)、邊及其他中間信息,將原始網(wǎng)絡(luò)中的分析問(wèn)題轉(zhuǎn)移到相對(duì)稀疏的高層網(wǎng)絡(luò)中,能夠在保證查詢精度的同時(shí)達(dá)到高效、快速實(shí)現(xiàn)特定查詢的目的。本文以大規(guī)模復(fù)雜網(wǎng)絡(luò)的層次結(jié)構(gòu)研究為主線,重點(diǎn)圍繞網(wǎng)絡(luò)層次結(jié)構(gòu)模型以及最短路徑查詢問(wèn)題中的預(yù)處理與查詢兩個(gè)方面進(jìn)行研究。同時(shí),以道路網(wǎng)數(shù)據(jù)構(gòu)建層次結(jié)構(gòu)網(wǎng)絡(luò)并實(shí)現(xiàn)近似最短路徑查詢,從而為方法應(yīng)用提供參考示范。主要研究?jī)?nèi)容如下:(1)針對(duì)大規(guī)模復(fù)雜網(wǎng)絡(luò)中層次結(jié)構(gòu)分析不足的問(wèn)題,系統(tǒng)分析了最短路徑查詢、k最近鄰查詢以及網(wǎng)絡(luò)中心性等研究中層次結(jié)構(gòu)網(wǎng)絡(luò)的構(gòu)建方法,總結(jié)了網(wǎng)絡(luò)層次結(jié)構(gòu)模型的一般性理論,包括基本概念與定義、分層模型描述以及網(wǎng)絡(luò)的劃分方案。(2)針對(duì)現(xiàn)有網(wǎng)絡(luò)劃分方法中僅考慮以單一指標(biāo)作為網(wǎng)絡(luò)劃分策略,而產(chǎn)生的網(wǎng)絡(luò)劃分規(guī)模不均衡和時(shí)間開銷大等問(wèn)題,基于分割思想和覆蓋的地標(biāo)點(diǎn)選擇方法提出了中心距離均衡的網(wǎng)絡(luò)劃分方法,并設(shè)計(jì)了相應(yīng)的網(wǎng)絡(luò)劃分與簡(jiǎn)化算法,為非平面結(jié)構(gòu)網(wǎng)絡(luò)的劃分及網(wǎng)絡(luò)分割質(zhì)量的衡量提供了一種思路。(3)為了提高查詢速度與預(yù)處理效率,在中心距離均衡法的基礎(chǔ)上,迭代實(shí)現(xiàn)網(wǎng)絡(luò)劃分與化簡(jiǎn),設(shè)計(jì)實(shí)現(xiàn)了基于BCD的層次結(jié)構(gòu)網(wǎng)絡(luò)構(gòu)建方法,以及節(jié)點(diǎn)樹形結(jié)構(gòu)的表示方法。多層級(jí)的層次結(jié)構(gòu)網(wǎng)絡(luò)降低了原始網(wǎng)絡(luò)的規(guī)模,降低了分層網(wǎng)絡(luò)中搜索算法的復(fù)雜度。(4)構(gòu)建了基于層次結(jié)構(gòu)網(wǎng)絡(luò)的近似查詢處理方案。采用關(guān)系模型表達(dá)并存儲(chǔ)網(wǎng)絡(luò)的層次結(jié)構(gòu),在層次結(jié)構(gòu)網(wǎng)絡(luò)中引入reach*剪枝算法,實(shí)現(xiàn)了最短路徑的快速查詢;同時(shí),設(shè)計(jì)實(shí)現(xiàn)了節(jié)點(diǎn)近似最短路徑值范圍的估計(jì)方法,并在該算法設(shè)計(jì)的基礎(chǔ)上實(shí)現(xiàn)基于樹形結(jié)構(gòu)的近似最短路徑值的實(shí)時(shí)估計(jì)。(5)針對(duì)紐約道路網(wǎng)數(shù)據(jù)進(jìn)行實(shí)證分析,重點(diǎn)對(duì)地標(biāo)點(diǎn)選擇、層次結(jié)構(gòu)網(wǎng)絡(luò)構(gòu)建以及近似查詢結(jié)果進(jìn)行分析。利用隨機(jī)策略與基于度的選擇策略進(jìn)行地標(biāo)點(diǎn)選取,分析比較6層層次結(jié)構(gòu)網(wǎng)的地標(biāo)點(diǎn)分布、網(wǎng)絡(luò)規(guī)模與構(gòu)建時(shí)間;利用reach*算法實(shí)時(shí)計(jì)算不同層次結(jié)構(gòu)網(wǎng)絡(luò)的最短路徑;利用范圍約束的最短路徑值查詢方法估算任意節(jié)點(diǎn)間的最短距離范圍,從而為方法應(yīng)用提供參考和借鑒。
[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.
【學(xué)位授予單位】：中國(guó)測(cè)繪科學(xué)研究院
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5
，

本文編號(hào)：2174681