Dave, Vachik S.Al Hasan, Mohammad2017-04-122017-04-122015Dave, V. S., & Al Hasan, M. (2015). TopCom: Index for Shortest Distance Query in Directed Graph. In Database and Expert Systems Applications (pp. 471–480). Springer, Cham. https://doi.org/10.1007/978-3-319-22849-5_32https://hdl.handle.net/1805/12228Finding 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.enPublisher Policyshortest distance querygraph algorithmsindexing method for distance queryConference proceedings