# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 3 The Proposed Method
### Query Segment Computation  
In this subsection, we describe an algorithm ComputeSeg for the query segment computation. When a new query \(q=(q.p,q.d)\) is issued by a client, ComputeSeg, which takes a query point \(q.p\) and a query distance \(q.d\) as inputs, computes the query segments of \(q\) based on [PERSON]'s algorithm. Before we describe the details of ComputeSeg, we introduce a distance metric, \(mindist_{N}(q.p,v_{i}v_{j})\), which is defined between a query point \(q.p\) and an edge \(v_{i}v_{j}\) in the road network \(G\), and serves as the lower bound for filtering the unnecessary edges in the query segment computation. **Definition 7**. : _Given a query point \(q.p\) and an edge \(v_{i}v_{j}\) in the road network \(G\), \(\textbf{mindist}_{N}(\textbf{q.p},\textbf{v}_{i}\textbf{v}_{j})\) is defined as:_  
\[mindist_{N}(q.p,v_{i}v_{j})= \begin{cases}0&\text{if }q.p\in v_{i}v_{j};\\ \min\Big{(}dist_{N}(q.p,v_{i}),dist_{N}(q.p,v_{j})\Big{)}&\text{otherwise.}\end{cases}  \tag{4}\]  
**Lemma 3**. : _Given a query point \(q.p\) and an edge \(v_{i}v_{j}\) in the road network \(G\), \(\forall p\in v_{i}v_{j}\), \(mindist_{N}(q.p,v_{i}v_{j})\leq dist_{N}(q.p,p)\), where \(p\) denotes a point._  
Proof. : We prove this lemma by contradiction. Let us assume that there exists a point \(\hat{p}\in v_{i}v_{j}\) such that \(dist_{N}(q.p,\hat{p})<mindist_{N}(q.p,v_{i}v_{j})\). We distinguish two cases:  
1. If \(q.p\in v_{i}v_{j}\), \(mindist_{N}(q.p,v_{i}v_{j})=0\). This immediately contradicts the assumption because \(dist_{N}(q.p,\hat{p})\) cannot be less than 0. 2. If \(q.p\
otin v_{i}v_{j}\), \(mindist_{N}(q.p,v_{i}v_{j})=\min\Big{(}dist_{N}(q.p,v_{i}),dist_{N}(q.p,v_{j} )\Big{)}\). Let us consider the subcase, where \(mindist_{N}(q.p,v_{i}v_{j})=dist_{N}(q.p,v_{i})\). Then, when we simplify the Equation (3) to obtain: \(dist_{N}(q.p,\hat{p})=\min\Big{(}\ dist_{N}(q.p,v_{i})+dist_{E}(v_{i},\hat{p}),\ dist_{N}(q.p,v_{j})+dist_{E}(v_{j},\hat{p})\Big{)}\), \(dist_{N}(q.p,\hat{p})=dist_{N}(q.p,v_{i})+dist_{E}(v_{i},\hat{p})\). This leads to a contradiction to the assumption because \(dist_{N}(q.p,v_{i})\leq dist_{N}(q.p,v_{i})+dist_{E}(v_{i},\hat{p})\). The subcase, where \(mindist_{N}(q.p,v_{i}v_{j})=dist_{N}(q.p,v_{j})\), leads to the same contradiction as the former subcase. Therefore, \(\hat{p}\) cannot exist. Algorithm 1 is the pseudocode of ComputeSeg, assuming \(e\) is the edge that contains \(q.p\) (\(e\) is identified by using EI). First, ComputeSeg initializes an empty min-heap \(H\) to traverse the vertices in the road network \(G\) in the ascending order of their network distance from \(q.p\) (line 1). Next, ComputeSeg enheaps the endpoints (i.e., vertices) of \(e\) into \(H\) with keys equal to their network distance from \(q.p\) (lines 2-3). Then, ComputeSeg iteratively deheaps a vertex from \(H\). For each deheaped vertex \(v_{i}\), ComputeSeg marks \(v_{i}\) as _visited_ and checks each of its adjacent vertices \(v_{j}\) whether or not \(v_{j}\) has been visited (\(v_{j}\) is identified by using ET). If \(v_{j}\) has not been visited, ComputeSeg further checks if \(dist_{N}(q.p,v_{i})\leq q.d\). Only if this is the case, is \(v_{j}\) enheaped into \(H\) with a key \(dist_{N}(q.p,v_{i})+dist_{N}(v_{i},v_{j})\) (lines 8-10). The rationale is that if (i) \(v_{j}\) has not been visited and (ii) \(dist_{N}(q.p,v_{i})>q.d\), it is guaranteed that \(dist_{N}(q.p,v_{j})>q.d\). This implies that no portion of each edge \(v_{j}v_{k}\) formed by \(v_{j}\) and each of its adjacent vertices \(v_{k}\) (including \(v_{i}\)) can be the query segment of \(q\) because \(mindist_{N}(q.p,v_{j}v_{k})>q.d\). From Lemma 3, we know that the network distance between \(q.p\) and every point \(p\in v_{j}v_{k}\) is equal to or greater than \(mindist_{N}(q.p,v_{j}v_{k})\), and thus that \(\forall p\in v_{j}v_{k}\), \(dist_{N}(q.p,p)>q.d\). Therefore, \(v_{j}\) need not be enheaped and expanded.