关键词: 图数据, 边受限制, 预处理, 最短距离查询

Abstract: Calculating the shortest distance between two points is one of the basic operations on the marked graph. For the large graphs, query efficiency is improved by estimating the distance between two points according to the landmarks. The existing landmarks selection strategy cannot be satisfied in both centrality and computational complexity. The distance information storage by the landmarks to other nodes is still large. Firstly, for large-scale directed graphs, the landmark node selection strategy ensures the centrality while reducing the computational complexity. The DBSCAN clustering idea is used to divide the nodes into different classes. The connected forward and backward core nodes are selected as forward and backward landmarks. Then, the distance information between the landmarks and the other nodes in the class and the distance information among the landmarks are stored to reduce the storage. Finally, the source node reaches the target node through the backward landmarks and the forward landmarks, and the minimum mean value of the upper and lower bounds is used as the estimated value. The theory proves that the time complexity of the landmarks selection strategy is reduced by an order of magnitude compared with the traditional methods, and the data storage is reduced by an order of magnitude compared with the traditional method.

Key words: graph data, edge restricted, preprocess, shortest distance query