Finding shortest distance between two vertices in a graph is an important problem due to its numerous applications in diverse domains, including geo-spatial databases, social network analysis, and information retrieval. Classical algorithms such as, Dijkstra solve this problem in polynomial time, but these algorithms cannot provide real-time response for a large number of bursty queries on a large graph. So, indexing based solutions that pre-process the graph for efficiently answering exactly or approximately a large number of distance queries in real-time are becoming increasingly popular. Existing solutions have varying performance in terms of index size, index building time, query time, and accuracy. In this work, we propose TopCom, a novel indexing-based solution for exactly answering distance queries in a directed acyclic graph DAG. Our experiments with two of the existing state-of-the-art methods IS-Label and TreeMap show the superiority of TopCom over these two methods considering scalability and query time.
['Vachik S. Dave', 'Mohammad Al Hasan']
TopCom: Index for Shortest Distance Query in Directed Graph