## 5 The Group-Aware Query Region Tree (GQR-Tree)
### GQR-Tree Manipulations
```
1:Input\(N\): an overflowed non-leaf node, \(g.bv\): a group bit-vector
2: identify the query group \(g\), which causes \(N\) to be overflowed, using \(g.bv\);
3: set \(Conceptual\_leaf\) stored in \(N\) for \(g\) to \(False\);
4:if\(N\)'s children are non-leaf nodes then
5: copy the tuple \((g.bv,full\_qid\_list)\) maintained in \(N.full\_qid\_table\) and paste it into \(full\_qid\_table\) of \(N\)'s children;
6: visit \(N.partial\_qid\_table\) and get the tuple \(\langle g.bv,partial\_qid\_list\rangle\);
7:for each query \(q\) referred to by each query identifier contained in \(partial\_qid\_list\)do
8:for each \(N\)'s child node \(\dot{N}\)do
9: if\(q.R\) covers or equals \(\dot{N}\)then
10: insert the query identifier of \(q\) into \(full\_qid\_list\) of the tuple \((g.bv,full\_qid\_list)\) maintained in \(\dot{N}.full\_qid\_table\);
11:else if\(q.R\) is covered by or partially intersects \(\dot{N}\)then
12: increase \(|g\_\dot{N}|\) by 1;
13: create a new tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) for \(g\) in \(\dot{N}.partial\_qid\_table\) (if it does not exist);
14: insert the query identifier of \(q\) into \(partial\_qid\_list\);
15: delete the tuple \((g.bv,partial\_qid\_list)\) from \(N.partial\_qid\_table\);
16:for each \(N\)'s child node \(\dot{N}\)do
17:if\(|g\_\dot{N}|\leq\theta\)then
18: set \(Conceptual\_leaf\) stored in \(\dot{N}\) for \(g\) to \(True\);
19:else
20: SplitNonLeaf(\(N,g.bv\));
21:else // \(N\)'s children are leaf nodes
22: copy the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\) and paste it into \(full\_qid\_table\) of \(N\)'s children;
23: visit \(N.partial\_qid\_table\) and get the tuple \(\langle g.bv,partial\_qid\_list\rangle\);
24:for each query \(q\) referred to by each query identifier contained in \(partial\_qid\_list\)do
25:for each \(N\)'s child node \(\dot{N}\)do
26:if\(q.R\) covers or equals \(\dot{N}\)then
27: insert the query identifier of \(q\) into \(full\_qid\_list\) of the tuple \((g.bv,full\_qid\_list)\) maintained in \(\dot{N}.full\_qid\_table\);
28:else if\(q.R\) is covered by or partially intersects \(\dot{N}\)then
29: increase \(|g\_\dot{N}|\) by 1;
30: insert a new tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) for \(g\) into \(\dot{N}\) (if it does not exist);
31: insert the query identifier of \(q\) into \(partial\_qid\_list\);
32: delete the tuple \((g.bv,partial\_qid\_list)\) from \(N.partial\_qid\_table\);
33:for each \(N\)'s child node \(\dot{N}\)do
34:if\(|g\_\dot{N}|>\theta\)then
35: SplitLeaf(\(\dot{N},g.bv\));
```  
**Algorithm 4**SplitNonLeaf(\(N,g.bv\))  
Algorithm 5 is the pseudocode of SplitLeaf. Given a leaf node \(N\) and a group bit-vector \(g.bv\), SplitLeaf identifies the query group \(g\), which causes \(N\) to be overflowed (using \(g.bv\)), after which it creates two new empty leaf nodes \(N_{left}\) and \(N_{right}\), and a new non-leaf node \(N_{new}\) that stores entries \((ptr,N_{left})\) and \((ptr,N_{right})\), where \(N_{left}\) or \(N_{right}\) represents one of the equal halves of \(N\) (Lines 1-4). Now, \(N_{left}\) and \(N_{right}\) become \(N_{new}\)'s children. Then, SplitLeaf copies the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\) and pastes it into \(N_{left}.full\_qid\_table\), \(N_{right}.full\_qid\_table\), and \(N_{new}.full\_qid\_table\) (Line 5). In addition, for each query group \(\dot{g}\in\mathcal{G}-\{g\}\)such that \(|\hat{g}\_N|>0\), SplitLeaf (i) copies the tuple \(\langle\hat{g}.bv,partial\_{\_}{dist}\rangle\) stored in \(N\) and pastes it into \(N_{new}.partial\_{\_}{d}\_{table}\), and (ii) sets \(|\hat{g}\_N_{new}|\) and \(Conceptual\_Leaf\) created in \(N_{new}\) for \(\hat{g}\) to \(|\hat{g}\_N|\) and \(True\), respectively (Lines 6-8). Then, SplitLeaf sets \(|g\_N_{new}|\) and \(Conceptual\_Leaf\) created in \(N_{new}\) for \(g\) to \(lg\_N|\) and \(False\), respectively, after which it finds the entry \((ptr,N)\) stored in \(N\)'s parent to redirect \(ptr\) to point to \(N_{new}\) (Lines 9-10).