Modeling & Storing Spatial Networks

• Modeling spatial networks
  • Adjacency matrix
    • Dense graphs
  • Adjacency list
    • Sparse graphs
    • Suitable for spatial networks
• Storing large spatial networks
  • Partition adjacency lists to disk block based on proximity
  • Create B+-tree index on top of partitions based on node-id

Shortest Path Search

Given 2 nodes s, t in graph G(V, E), find shortest path from s to t.

• Non-negative edge weights
  • Variations of Dijkstra's
• Negative edges
  • Bellman-Ford
• s, t on edges
  • Introduce 2 more nodes

Dijkstra's Algorithm

dijkstra(G, s, t):
    # init
    for v in G:
        spd(s, v) = inf # shortest path distance
        path(s, v) = null
        v.visited = false
    priority_queue q
    spd(s, s) = 0
    q.add(s)

    # progress
    while not q.empty():
        v = q.top() # smallest spd
        q.pop()
        v.visited = true

        if v == t:
            return path(s, t)
        else:
            for u in v.neighbors:
                if spd(s, u) > spd(s, v) + weight(v, u):
                    spd(s, u) = spd(s, v) + weight(v, u)
                    path(s, u) += (v, u)
                    q.add_or_update(u)

Worst case cost: O(|E| + |V| log|V|)

A*-Search

Directing search towards t. Visit nodes in increasing SPD(s, v) + dist(v, t) order. dist should be lower distance bounds.

Bi-Directional Search

Maintain 2 queues for both s and t. Terminate when they meat.

Can be combined with A*-search.

Spatial Queries over Spatial Networks

Spatial Selections

Find all objects in spatial relation R within network distance ε from location q.

• Store & index spatial network
  • Spatial component (e.g. nodes, edges)
  • Graph component (e.g. connectivity)
• Store & index sets of spatial objects
• Given spatial location p, use spatial component to find network edge containing p
• Given network edge, use network component to traverse neighboring edges
• Given neighboring edges, use spatial indexes to find objects on them

Method 1: Network Browsing

1. Find network edge containing q
   1. Use spatial index of network (spatial component) i.e. edge R-tree
2. Find all edges (subnetwork) within distance
   1. Use adjacency index (graph component) of network
   2. Apply Dijkstra's algorithm
3. For all edges, find objects that intersect them (spatial selection)
   1. Use object R-tree

Method 2: Euclidean Bounds

Assume dist(v, u) <= SPD(v, u) for any v, u.

1. Find all objects within distance
   1. Use object R-tree
   2. Use e.g. Euclidean distance
2. For each object o found, compute SPD(q, o) and see if real distance is within distance
   1. Use network R-tree to find where o is
   2. Compute SPD(q, o)
   3. Check if SPD(q, o) <= ε

NN Search

Find the nearest object in spatial relation R to location q.

• Network browsing
  • Fast if edges densely populated with points of interest
• Euclidean bounds
  • Fast if edges sparsely populated with points of interest

Method 1: Network Browsing

1. Find network edge containing q
   1. Use spatial index of network (spatial component) i.e. edge R-tree
2. Retrieve edges in order of their distance to q
   1. Use adjacency index (graph component) of network
   2. Apply Dijkstra's algorithm
3. For each edge, find objects that intersect them (spatial selection)
   1. Use object R-tree
4. Keep track of nearest object found so far, terminate network browsing with its SPD

Method 2: Euclidean Bounds

Assume dist(v, u) <= SPD(v, u) for any v, u.

1. Find Euclidean NN of q in order of their distance to q
   1. Use object R-tree
   2. Keep track of currentNN & bound = SPD(q, currentNN)
2. For each NN
   1. If dist(q, v) >= bound
      1. Terminate, report currentNN & bound
   2. If SPD(q, v) < bound
      1. Set currentNN = v & bound = SPD(q, currentNN)
      2. Keep iterating

Spatial Join Queries

Find all pairs (r, s) in spatial relation R & S s.t. SPD(r, s) is within network distance ε from location q.

1. Index nested loop of ε-distance selection (Euclidean distance) on each object in R for objects in S
2. For each pair (r, s), compute SPD(r, s) and verify SPD(r, s) <= ε

Advanced Indexing Techniques for Spatial Networks

• Problem
  • Dijkstra's algorithm & related methods can be very expensive on large graphs
• Solution
  • (Partial) materialization of shortest paths in static graphs

Hierarchical Path Materialization

1. Partition graph G into G1, G2, G3, ... based on connectivity & proximity of nodes
   1. Each edge in one Gi
   2. Border nodes in more than one Gi

2. For each Gi

   1. Compute & materialize SPs between every pair of nodes
   2. Compute & materialize SPs between every pair of border nodes
      1. May hierarchically partition them into another level

3. Good partitioning if:

   • small partitions
   • few combinations examined for SP search

Shortest Path Search

• If s & t border
  • Use matrix B
• If one of s & t border
  • SP(s, t) = min{p(s, u) + p(u, t) | (u in B) ∩ (u in Gt or Gs)}
• If s & t not border
  • If s & t in same G
    • Use matrix Mst
  • If not
    • SP(s, t) = min{p(s, u} + p(u, v) + p(v, t) | u, v, in B, u in Gs, v in Gt}

Compressing Materialized Paths

Distance Matrix with Successors

Space Partitioning

• For each node s, index a set of (succ, R) pairs with spatial index Is
  • succ: successor of s
  • R: continuous region s.t. each node t in R has succ as the successor of s in SP(s, t)
• Compute SP(s, t)
  • Init SP = s
  • Find (succ, R) with Is s.t. t in R
  • SP += (s, succ)
  • If succ is t, report SP
  • Else, s = succ, keep iterating