## 1 Introduction
It is also important to notice that in a monitoring query evaluation setting, query results are required to be updated as soon as possible whenever being changed because a time-delay may yield obsolete results for monitoring queries; thus, it is critical to keep the time delay of updating query results minimum by reducing the server workload (e.g., CPU-time). The _safe region method_ (_SR_), which helps moving objects reduce the frequency of sending their location-updates, was introduced in [6, 17]. A _safe region_, assigned to each moving object \(o\), is the region that (i) contains \(o\) and (ii) guarantees that the current results of all the queries issued to the server will remain valid if \(o\) moves only within this region. Therefore, \(o\) can move freely without sending its location-update to the server as long as it does not exit its safe region. For example, the moving object \(o_{1}\) in Figure 1 need not send its location-update if it locates within its safe region (_i.e._, blue-dotted rectangle). Although SR improves the overall system performance to a certain degree, because the size of a safe region assigned to each moving object \(o\) is typically small, \(o\) easily exits its current safe region and contacts the server in order to receive a new safe region. Thus, the server must frequently search \(o\)'s safe regions, which requires intensive computational overhead. _Monitoring query management (MQM)_ and the _query region-tree method_ (_QRT_) whose primary goal is to reduce the communication cost and the server workload by leveraging the available (memory and computational) capabilities of moving objects, was introduced in [1, 2], respectively. In MQM and QRT, the server pushes some tasks of range monitoring query evaluation to the moving objects. Specifically, the server assigns each moving object \(o\) (i) a rectangular subspace of the entire workspace, called the _resident domain_ that contains \(o\); and (ii) several spatial query ranges that overlap with \(o\)'s resident domain. The size of \(o\)'s resident domain is determined by \(o\)'s capability, \(o.Cap\), which indicates the maximum number of (nearby) spatial query ranges \(o\) can load and process at a time; thus if \(o.Cap=n\), the resident domain assigned to \(o\) must contain \(o\) and overlap with no more than \(n\) spatial query ranges. For example, assuming the capability \(o_{2}.Cap\) of the moving object \(o_{2}\) in Figure 1 is 3, \(o_{2}\) is assigned (i) the red-dotted rectangle as its resident domain and (ii) three spatial query ranges \(q_{3}.R\), \(q_{4}.R\), and \(q_{5}.R\), which overlap with \(o_{2}\)'s resident domain. Only when \(o_{2}\) exits its resident domain or crosses any of the boundary of its assigned spatial query ranges, does it contact the server to receive a new resident domain (together with new spatial query ranges) or to let the server update the corresponding query result, respectively. In the figure, \(o_{2}\) sends its location-update because \(o_{2}\) crosses the boundary of \(q_{4}.R\), and in response to \(o_{2}\)'s location-update, the server updates the result of the corresponding query \(q_{4}\). As such, in MQM and QRT, moving objects and the server share the tasks of query evaluation, which lightens the server workload. Because the moving objects are aware of when they should send their location-updates, the wireless communication cost can be also reduced. For indexing queries and searching the resident domain of each moving object, MQM and QRT use the _binary partitioning tree_ (_BP-tree_) and the _query region tree_ (_QR-tree_) that overcomes the limitations of the BP-tree, respectively. Unfortunately, none of the methods reviewed above can adequately deal with CM range monitoring queries because they rely only on spatial information. For evaluation of CM range monitoring queries, in the previous paper [1], we proposed an enhanced version of the QR-tree, called the _bit-vector  
Figure 1: An example of the safe region and resident domain.