# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 1 Introduction
In Euclidean space, the distance between a moving object \(o\) and a query point \(q.p\) is defined as the length of the straight-line connecting them, whereas in the road network, the distance between \(o\) and \(q.p\) is defined as the total length of the shortest path connecting them. Therefore, the existing distributed methods cannot support range monitoring queries in the road network. For example, let us consider a range monitoring query \(q=(q.p,q.d)\), where \(q.p\) is shown in Figure 1 and \(q.d=10\). As shown in Figure 1, if \(q\) is issued over a set of moving object \(O=\{o_{1},o_{2},o_{3},o_{4},o_{5},o_{6}\}\) in Euclidean space, its current result is \(\{o_{3},o_{4},o_{5},o_{6}\}\), where the red circle in the figure represents the _query range_ of \(q\). On the other hand, as shown in Figure 1, if \(q\) is issued over \(O\) in the road network, its current result is \(\{o_{3},o_{6}\}\), where a set of red _line segments_ in the figure represents the query range of \(q\). (Note: Each number in brackets in Figure 1 indicates the distance between \(o_{i\,(1\leq i\leq 6)}\in O\) and \(q.p\) in the road network.) We refer to each line segment that belongs to the query range in the road network as the _query segment_. In this paper, we propose the distributed method for processing range monitoring queries in the road network. To utilize the computational capabilities of moving objects, we introduce the concept of _vicinity region_. Given a moving object \(o\), \(o\)'s vicinity region, denoted by \(VR(o)\), is a rectangular region, which _contains_ (i) the point of \(o\)'s current location and (ii) a number of query segments. By letting the server assign \(o\) (i) \(VR(o)\) and (ii) query segments _inside_\(VR(o)\), \(o\) can monitor by itself whether it affects the results of nearby queries while it is moving. The moving object \(o\) sends a location-update to the server whenever (i) it leaves \(VR(o)\) or (ii) it affects the result of some nearby query \(q\). In the former case, the server assigns \(o\) a new vicinity region together with new query segments, while in the latter case, the server updates the result of \(q\) accordingly. One critical problem is how to determine the suitable size of a vicinity region \(VR(o)\) for each moving object \(o\). If \(VR(o)\) is too small, \(o\) needs to frequently send a location-update to the server for receiving a new vicinity region. On the other hand, if \(VR(o)\) is too large, \(o\) needs to monitor a large number of queries, which imposes a computationally intensive burden on \(o\). In general, a handheld computing device carried by \(o\) executes multiple applications, and thus if a single LBS application occupies substantial computational resources, the service quality of the other applications may deteriorate drastically. With this problem in mind, we propose a new spatial index structure, called the _Segment-based Space Partitioning tree (SSP-tree)_. The role of the SSP-tree to efficiently search the appropriate vicinity regions for moving objects based on their _heterogeneous_ computational capabilities. We also describe the details of the communication strategy between the server and moving objects for cooperative processing of range monitoring queries in the road network. In summary, we propose (i) the concept of vicinity region; (ii) the SSP-tree for vicinity region search; and (iii) the vicinity region based communication strategy between the server and moving objects for distributed processing of static range monitoring queries. Through simulations, we verify the effectiveness of the proposed method for processing static range monitoring queries in terms of the wireless communication cost and the server computation cost.