## 5 The Group-Aware Query Region Tree (GQR-Tree)
### GQR-Tree Manipulations
Finally, MergeNonLeaf deletes the information about \(g\) stored in all \(N\)'s descendant nodes and their associated \(partial\_qid\_tables\) (if exist) and \(full\_qid\_tables\) (Line 13). This merge process propagates upward until reaching the node that does not satisfy the merge condition (Line 14). ```
0:\(N\): a non-leaf node, which is a parent of non-leaf nodes, \(g\).\(bv\): a group bit-vector
1: identify the query group \(g\) using \(g\).\(bv\);
2:if\(|g\_N|\leq\theta\)then
3: set \(Conceptual\_Leaf\) stored in \(N\) for \(g\) to \(True\);
4: create a new tuple \(\langle g.bv,partial\_dist\_list\rangle_{new}\) for \(g\) in \(N.partial\_id\_table\);
5:for each \(N\)'s child node \(\dot{N}\)do
6:if\(Conceptual\_Leaf\) stored in \(\dot{N}\) for \(g\) is \(True\)then
7: visit \(\dot{N}.partial\_id\_table\) and get the tuple \(\langle g.bv,partial\_dist\_list\rangle\);
8: insert all the query identifiers contained in \(partial\_id\_list\) into \(partial\_id\_list\) of the tuple \(\langle g.bv,partial\_dist\_list\rangle_{new}\);
9: visit \(\dot{N}.full\_id\_table\) and get the tuple \(\langle g.bv,full\_id\_list\rangle\);
10:for each query \(q\) referred to by each query identifier contained in \(full\_id\_list\)do
11:if\(q\).\(R\) is covered by or partially intersects \(N\)then
12: insert the query identifier of \(q\) into \(partial\_q\_id\_list\) of the tuple \(\langle g.bv,partial\_dist\_list\rangle_{new}\);
13: delete the information about \(g\) stored in all \(N\)'s descendant nodes and their associated \(partial\_q\_q\_tables\) (if exist) and \(full\_q\_q\_tables\);
14:MergeConLeaf(\(N\)'s parent, \(g\).\(bv\));
```  
**Algorithm 7**MergeConLeaf(\(N,g.bv\))  
Algorithm 8 is the pseudocode of MergeLeaf. Given a non-leaf node \(N\), which is a parent of leaf nodes, and a group bit-vector \(g\).\(bv\), MergeLeaf identifies the query group \(g\) using \(g\).\(bv\) (Line 1). Then, MergeLeaf checks if \(|g\_N|\leq\theta\); if this is the case, it further checks if every \(Conceptual\_Leaf\) stored in \(N\) for every query group \(\dot{g}\in\mathcal{G}-\{g\}\) is set to \(True\) (Lines 2-3). If so, MergeLeaf creates a new empty leaf node \(N_{new}\) (Line 4). Then, MergeLeaf (i) copies all the tuples maintained in \(N.full\_qid\_table\) and \(N.partial\_qid\_table\), and pastes them into \(N_{new}.full\_qid\_table\) and \(N_{new}\), respectively, and (ii) sets \(|\dot{g}\_N_{new}|\) to \(|\dot{g}\_N|\) (Lines 5-6). In addition, MergeLeaf (i) inserts a new tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) for \(g\) into \(N_{new}\) and (ii) sets \(|g\_N_{new}|\) to \(|g_{-}N|\), after which it finds the entry \((ptr,N)\) stored in \(N\)'s parent to redirect \(ptr\) to point to \(N_{new}\) (Lines 7-9). Now, \(N\)'s parent becomes \(N_{new}\)'s parent. Next, given the tuple \(\langle g.bv,partial\_qid\_list\rangle\) stored in each \(N\)'s child node \(\dot{N}\), MergeLeaf inserts all the distinct query identifiers contained in \(partial\_qid\_list\) into \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) (Lines 10-12). Then, given the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in each \(\dot{N}.full\_qid\_table\), for each query \(q\) referred to by each query identifier contained in \(full\_qid\_list\), MergeLeaf checks if \(q\).\(R\) is covered by or partially intersects \(N_{new}\). If so, it inserts the query identifier of \(q\) into \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) (stored in \(N_{new}\)) (Lines 13-16). Finally, after discarding \(N\) and \(N\)'s children, MergeLeaf invokes itself with \(N_{new}\)'s parent and \(g.bv\) as an input to condense the tree if possible (Lines 17-18).