Graph Partitioning-based Query Acceleration of Power Graph Database

As the topology of the power grid continues to increase, the time complexity of querying the shortest path in the grid GIS graph database increases dramatically, which restricts the topological analysis performance of the grid GIS graph database and makes the risk of power system paralysis increase considerably. In order to accelerate the query speed, we propose a Shortest-Path (SP) algorithm based on graph partition and routing nodes. The SP algorithm first divides the overall grid topology, followed by specifying the two nodes that form the interacting edges of the subgraph in the topology graph as routing nodes and making the routing nodes store the shortest paths between them and other nodes in the subgraph they belong to, and finally converting the overall shortest path query into a routing node query to optimize the shortest path query efficiency. The effectiveness of the proposed algorithm is verified by simulation calculations on a real dataset in a province.