Spatial Networks
In real applications, accessibility of objects is restricted by a spatial network. We are concerned with the shorted path distance instead of the Euclidean distance, which is no longer relevant.
To model spatial networks, we prefer adjacency lists instead of adjacency matrices due to the sparse nature of the networks.
Problem: Adj. lists may not fit in memory if graph is large.
Solution:
- Partition adj. lists to disk blocks, based on proximity
- Create B+ tree index on top of partitions based on node IDs
Shortest Path Computation
Given a graph with non-negative edge weights, the shortest path from node to node is the path that minimizes the sum of the weights of the edges along the path.
Time complexity: (=number of edges, =number of vertices)
- Initialize a priority queue Q, with a source node 's' and distance 0. All other nodes have distance infinity.
- Pop the node with the smallest distance from Q. If the node is unvisited, mark it as visited.
- For each neighbor of the current node, calculate the tentative distance through the current node. If this tentative distance is less than the known distance, update the distance.
- Repeat steps 2 and 3 until all nodes are visited or the target node is visited.
Improves Dijkstra's algorithm by directing the search towards the target node .
For the heap queue, instead of using only distance from source as comparison (dist[v] => spd(s, v)), include the Euclidean distance to target as comparison (dist[v] => spd(s, v) + ed(v, t)).
Instead of searching from the source node to the target node , search from both the source and target nodes simultaneously.
- Use two queues and
- Use
dist[v] => min(spd(s, v), spd(t, v))as heap queue comparison - If
vvisited by both and , return the shortest path
Spatial queries over spatial networks
About how to use the various indexes and algorithms to answer spatial queries over spatial networks.
Methodology
Spatial queries based on network distances:
- Selection e.g. find nodes within d distance from s
- Nearest neighbour search e.g. find nearest node to s
- Joins e.g. find pairs of nodes with distance <= d
Consists of:
- Stored edges & nodes in adjacency lists (Graph)
- Indexed nodes (R-tree)
- Indexed edges (B+ tree)
Object R-trees.
Objects (e.g. starting points, POIs) usually lies on an edge, not on a node directly.
Therefore, we need to find the nearest edge to the object and use that edge as a proxy for the object.
A query then runs in three steps:
- Find query node via edge R-tree
- Traverse the graph to find candidate objects
- Use object R-tree to find objects on those edges
There are two methods we can evaluate each type of query:
- Network browsing: Fast if network is dense
- Euclidean bounds: Fast if network is sparse
Assumption: Euclidean distance is a lower bound of the network distance spd(v, u) >= ed(v, u) v, u.
Selection queries
Consider query: "Find objects in spatial relation R, within (network) distance d from s"
- Find edge containing
svia edge R-tree - Run dijkstra from
sto find all edgese_cwithin distanced - For all
e_capply spatial selection onR's R-tree
- Filter: Use object R-tree to get candidates based on e-distance.
r_c: ed(s, r_c) <= d - Refine: For each candidate
r_c, find the nearest edgee_cvia edge R-tree, and check ifspd(s, e_c) <= d. If yes, returnr_c.
NN queries
Consider query: "Find objects in spatial relation R, nearest to s"
- Find edge containing
svia edge R-tree - Use dijkstra to progressively get edges
e_cin order of increasing distance froms - For each edge
e_c, apply spatial selection onR's R-tree. If any object found, return the nearest one.
- Find euclidean NN
ennvia R-tree ofR. bound = SPD(s, enn)(A*)- Find
enn_2 - If
(ed(s, enn_2) >= bound) ?return enn: enn = enn2, goto 2
Join queries
Consider query: "Find pairs s.t. , , and spd(r, s) <= d"