## 5 The Group-Aware Query Region Tree (GQR-Tree)
### Resident Domain Search  
When a new moving object \(o\) is registered at the server (or the server receives the \(RequestDomain\) message from \(o\)), the search algorithm for \(o\)'s resident domain is invoked. Algorithm 1 is the pseudocode of the search algorithm on the GQR-tree. Given a GQR-tree node \(N\) (initially set to the root) and a moving object \(o=(o.loc,o.A)\) with its capability \(o.Cap\), the search algorithm generates an object bit-vector \(o.bv\) and identifies the query group \(g\) such that \(g.bv\wedge o.bv=o.bv\). Then, the search algorithm recursively accesses the GQR-tree nodes that contain \(o.loc\) until reaching the node \(N\) such that \(|g\_N|\leq o.Cap\). Now, \(N\) becomes \(o\)'s resident domain. Figure 6: An example of the sub-GQR-tree. Next, the search algorithm invokes FindQueryID (See Algorithm 2), which is a _depth-first search_ algorithm that takes \(N\), \(o.bv\), and \(is\_Resident\_Domain\) (one-bit flag) as an input and retrieves all the query identifiers of the queries that are elements of \(g\_N\) (\(\subseteq g\)). Specifically, assuming \(N\) is a non-leaf node, FindQueryID identifies the query group \(g\) such that \(g.bv\)\(\wedge\)\(o.bv=o.bv\). Then, FindQueryID checks if \(Conceptual\_Leaf\) stored in \(N\) for \(g\) is set to \(True\) (_i.e._, \(0\leq|g\_N|\leq\theta\)). If so, it visits \(N.partial\_qd\_table\) and retrieves all the query identifiers contained in \(partial\_qd\_list\) of the tuple \(\langle g.bv,partial\_qd\_list\rangle\) (Lines 2-8). On the other hand, if \(Conceptual\_Leaf\) stored in \(N\) for \(g\) is set to \(False\), FindQueryID recursively accesses each \(N\)'s descendent (non-leaf or leaf) node \(\hat{N}\) (Lines 9-12 or 26-28) and according to two cases, it proceeds as follows:  
* **Case (1):** If \(\hat{N}\) is a non-leaf node and \(Conceptual\_Leaf\) stored in \(\hat{N}\) for \(g\) is set to \(True\), FindQueryID visits \(\hat{N}.partial\_qd\_table\) and \(\hat{N}.full\_qd\_table\), after which it retrieves all the distinct query identifiers contained in \(partial\_qd\_list\) of the tuple \(\langle g.bv,partial\_qd\_list\rangle\) and \(full\_qd\_list\) of the tuple \(\langle g.bv,full\_qd\_list\rangle\) (Lines 19-25). * **Case (2):** If \(\hat{N}\) is a leaf node, FindQueryID retrieves all the distinct query identifiers contained in \(partial\_qd\_list\) of the tuple \(\langle g.bv,partial\_qd\_list\rangle\) (stored in \(\hat{N}\)), after which it visits \(\hat{N}.full\_qd\_table\) and retrieves all the distinct query identifiers contained in \(full\_qd\_list\) of the tuple \(\langle g.bv,full\_qd\_list\rangle\) (Lines 29-34). It should be noted that \(\hat{N}.full\_qd\_table\) must be visited and each query identifier contained in \(full\_qd\_list\) must be retrieved and checked if the corresponding query \(q\in g\_N\). This is because, although the spatial query range of \(q\) covers or equals \(\hat{N}\), they may be covered by or partially intersect \(N\). In the worst case, \(N\) (\(o\)'s resident domain) may be a leaf node. In this case, FindQueryID retrieves only the query identifiers contained in \(partial\_qd\_list\) of the tuple \(\langle g.bv,partial\_qd\_list\rangle\) stored in \(N\) (Lines 13-16).