Approximate Shortest Path Query Research Based On Hierarchy Network

Large-scale networks,developed with the age of big data,have been facing with a great challenge in data storage and analysis because of the rapid increase of data size,complexity of topological structure and applications.There are special issues in the process of analyzing and querying based on original network,such as considerable space and the rapidly response to changing demands.Abstracting logical model of tree structure from network has becoming an effective way to solve such problems.Shortest path query is one of the core contents among the study of network studies.Hierarchical technology is an accelerated technique for implementing fast shortest path queries.At the same time,analysis and application based on intermediate information and hierarchical network model allow the part of original network analysis move to a relatively sparse higher network,thereby quickly and effectively achieving specific analysis.This paper will focus on large-scale network hierarchy structure and mainly talk about preprocessing and querying in approximate shortest path query,and then build hierarchy network with New York road network data and realize approximate shortest path queries.The main research contents are as follows.(1)Aiming at the problem of insufficient analysis of hierarchy structure in networks,we systematic review Shortest Path Query,k-Nearest Neighbor and Degree Centrality.This paper expand the network hierarchy model,including basic concepts,large-scale networks description and division program.(2)This paper propose a method--Balanced Center Distance Partition Algorithm(BCD)to improve the efficiency of preprocessing.This method uses coverage-based landmarks selection method in order to iteratively implement network partitioning and reduction.Advanced network,was built through the sub-network and adjacency relation for the nodes and edges,which provides a thought of the division of the flat structure network and the measurement of segmentation quality.(3)In order to improve the preprocessing efficiency and query speed,this paper propose a method of building tree structure based on BCD algorithm.This tree structure is built by selecting covered-landmarks,iterating implements network partitioning and simplification.Hierarchy network with several layers reduces the size of the original network reduces and the complexity of searching algorithms.(4)This paper construct an approximate query processing scheme based on hierarchical structure network.We use relational model to express and store the network hierarchical structure,and introduce reach* technology is introduced into hierarchy network.According to the designed shortest path query algorithm,we put forward an error bounded approximate shortest distance estimate method based one a multi-level hierarchal network.(5)Based on road network,we present experimental tests to compare and analysis the performance achievements of landmark selection,BCD partition algorithm and approximate shortest path query method under different landmark selection schemes.This paper analyzes the distribution network scale and build time of six layers network by using the random strategy and the degree strategy;calculates the shortest path of different hierarchy network uses reach* algorithm;uses error-bound query method estimate the shortest distance range,and then provide reference for method application.