Spatial component (indexes coordinates of nodes, edges, etc.)
Store (and index) the sets of spatial objects
Ex., one spatial relation for restaurants, one spatial relation for hotels, one relation for mobile users, etc.
Given a spatial location p, use spatial component of network to find the network edge containing p
Given a network edge, use network component to traverse neighboring edges
Given a neighboring edge, use spatial indexes to find objects on them
Evaluation of Spatial Selections (1)
Query: find all objects in spatial relation R, within network distance ε from location q
Method:
Use spatial index of network (R-tree indexing network edges) to find edge n_1n_2, which includes q
Use adjacency index of network (graph component) and apply Dijkstra’s algorithm to progressively retrieve edges that are within network distance ε from location q
For all these edges apply a spatial selection on the R-tree that indexes R to find the results
Example
Example: Find restaurants at most distance 10 from q
Step 1: find network edge which contains q
Step 2: traverse network to find all edges (or parts of them within distance 10 from q)
Step 3: find restaurants that intersect the subnetwork computed at step 2
Evaluation of Spatial Selections (2)
Description
Query: find all objects in spatial relation R, within network distance ε from location q
Alternative method based on Euclidean bounds:
Assumption: Euclidean distance is a lower-bound of network distance:
dist(v,u) ≤ SPD(v,u), for any v,u
Use R-tree on R to find set S of objects such that for each o in S: dist(q,o) ≤ ε
For each o in S:
find where o is located in the network (use Network R-tree)
compute SPD(q,o) (e.g. use A*)
If SPD(q,o) ≤ ε then output o
Example
Example: Find restaurants at most distance 10 from q
Step 1: find restaurants for which the Euclidean distance to q is at most 10: S={r1,r2,r3}
Step 2: for each restaurant in S, compute SPD to q and verify if it is indeed a correct result
Evaluation of NN search (1)
Query: find in spatial relation R the nearest object to a given location q
Method:
Use spatial index of network (R-tree indexing network edges) to find edge n_1n_2, which includes q
Use adjacency index of network (graph component) and apply Dijkstra’s algorithm to progressively retrieve edges in order of their distance to q
For each edge apply a spatial selection on the R-tree that indexes R to find any objects
Keep track of nearest object found so far; use its shortest path distance to terminate network browsing
Example
Example: Find nearest restaurant to q
Step: in ppt 31
Evaluation of NN search (2)
Query: find in spatial relation R the nearest object to a given location q