Tedi Busqueda Eficiente

TEDI: Efficient Shortest Path Query Answering on Graphs
Fang Wei
University of Freiburg

SIGMOD 2010

Applications

Shortest Path Queries
A shortest path query on a(n) (undirected) graph finds the shortest path for the given source and target vertices in the graph.
1 2 3 4 5

ranked keyword search XML databases bioinformatics social network ontologies

State-of-the-art ResearchShortest Path
• Concept of compact BFS-trees (Xiao et al. EDBT09)

where the BFS-trees are compressed by exploiting the symmetry property of the graphs.
• Dedicated algorithms specifically on GIS data. It is

unknown, whether the algorithms can be extended to dealing the other graph datasets.

State-of-the-art Research
Reachability Query Answering
Well studied in the DB community
• 2-HOPapproach: pre-compute the transitive closure, so

that the reachability queries can be more efficiently answered comparing to BFS or DFS.
• interval labeling approach: first extract some tree from the

graph, then store the transitive closure of the rest of the vertices.

State-of-the-art Research
Reachability Query Answering
Well studied in the DB community
• 2-HOP approach: pre-computethe transitive closure, so

that the reachability queries can be more efficiently answered comparing to BFS or DFS.
• interval labeling approach: first extract some tree from the

graph, then store the transitive closure of the rest of the vertices. Can not be extended to cope with the shortest path query answering: require only a boolean answer (yes or no); the transitive closure stored inthe index can be drastically compressed.

TEDI: Intuition of decomposing graphs

G2  G1 
• Subgraphs G1 and G2 are connected through a small set

of vertices S.
• Then any shortest path from u ∈ G1 to v ∈ G2 has to pass

through some vertex s ∈ S.
• Do it recursively in G1 and G2 .

TEDI: our approach

TEDI (TreE Decomposition based Indexing)
• an indexing and query processingscheme for the shortest

path query answering.
• we first decompose the graph G into a tree in which each

node contains a set of vertices in G.
• there are overlapping among the bags • connectedness of the tree

TEDI: our approach

TEDI (TreE Decomposition based Indexing)
• Based on the tree index, we can execute the shortest path

search in a bottom-up manner and the query time isdecided by the height and the bag cardinality of the tree, instead of the size of the graph.
• pre-compute the local shortest paths among the vertices in

every bag of the tree.

Tree Decomposition

Tree Decomposition
b

a c e

g f

h

1

Tree with a vertex set (bag) associated with every node For every edge (v , w): there is a bag containing both v and w For every v : the bags thatcontain v form a connected subtree

d

2

abc

acf

agf

gh

3

cde

Tree Decomposition

Tree Decomposition
b

a c e

g f

h

1

Tree with a vertex set (bag) associated with every node For every edge (v , w): there is a bag containing both v and w For every v : the bags that contain v form a connected subtree

d

2

abc

acf

a gf

gh

3

cdeTree Decomposition

Tree Decomposition
b

a c e

g f

h

1

Tree with a vertex set (bag) associated with every node For every edge (v , w): there is a bag containing both v and w For every v : the bags that contain v form a connected subtree

d

2

ab c

ac f

a gf

gh

3

cde

Tree Decomposition

Tree Decomposition
b

a c e

g f

h

1

Tree with a vertexset (bag) associated with every node For every edge (v , w): there is a bag containing both v and w For every v : the bags that contain v form a connected subtree

d

2

ab c

ac f

ag f

gh

3

c de

Treewidth

• The width of a tree decomposition TG is its maximal bag

size (cardinality).
• The treewidth of G is the minimum width over all tree

decompositions of G....