# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 2 Problem Statement and System Overview  
### Background and Problem Statement  
In this paper, we address the problem of processing range monitoring queries in the road network. The road network is modeled as an undirected graph \(G=(V,E)\), where \(V=\{v_{1},v_{2}\ldots,v_{|V|}\}\) is a set of vertices and \(E(\subseteq V\times V)=\{v_{i}v_{j}|1\leq i\leq|E|,1\leq j\leq|E|,i\
eq j\}\) is a set of edges. A vertex \(v\in V\) corresponds to a road intersection or dead-end. On the other hand, an edge \(v_{i}v_{j}\in E\) corresponds to a road segment, which connects two vertices \(v_{i}\) and \(v_{j}\). For convenience of notation, we sometimes indicate an edge \(v_{i}v_{j}\) as \(e\). We can assume that each road segment of the road network is a straight line because a curved road segment can be transformed into a set of straight lines by adding extra vertices and edges to \(G\). Therefore, the length of an edge \(v_{i}v_{j}\) can be the Euclidean distance between its two endpoints \(v_{i}\) and \(v_{j}\). Hereafter, we use \(dist_{E}(\cdot,\cdot)\) to denote the Euclidean distance between any two points (including the vertices) in the road network \(G\). Figure 1: Difference between Euclidean space and the road network. (**a**) The query range in Euclidean space; (**b**) The query range in the road network. **Definition 1**. : _Given two vertices \(v_{a}\) and \(v_{b}\) in the road network \(G=(V,E)\), where \(v_{a}v_{b}\
otin E\), a **path** from \(v_{a}\) to \(v_{b}\), denoted by \(P(v_{a},v_{b})\), is a sequence of vertices \((v_{p_{1}},v_{p_{2}}\dots,v_{p_{k}})\) such that \(v_{p_{1}}=v_{a}\), \(v_{p_{k}}=v_{b}\), and for each consecutive pair of vertices \((v_{p_{i}},v_{p_{i+1}})\) for all \(1\leq i<k\), the condition: \(v_{p_{i}}v_{p_{i+1}}\in E\) holds. Then, the **path length** of \(P(v_{a},v_{b})\) is calculated as:_  
\[L(P(v_{a},v_{b}))=\sum_{i=1}^{k-1}dist_{E}(v_{p_{i}},v_{p_{i+1}}), \tag{1}\]  
_where \(v_{p_{1}}=v_{a}\) and \(v_{p_{k}}=v_{b}\)._  
**Definition 2**. : _Given two vertices \(v_{a}\) and \(v_{b}\) in the road network \(G=(V,E)\), where \(v_{a}v_{b}\
otin E\), there can exist more than one path from \(v_{a}\) to \(v_{b}\). Then, the **shortest path** from \(v_{a}\) to \(v_{b}\), denoted by \(SP(v_{a},v_{b})\), is defined as:_  
\[SP(v_{a},v_{b})=\operatorname*{arg\,min}_{P(v_{a},v_{b})\in\mathit{Pset}(v_{ a},v_{b})}L(P(v_{a},v_{b})), \tag{2}\]  
_where \(\mathit{Pset}(v_{a},v_{b})\) is the set of all the paths from \(v_{a}\) to \(v_{b}\). The path length of \(SP(v_{a},v_{b})\), i.e., \(L(SP(v_{a},v_{b}))\), is called the **shortest path length**._  
Consider an example of the road network \(G\) in Figure 2a, which serves as a running example in the rest of this paper. In Figure 2a, \(G\) consists of 10 vertices and 13 edges. (Note: The vertices and edges outside of the workspace are omitted.) Each number near to each edge in the figure indicates its length (i.e., the Euclidean distance between its two endpoints). From the figure, it can be easily seen that \(SP(v_{1},v_{9})=(v_{1},v_{4},v_{7},v_{9})\) and \(L(SP(v_{1},v_{9}))=29\). Let \(\mathcal{O}=\{o_{1},o_{2},\dots,o_{|\mathcal{O}|}\}\) and \(Q=\{q_{1},q_{2},\dots,q_{|\mathcal{O}|}\}\) be a set of moving objects and a set of range monitoring queries, respectively. Each object \(o\in\mathcal{O}\) is constrained to move only along the edges in the road network \(G\), and thus the point of \(o\)'s location, denoted by \(o.p\), at a particular snapshot in time always lies on an edge in \(G\). Each query \(q\in Q\) is represented by a tuple \((q.p,q.d)\), where \(q.p\) is a query point lying on an edge in \(G\) and \(q.d\) is a query distance. **Definition 3**. : _Given two points \(p_{a}\) and \(p_{b}\), where \(p_{a}\) lies on an edge \(v_{i_{1}}v_{j_{1}}\) and \(p_{b}\) lies on an edge \(v_{i_{2}}v_{j_{2}}\), the distance between \(p_{a}\) and \(p_{b}\) in the road network \(G\), which is called the **network distance** (between \(p_{a}\) and \(p_{b}\)) and denoted by \(dist_{N}(p_{a},p_{b})\), is defined as:_  
\[dist_{N}(p_{a},p_{b})=