Spatial-Region-based Graph Path Distance Function

A Spatial-Region-based Graph Path Distance Function is a Spatial-Region-based Graph Path Distance Function that ...

• AKA: SRB, SRB Distance.
• See: Perimeter-based Graph Path Distance Function.

---

---

References

2009

• (Lu et al., 2009) ⇒ Qifeng Lu, Feng Chen, Kathleen Hancock. (2009). “On Path Anomaly Detection in a Large Transportation Network.” In: Journal of Computers, Environment, and Urban Systems, 33(6). doi:10.1016/j.compenvurbsys.2009.07.009
  • Given graph G (hV, Ei) and two paths P1 = hvs. . .vei and P2 = hvs0,. . .,ve0i, the region-based distance dSR(P1, P2) between paths P1 and P2 is defined as.
    • dRðP1; P2Þ ¼ dGðms; m0sÞ þ dGðme; m0eÞ þXe 2E jej; where
    • E ¼ feje 2 E ^ e 2 Rg; ð4Þ
  • where R is the spatial region determined (enclosed) by P1, P2, Ps(vs, vs), and Ps(ve, ve), E* is the collection of the edges identified through the spatial intersection of the graph and the region R, the same as the one discussed in Section 3.2.1.
  • The motivation of SRB distance is that the space area of the region R would intuitively provide useful information about the dissimilarity between these two paths.
  • SRB distance has two major advantages. First, it captures the spatial closeness between two paths. If two paths are more spatially distant, intuitively the value of the SR distance between these two paths will be larger. This is straightforward when the paths to be compared have close start vertices and close end vertices. In the special case where two paths have reversed positions about the start and end vertices, which means the start vertex of path P1 is close to the end vertex of path P2 and the start vertex of P1 is close to the end vertex of P2, the region may not be well identified. However, the SRB distance considers the distance between the start (or end) vertices.

---