# 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
\begin{cases}dist_{E}(p_{a},p_{b})&\text{if }v_{i_{1}}=v_{i_{2}}\text{ and }v_{j_{1}}=v_{j_{2}}\text{ (i.e., }p_{a}\text{ and }p_{b}\text{ lie on the same edge);}\\ \min_{x\in\{i_{1},j_{1}\},y\in\{i_{2},j_{2}\}}\left(dist_{E}(p_{a},v_{x})+L( SP(v_{x},v_{y}))+dist_{E}(v_{y},p_{b})\right)&\text{otherwise.}\end{cases}  \tag{3}\]  
Figure 2: An example of the range monitoring query in the road network. (**a**) The road network \(G\); (**b**) The range monitoring query in \(G\). Given the road network \(G\) in Figure 2a, Figure 2b shows the network distance between a query point \(q.p\) and several points on \(G\) (e.g., vertices and points of moving objects' location). For example, \(dist_{N}(q,p,v_{5})=dist_{E}(q.p,v_{5})\) and \(dist_{N}(q.p,o_{1}.p)=dist_{E}(q.p,o_{1}.p)\) because \(q.p\), \(v_{5}\), and \(o_{1}.p\) lie on the same edge \(v_{5}v_{6}\). On the other hand, \(dist_{N}(q,p,v_{3})=dist_{E}(q.p,v_{6})+L(SP(v_{6},v_{3}))+dist_{E}(v_{3},v_{3})\) and \(dist_{N}(q.p,o_{3}.p)=dist_{E}(q.p,v_{6})+L(SP(v_{6},v_{8}))+dist_{E}(v_{8},o_{3 }.p)\). In Figure 2b, each number in brackets indicates the network distance between \(q.p\) and each point. (Note: The network distance between \(q.p\) and some vertices are omitted for brevity.) **Definition 4**. : _A **range monitoring query**\(q=(q.p,q.d)\), issued over a set of moving objects \(O\), in the road network \(G\), continually retrieves a subset \(\hat{O}\)\((\subseteq O)\) of moving objects for which the condition: \(\forall o\in\hat{O},dist_{N}(q.p,o.p)\leq q.d\) holds._  
**Definition 5**. : _Given a query \(q=(q.p,q.d)\), the **query range** of \(q\) in the road network \(G\), denoted by \(QR(q)\), is a set of all points on the edges (in \(G\)) reachable from \(q.p\) within \(q.d\). Formally, \(QR(q)=\{p|dist_{N}(q.p,p)\leq q.d\) and \(p\) is a point in \(G\}\)._  
From Definitions 4 and 5, we can immediately know that given a query \(q=(q.p,q.d)\) and a moving object \(o\)\((\in O)\) in the road network \(G\), if and only if the point of \(o\)'s current location is inside the query range of \(q\), can \(o\) be the current result of \(q\) (i.e., \(o.p\in QR(q)\Leftrightarrow dist_{N}(q.p,o.p)\leq q.d\)). In the road network \(G\), the query range \(QR(q)\) of a query \(q\) consists of a set of _line segments_. **Definition 6**. : _Given an edge \(v_{i}v_{j}\) in the road network \(G\), a **line segment**, denoted by \(s[p_{a},p_{b}]\), where \(p_{a}\) and \(p_{b}\) are points on \(v_{i}v_{j}\), is a set of all points on \(v_{i}v_{j}\) between \(p_{a}\) and \(p_{b}\), i.e., the portion of \(v_{i}v_{j}\) between \(p_{a}\) and \(p_{b}\)._  
For example, in Figure 2b, the query range consists of all red line segments (i.e., \(s[v_{5},v_{6}]\), \(s[v_{6},p_{1}]\), and \(s[v_{6},p_{2}]\)), assuming \(q.d=15\). Please note that, by definition, an edge \(v_{i}v_{j}\) in \(G=(V,E)\) is also considered to be a line segment formed by its two endpoints \(v_{i}\) and \(v_{j}\) (i.e., \(v_{i}v_{j}=s[v_{i},v_{j}]\)). In this paper, we refer to each line segment that belongs to the query range \(QR(q)\) of a query \(q\) as the _query segment_ of \(q\), which we denote by \(qs[p_{a},p_{b}]\) or \(qs\) for short. Therefore, given the query range \(QR(q)\) of a query \(q\), each query segment \(qs[p_{a},p_{b}]\in QR(q)\) satisfies the condition: \(\forall p\in qs[p_{a},p_{b}]\), \(p\in QR(q)\). The primary goal of our work is to reduce the amount of location-update stream (generated by moving objects) while maintaining the correct results of range monitoring queries in the road network. To this end, we use the concept of vicinity region so that moving objects send location-updates to the server only when necessary. Given a moving object \(o\), \(o\)'s vicinity region \(VR(o)\) is a rectangular region, which contains (i) the point of \(o\)'s current location and (ii) some query segments.