I/O Efficient Algorithms for Exact Distance Queries on Disk-Resident Dynamic Graphs

Point-to-point shortest distance queries are fundamental to large graph analytics. Motivated by the need for low-latency distance queries in large-scale "dynamic" graphs, we consider the problem of answering exact shortest distance queries on disk-resident scale-free dynamic graphs. Our query processing uses the canonical labeling method, which is a special 2-hop distance labeling for fast distance queries. In this paper, we propose two I/O efficient algorithms to update the canonical labeling. To the best of our knowledge, our proposed methods are the first practical disk-based methods to "incrementally update" the canonical labeling on dynamic graphs. We also show how to answer distance queries on the latest network based on outdated labels and new edges. Extensive experiments demonstrate the efficiency of our methods. Our update methods are an order of magnitude faster than reconstructing the canonical labeling. When the number of new edges is small, say less than 1% of the previous number of edges, our query algorithm based on outdated labels provides exact shortest distance and the query time is comparable to other query algorithms using latest labels.