## 5 The Group-Aware Query Region Tree (GQR-Tree)
### Resident Domain Search
```
1:Input\(N\): a GQR-tree node, \(o.bv\): an object bit-vector, \(is\_Resident\_Domain\): a bit flag initially set to \(True\)
2:Output\(qid\_set\): a set of (distinct) query identifiers
3: initialize an empty set \(qid\_set\);
4:if\(is\_Resident\_Domain\) = \(True\)then
5: identify the query group \(g\) such that \(g.bv\wedge o.bv=o.bv\);
6:if\(N\) is a non-leaf node then
7:if\(Conceptual\_Leaf\) stored in \(N\) for \(g\) is \(True\)then
8: visit \(N.partial\_qid\_table\) and get the tuple \(\langle g.bv,partial\_qid\_list\rangle\);
9: retrieve all the query identifiers contained in \(partial\_qid\_list\) and insert them into \(qid\_set\);
10: return \(qid\_set\);
11:else // \(Conceptual\_Leaf\) stored in \(N\) for \(g\) is \(False\)
12: set \(is\_Resident\_Domain\) to \(False\);
13:for each entry \((ptr,\hat{N})\) stored in \(N\)do
14: FindQueryID(\(\hat{N},o.bv,is\_Resident\_Domain\));
15:else // \(N\) is a leaf node
16: get the tuple \(\langle g.bv,partial\_qid\_list\rangle\) stored in \(N\);
17: retrieve all the query identifiers contained in \(partial\_qid\_list\) and insert them into \(qid\_set\);
18: return \(qid\_set\);
19:else // \(is\_Resident\_Domain\) = \(False\)
20: identify the query group \(g\) such that \(g.bv\wedge o.bv=o.bv\);
21:if\(N\) is a non-leaf node then
22:if\(Conceptual\_Leaf\) stored in \(N\) for \(g\) is \(True\)then
23: visit \(N.partial\_qid\_table\) and get the tuple \(\langle g.bv,partial\_qid\_list\rangle\);
24: retrieve all the query identifiers contained in \(partial\_qid\_list\) and insert them into \(qid\_set\);
25: visit \(N.full\_qid\_table\) and get the tuple \(\langle g.bv,full\_qid\_list\rangle\);
26: retrieve all the query identifiers contained in \(full\_qid\_list\) and insert them into \(qid\_set\);
27: return \(qid\_set\);
28:else // \(Conceptual\_Leaf\) stored in \(N\) for \(g\) is \(False\)
29:for each entry \((ptr,\hat{N})\) stored in \(N\)do
30: FindQueryID(\(\hat{N},o.bv,is\_Resident\_Domain\));
31:else // \(N\) is a leaf node
32: get the tuple \(\langle g.bv,partial\_qid\_list\rangle\) stored in \(N\);
33: retrieve all the query identifiers contained in \(partial\_qid\_list\) and insert them into \(qid\_set\);
34: return \(qid\_set\);
```  
**Algorithm 2**FindQueryID(\(N,o.bv,is\_Resident\_Domain\))  
After Algorithm 1 terminates, the server searches all the queries (in the query table) referred to by the retrieved query identifiers, updates query results if necessary, and assigns the moving object \(o\) its resident domain \(N\) together with query identifier and spatial query range pairs. Figure 7 shows an example of the GQR-tree for the queries \(q_{1}\sim q_{5}\) shown in Figure 3, assuming \(\emptyset=1\). Let us assume that the non-spatial attribute values \(o_{3}.A\) of the moving object \(o_{3}\) with \(o_{3}.Cap=1\) in Figure 7 is \(\{o_{3}.a_{1}=28,\)\(o_{3}.a_{2}=\)\(\mathit{Vegetarian},\)\(o_{3}.a_{3}=Male\}\). Then, the object bit-vector \(o_{3}.bv\) of \(o_{3}\) is \(01000110\) and is matched to \(g_{1}.bv\). When \(o_{3}\) is registered at the server, starting from the root, the search algorithm recursively traverses the GQR-tree until it reaches the node \(N_{2}\) because \(N_{2}\) contains the location of \(o_{3}\) and \(|g_{1}\_N_{2}|\) (\(=1\)) \(\leq o_{3}.Cap\). Then, the search algorithm invokes