# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 2 Problem Statement and System Overview
### System Overview  
Figure 3 shows an overview of the system model. Similarly to the system model presented in the previous work [2; 3; 4; 5; 6; 7], the system model we consider consists of three major components: moving objects, clients, and the central server. * **Moving objects**: Each moving object \(o\), which is identified by its unique identifier \(oid\), is capable of sensing the point of its current location \(o.p\) and has some available computational capability \(o.cap\). We assume (i) that each moving object \(o\) has a heterogeneous capability \(o.cap\), which is measured by the maximum number of query segments it can process, and (ii) that \(o.cap\geq\theta\), where \(\theta\) is a system parameter indicating the minimum number of query segments \(o\) should process; thus, a moving object with a more powerful capability can be assigned a larger vicinity region that contains a more number of query segments. There are two types of location-update messages sent from the moving objects to the server: RequestVR and UpdateResult. The former is for the purpose of receiving a new vicinity region, whereas the latter is to let the server update the result of a query (if necessary). For example, assuming the moving object \(o_{1}\) in Figure 3 is assigned the vicinity region \(VR(o_{1})\) together with query segments \(qs[v_{6},\,p_{1}]\), \(qs[v_{6},\,p_{2}]\), and \(qs[v_{6},\,p_{3}]\), it sends the RequestVR message to the server because it leaves \(VR(o_{1})\). On the other hand, assuming the moving object \(o_{2}\) in Figure 3 is assigned the vicinity region \(VR(o_{2})\) together with query segments \(qs[v_{1},v_{4}]\), \(qs[v_{2},v_{5}]\), and \(qs[v_{4},v_{5}]\), it sends the UpdateResult message to the server because it leaves \(qs[v_{1},v_{4}]\). * **Clients**: Each client is able to issue multiple range monitoring queries over the moving objects, and continually receives the up-to-date results of these queries from the server via wireless or \begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Explanation** \\ \hline \(G=(V,E)\) & A graph model of the road network (\(V\): a set of vertices, \(E\): a set of edges) \\ \(v_{i}\) (\(\in V\)) & A vertex in \(G\) \\ \(v_{i}\)\(v_{j}\) or \(e\) (\(\in E\)) & An edge in \(G\) \\ \(o\) & A moving object \\ \(o.p\) & The point of \(o\)’s current location \\ \(o.cap\) & \(o\)’s computational capability \\ \(q=(q.p,q.4)\) & A range monitoring query (\(q.p\): query point, \(q.d\): query distance) \\ \(QR(q)\) & The query range of \(q\) \\ \(qs[p_{a},p_{b}]\) or \(qs\) (of \(q\)) & A query segment (of \(q\)) \\ \(dist_{E}(\cdot,\cdot)\) & The Euclidean distance between any two points in \(G\) \\ \(dist_{N}(\cdot,\cdot)\) & The network distance between any two points in \(G\) \\ \(N\) & A SSP-tree node or its corresponding subspace \\ \(N.C\) & The count variable maintained in \(N\) \\ \(N.FL\) & The full list maintained in \(N\) \\ \(QRT\) & Query relevance table \\ \(SRT\) & Segment relevance table \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Frequently used notation. high-speed wired connections. Each query \(q\), issued by a client, is identified by its unique identifier \(qid\), and its query point \(q.p\) is assumed to be static; thus, the movement of \(q.p\) can be treated as a deletion of the old query followed by an insertion of a new query. * **Central server**: The server acts as an intermediary between moving objects and clients, i.e., moving objects and clients do not communicate directly, but indirectly through the server. In addition to the SSP-tree, the server maintains the following basic memory-resident data structures, which are commonly used in the existing methods for the road network [13; 14]. * _Edge Index_ (_EI_): EI is the PMR-quadtree built on the edges in the road network \(G=(V,E)\). Each leaf node of EI stores the identifiers of the edges it intersects. Given a query \(q\), EI is used to identify the edge \(e\) (i.e., \(v_{i}v_{j}\in E\)), where \(q.p\) resides.