Graph Partitioning-based Query Acceleration of Power Graph Database

Graph Partitioning-based Query Acceleration of Power Graph Database

연구 분야: Databases

학회: 2022 IEEE 10th International Conference on Computer Science and Network Technology (ICCSNT)

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.