TopCom: Index for Shortest Distance Query in Directed Graph

Date
2015
Language
English
Embargo Lift Date
Committee Members
Degree
Degree Year
Department
Grantor
Journal Title
Journal ISSN
Volume Title
Found At
Springer
Abstract

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.

Description
item.page.description.tableofcontents
item.page.relation.haspart
Cite As
Dave, 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_32
ISSN
Publisher
Series/Report
Sponsorship
Major
Extent
Identifier
Relation
Journal
Database and Expert Systems Applications
Source
ArXiv
Alternative Title
Type
Conference proceedings
Number
Volume
Conference Dates
Conference Host
Conference Location
Conference Name
Conference Panel
Conference Secretariat Location
Version
Author's manuscript
Full Text Available at
This item is under embargo {{howLong}}