基于层次结构网络的近似最短路径查询研究
发布时间：2018-08-09 16:34
【摘要】：随着大数据时代的到来,网络数据规模的迅速增长以及数据拓扑结构的日益复杂,大规模网络数据的分析与操作存在着空间消耗过大以及快速响应需求也越来越难满足的问题,网络数据的简化与层次结构网络的构建是解决该问题的有效途径。最短路径查询问题是网络分析研究的核心内容之一,分层技术是实现最短路径查询的一种加速技术,网络层次结构模型保存了部分节点、边及其他中间信息,将原始网络中的分析问题转移到相对稀疏的高层网络中,能够在保证查询精度的同时达到高效、快速实现特定查询的目的。本文以大规模复杂网络的层次结构研究为主线,重点围绕网络层次结构模型以及最短路径查询问题中的预处理与查询两个方面进行研究。同时,以道路网数据构建层次结构网络并实现近似最短路径查询,从而为方法应用提供参考示范。主要研究内容如下:(1)针对大规模复杂网络中层次结构分析不足的问题,系统分析了最短路径查询、k最近邻查询以及网络中心性等研究中层次结构网络的构建方法,总结了网络层次结构模型的一般性理论,包括基本概念与定义、分层模型描述以及网络的划分方案。(2)针对现有网络划分方法中仅考虑以单一指标作为网络划分策略,而产生的网络划分规模不均衡和时间开销大等问题,基于分割思想和覆盖的地标点选择方法提出了中心距离均衡的网络划分方法,并设计了相应的网络划分与简化算法,为非平面结构网络的划分及网络分割质量的衡量提供了一种思路。(3)为了提高查询速度与预处理效率,在中心距离均衡法的基础上,迭代实现网络划分与化简,设计实现了基于BCD的层次结构网络构建方法,以及节点树形结构的表示方法。多层级的层次结构网络降低了原始网络的规模,降低了分层网络中搜索算法的复杂度。(4)构建了基于层次结构网络的近似查询处理方案。采用关系模型表达并存储网络的层次结构,在层次结构网络中引入reach*剪枝算法,实现了最短路径的快速查询;同时,设计实现了节点近似最短路径值范围的估计方法,并在该算法设计的基础上实现基于树形结构的近似最短路径值的实时估计。(5)针对纽约道路网数据进行实证分析,重点对地标点选择、层次结构网络构建以及近似查询结果进行分析。利用随机策略与基于度的选择策略进行地标点选取,分析比较6层层次结构网的地标点分布、网络规模与构建时间;利用reach*算法实时计算不同层次结构网络的最短路径;利用范围约束的最短路径值查询方法估算任意节点间的最短距离范围,从而为方法应用提供参考和借鉴。
[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
本文链接：https://www.wllwen.com/kejilunwen/yysx/2174681.html
