# The SSP-Tree: A Method for Distributed Processing of Range Monitoring Queries in Road Networks
## 1 Introduction  
The proliferation of handheld computing devices equipped with positioning systems has led to the rapid growth of _Location-Based Services_ (_LBSs_) [1]. In this paper, we study the problem of processing _range monitoring queries_. A range monitoring query \(q=(q.p,q.d)\), issued over a set of moving objects \(O\), (i) retrieves a subset of moving objects \(\hat{O}\) (\(\subseteq\)\(O\)) that are located within a query distance \(q.d\) from a query point \(q.p\); and (ii) continuously updates \(\hat{O}\) as the moving objects change their location. Range monitoring queries often play an important role for supporting LBSs. For example, let us consider the following scenarios. A gas station owner (i.e., client) wants to send promotionalcoupons to all cars (i.e., moving objects) currently located near her gas station; a child safety service provider (i.e., client) wants to monitor the potential dangerous areas to alert parents when their children (i.e., moving objects) enter these areas; a traffic management department wants to monitor the traffic conditions of the main highways in a city. In such scenarios, the functionality of monitoring moving objects that are currently located within a region of interest is highly required. A large number of methods for processing range monitoring queries were proposed [2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12; 13; 14], which can be broadly classified into two categories according to the mobility of query points; one deals with static query points (e.g., facilities such as the gas station mentioned above) [2; 3; 4; 5; 6; 7], whereas the other deals with moving query points (e.g., free taxis looking for the nearby passengers) [8; 9; 10; 11; 12; 13; 14]. Our proposed method belongs to the former category. Most existing methods for processing range monitoring queries are highly centralized in the sense that moving objects periodically send location-updates to the server, and that the server carries out all the computations for processing range monitoring queries [1]. Therefore, their focus is developing algorithms for efficiently process the queries at the server side. However, when the number of moving objects becomes very large, they may suffer from a severe communication bottleneck as well as overwhelming server workload due to a huge amount of location-update stream generated by the moving objects. One of the key challenges of processing range monitoring queries is how to minimize the wireless communication cost and the server computation cost, both of which heavily depend on the amount of location-update stream. As the amount of location-update stream is increased, the wireless communication cost and the server computation cost are also increased accordingly. Recently, some distributed methods, which aim to reduce the amount of location-update stream by utilizing the computational capabilities of moving objects, have been proposed [2; 3]. In the distributed methods, the server assigns each moving object \(o\) several queries, and \(o\) locally monitors its movement against these queries. Only when \(o\) affects the current result of any of the assigned queries, does it send a location-update to the server to let the server update the result of the corresponding query. As such, in the distributed methods, moving objects no longer need to periodically send location-updates to the server, and thus the amount of location-update stream can be reduced. The additional benefit of the distributed methods is that the moving objects can save energy consumption by reducing the number of wireless message transmissions (i.e., the number of location-updates sent to the server). Please note that a wireless message transmission is an energy expensive operation. Unfortunately, the existing distributed methods only deal with the objects moving freely in Euclidean space. In most real-life scenarios of LBSs, the objects are allowed to move only on a pre-defined set of paths specified by the underlying road network.