## 5 The Group-Aware Query Region Tree (GQR-Tree)
### Description
A tuple \(\langle g.bv,full\_qid\_list\rangle\) for a query group \(g\in\mathcal{G}\) can be maintained in \(N.full\_qid\_table\) only if there exists at least one element \(q\in g\) whose spatial query range \(q.R\) covers or equals \(N\). 7. Each non-leaf node \(N\) is associated with another data structure \(N.partial\_qid\_table\), which is a set of tuples of the form \(\langle g.bv,partial\_qid\_list\rangle\), where \(g.bv\) and \(partial\_qid\_list\) are defined as in the case of a leaf node. 8. For each non-leaf node \(N\), if a flag \(Conceptual\_Leaf\) for a query group \(g\in\mathcal{G}\) is set to \(True\), \(N\) is considered as the leaf node from the viewpoint of \(g\), and only if \(|g\_N|\geq 1\), a tuple \(\langle g.bv,partial\_qid\_list\rangle\) for \(g\) can be maintained in \(N.partial\_qid\_table\). 9. For each non-leaf node \(N\), if \(N\) is considered as the leaf node from the viewpoint of \(g\in\mathcal{G}\), no information about \(g\) is stored in \(N\)'s descendant nodes and their associated \(partial\_qid\_table\)s (if exist) and \(full\_qid\_table\)s.  
**Definition 5**. : _Given a query group \(g\in\mathcal{G}\) and a (non-leaf or leaf) node \(N\) of the GQR-tree, the list \(full\_qid\_list\) with arbitrary size contains only the query identifier of each element (query) \(q\in g\) whose spatial query range \(q.R\) covers or equals \(N\)._  
The GQR-tree method (GQRT) has three advantages over the existing methods (e.g., MQM, QRT, and BQRT). First, GQRT overcomes the first drawback of the existing methods (MQM, QRT, and BQRT) mentioned in Section 4. In contrast to the existing methods, in GQRT, the capability \(o.Cap\) of each moving object \(o\) is measured by the number of only the spatial query ranges that are non-spatially relevant to \(o\) without any additional complex computation. Specifically, when assigning the resident domain to \(o\), the GQR-tree enables \(o.Cap\) to be measured by the number of only the queries that are the elements of the query group \(g\) whose group bit-vector \(g.bv\) is matched to the _object bit-vector_\(o.bv\) of \(o\). We say that \(g.bv\) is matched to \(o.bv\) or vice versa if \(g.bv\wedge o.bv=o.bv\), where \(\wedge\) denotes bit-wise AND-ing. This helps the server assign \(o\) much larger resident domain, and thus the number of \(RequestDomain\) messages sent by \(o\) can be reduced. We represent non-spatial attribute values \(o.A\) of \(o\) as object bit-vector. The object bit-vector is generated based on the same mapping functions used for generating the query bit-vector. **Definition 6**. : _Given a moving object \(o=\)(\(o.loc\), \(o.A\)) and a set of predefined mapping functions \(\{f_{1},f_{2},\ \cdots,f_{n}\}\) for a set of \(A=\{a_{1},a_{2},\ \cdots,a_{n}\}\), an **object bit-vector**\(o.bv\) generated for \(o.A\) is \(f_{1}\)(\(o.a_{1}\)) \(+\)\(f_{2}\)(\(o.a_{2}\)) \(+\)\(\cdots\)\(+\)\(f_{n}\)(\(o.a_{n}\))._  
For example, the object bit-vector \(o_{1}.bv\) generated for non-spatial attribute values \(o_{1}.A=\{o_{1}.a_{1}=36,\)\(o_{1}.a_{2}=Vegetarian,\)\(o_{1}.a_{3}=Male\}\) of the object \(o_{1}\) with its capability \(o_{1}.Cap=2\) in Figure 3 is \(01000110\) (\(0100+01+10\)). Then, because the group bit-vector \(g_{1}.bv\) of the query group \(g_{1}\) in Figure 4 is matched to \(o_{1}.bv\) (_i.e._, \(g_{1}.bv\wedge o_{1}.bv=o_{1}.bv\)), \(o_{1}.Cap\) is measured by the number of only the queries that are the elements of \(g_{1}\). Because the total number of \(g_{1}\)'s elements (\(=2\)) is not greater than \(o_{1}.Cap\), \(o_{1}\) can be assigned the entire space in Figure 3 as its resident domain. Second, GQRT overcomes the second drawback of MQM and QRT mentioned in Section 4.