Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core

Takuya Akiba, Christian Sommer, and Ken-ichi Kawarabayashi
EDBT 2012 - 15th International Conference on Extending Database Technology (pp. 144-155)

We present new and improved methods for efficient shortest-path query processing. Our methods are tailored to work for two specific classes of graphs: graphs with small tree-width and complex networks. Seemingly unrelated at first glance, these two classes of graphs have some commonalities: complex networks are known to have a core-fringe structure with a dense core and a tree-like fringe.

Our main contributions are efficient algorithms and data structures on three different levels. First, we provide two new methods for graphs with small but not necessarily constant tree-width. Our methods achieve new tradeoffs between space and query time. Second, we present an improved tree-decomposition-based method for complex networks, utilizing the methods for graphs with small tree-width. Third, we extend our method to handle the highly inter-connected core with existing exact and approximate methods.

We evaluate our algorithms both analytically and experimentally. We prove that our algorithms for low-tree-width graphs achieve improved tradeoffs between space and query time. Our experiments on several real-world complex networks further confirm the efficiency of our methods: Both the exact and the hybrid method have faster preprocessing and query times than existing methods. The hybrid method in particular provides an improved tradeoff between space and accuracy.

@inproceedings{ASK12,
 author    = {Takuya Akiba 
              and Christian Sommer 
              and {Ken-ichi} Kawarabayashi},
 title     = {Shortest-Path Queries for Complex Networks: 
              Exploiting Low Tree-width Outside the Core},
 booktitle = {15th International Conference on 
              Extending Database Technology (EDBT)},
 year      = {2012},
 pages     = {144--155},
 url       = {http://dx.doi.org/10.1145/2247596.2247614},
 doi       = {10.1145/2247596.2247614},
}

Official version
Local version (214.9 KB)
Slides (2.2 MB)

Home → Publications → Shortest-Path Queries for Complex Networks: Exploiting Low Tree-width Outside the Core