## 5 The Group-Aware Query Region Tree (GQR-Tree)
### Description
In GQRT, each moving object \(o\) sends \(UpdateResult\) messages to the server only when necessary because the server assigns \(o\) its resident domain together with only the _qualified_ spatial query ranges such that the corresponding queries are the elements of the query group \(g\) with its group bit-vector \(g.bv\) being matched to the object bit-vector \(o.bv\). Continuing the example above, \(o_{1}\) in Figure 3 can be assigned the entire space as its resident domain together with \(q_{1}.R\) and \(q_{3}.R\) because the corresponding queries \(q_{1}\) and \(q_{3}\), respectively, are the elements of the query group \(g_{1}\), and thus \(o_{1}\)'s movement may affect only the results of \(q_{1}\) and \(q_{3}\). In addition, by associating each GQR-tree node \(N\) with \(full\_qid\_table\), GQRT further reduces the number of \(UpdateResult\) messages sent by moving objects based on the following lemma. **Lemma 1**. : _Given a GQR-tree node \(N\), \(N.full\_qid\_table\), and a query \(q\) that is an element of some query group \(g\in\mathcal{G}\), if the query identifier of \(q\) is contained in \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\), every moving object \(o\) whose object bit-vector \(o.bv\) is matched to \(g.bv\), and that is currently moving within \(N\) cannot cross the boundary of \(q\)'s spatial query range \(q.R\)._  
Proof. : We prove this lemma by contradiction. Given a GQR-tree node \(N\), let us assume that there exist (i) a moving object \(o\) whose object bit-vector \(o.bv\) is matched to the group bit-vector \(g.bv\) of some query group \(g\in\mathcal{G}\) and (ii) a query \(q\) (\(\in\)\(g\)) whose query identifier is contained in \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\). By Definition 5, we know that the spatial query range \(q.R\) of \(q\) covers or equals \(N\). Let us further assume that we can find \(o\), which crosses the boundary of \(q.R\) but not that of \(N\). Then, the condition \(N-q.R=\
eg\emptyset\) holds. This leads to a contradiction to the cover relationship or equal relationship defined in Definition 3. Hence, \(o\) cannot cross the boundary of \(q.R\) as long as it is moving within \(N\). Based on Lemma 1, when assigning \(N\) to a moving object \(o\) as its resident domain together with qualified spatial query ranges, for each spatial query range \(q.R\) among them, if the query identifier of the corresponding query \(q\) is contained in \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\), _i.e._, if \(q.R\) covers or equals \(N\), the server can exclude \(q.R\); instead, when the server receives the \(RequestDomain\) message from \(o\), it has to check whether the result of \(q\) is affected by \(o\)'s movement and update the result of \(q\) (if necessary). Therefore, given a GQR-tree node \(N\) and a moving object \(o\) with its object bit-vector \(o.bv\) being matched to the group bit-vector \(g.bv\) of some query group \(g\in\mathcal{G}\), if (i) \(N\) contains the location of \(o\) and (ii) \(|g\_N|\leq o.Cap\), the server can assign \(N\) to \(o\) as its resident domain together with only thespatial query ranges of the queries that are elements of \(g\_N\) (\(\subseteq g\)), _i.e._, spatial query ranges that are covered by or partially intersect \(N\), among the qualified spatial query ranges. Assuming \(\theta=1\), Figure 6 shows an example of some sub-GQR-tree rooted at the node \(N_{1}\). In the figure, assuming the capability \(o_{2}.Cap\) is \(1\) and the object bit-vector \(o_{2}.bv\) is matched to the group bit-vector \(g_{1}.bv\) of the query group \(g_{1}\) (_i.e._, \(g_{1}.bv\wedge o_{2}.bv=o_{2}.bv\)), the moving object \(o_{2}\) is assigned \(N_{1}\) as its resident domain together with the spatial query range \(q_{4}.R\) because \(N_{1}\) contains the location of \(o_{2}\) and \(|g_{1}\_N_{1}|\) (\(=1\)) \(\leq o_{2}.Cap\).