# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 3 The Proposed Method  
As mentioned in the previous section, we focus on the issue of how to efficiently search the appropriate _vicinity regions_ for moving objects. In this paper, similarly to the existing distributed methods in Euclidean space, we choose to partition the workspace into many disjoint subspaces for the search process of the vicinity regions. Please note that the space partitioning approaches used in the existing distributed methods cannot be applied in the road network because they assume that the query range (of a query) is even a rectangle instead of a circle [2; 3].  
As shown in Figure 4a, if the query ranges \(QR(q_{1})\) and \(QR(q_{2})\) of the queries \(q_{1}\) and \(q_{2}\), respectively, in the road network are approximated by the rectangles, _false positives_ may be generated in the current results of \(q_{1}\) and \(q_{2}\). In the LBS applications, false positives are more harmful than false negatives because the former can lead to the wrong query results. For example, let us assume that the moving object \(o_{1}\) in Figure 4a is assigned (i) the entire workspace as its vicinity region \(VR(o_{1})\) and (ii) two approximated rectangles of query ranges \(QR(q_{1})\) and \(QR(q_{2})\). Then, when \(o_{1}\) moves as shown in the figure, \(o_{1}\) does not send the UpdateResult message to the server because it does not leave the approximated rectangle of \(QR(q_{2})\). As a result, the server does not know the point of \(o_{1}\)'s current location \(o_{1}.p\), and thus \(o_{1}\) is wrongly included in the current result of \(q_{2}\) although \(o_{1}.p\
otin QR(q_{2})\) (i.e., \(dist_{N}(q_{2}.p,o_{1}.p)>q_{2}.d\)).  
Figure 4b shows an example of the space partitioning approach used in this paper, which recursively partitions the workspace into two equal subspaces until the number of query segments _inside_ each subspace is no more than the split threshold \(\theta\). (Note: In the figure, \(\theta\) is assumed to be 4.) In this paper, we assume that a subspace is horizontally or vertically partitioned along its longer dimension. Specifically, given a subspace, if its width is longer than its height, it is partitioned vertically, otherwise, it is partitioned horizontally. With such a space partitioning approach, the server can use a subspace as a vicinity region \(VR(o)\) of each moving object \(o\). The size of \(VR(o)\) (i.e., the size of the subspace used as \(VR(o)\)) is determined by \(o\)'s capability \(o.cap\); thus if \(o.cap=n\), \(VR(o)\) must contain the point of \(o\)'s current location \(o.p\) and no more than \(n\) query segments.  
Figure 4: Examples of approximation of query ranges and the space partitioning approach used in this paper. (**a**) Approximation of query ranges; (**b**) The space partitioning approach used in this paper.  
For example, assuming \(o_{2}.cap\) of the moving object \(o_{2}\) in Figure 4b is 3, \(o_{2}\) is assigned (i) _subspace 112_ as its vicinity region \(VR(o_{2})\) and (ii) three query segments \(qs[p_{2},v_{5}]\), \(qs[v_{5},p_{4}]\), and \(qs[v_{5},p_{5}]\).  
To efficiently support partitioning the workspace, the _SSP-tree_ is used, which will be presented in detail throughout this section.