## 5 The Group-Aware Query Region Tree (GQR-Tree)
### GQR-Tree Manipulations
If so, it deletes the query identifier of \(q\) from \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle\) maintained in \(N.partial\_qid\_table\) and stops following the corresponding path of the GQR-tree (Lines 6-9). Then, the delete algorithm invokes a merge algorithm for a non-leaf node, namely, MergeNonLeaf (Line 10). **Input**\(N\): a GQR-tree node initially set to the root, \(q\): a terminated query  
```
1:map \(q\).\(V\) to \(q\).\(bv\);
2:identify the query group \(g\) whose group bit-vector \(g\).\(bv\) is same as \(q\).\(bv\);
3:if\(N\) is a non-leaf node then
4:if\(q\).\(R\) covers or equals \(N\)then
5: delete the query identifier of \(q\) from \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\);
6:else // \(q\).\(R\) is covered by or partially intersects \(N\)
7: decrease \(|g\_N|\) by 1;
8:if\(Conceptual\_Leaf\) stored in \(N\) for \(g\) is \(True\)then
9: delete the query identifier of \(q\) from \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle\) maintained in \(N.partial\_qid\_table\);
10: MergeNonLeaf(\(N\)'s parent, \(g\).\(bv\));
11:else // \(Conceptual\_Leaf\) for \(g\) is \(False\)
12:for each entry (\(ptr\), \(\hat{N}\)) stored in \(N\)do
13:if\(q\).\(R\) overlaps with \(\hat{N}\)then
14:Delete(\(\hat{N}\), \(q\));
15:else // \(N\) is a leaf node
16:if\(g\).\(R\) covers or equals \(N\)then
17: delete the query identifier of \(q\) from \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\);
18:else // \(q\).\(R\) is covered by or partially intersects \(N\)
19: decrease \(|g\_N|\) by 1;
20: delete the query identifier of \(q\) from \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle\) stored in \(N\);
21:MergeLeaf(\(N\)'s parent, \(g\).\(bv\));
```  
**Algorithm 6****Delete(\(N\), \(q\))**  
When reaching a leaf node \(N\) in the path, the delete algorithm checks if \(q\).\(R\) covers or equals \(N\). If so, it deletes the query identifier of \(q\) from \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\) (Lines 16-17). Otherwise, the delete algorithm decreases \(|g\_N|\) by \(1\) and deletes the query identifier of \(q\) from \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle\) stored in \(N\) (Lines 18-20). Then, the delete algorithm invokes a merge algorithm for a leaf node, namely, MergeLeaf to condense the GQR-tree if possible (Line 21). Algorithm 7 is the pseudocode of MergeNonLeaf. Given a non-leaf node \(N\), which is a parent of non-leaf nodes, and a group bit-vector \(g.bv\), MergeNonLeaf identifies the query group \(g\) using \(g\).\(bv\) (Line 1). Then, MergeNonLeaf checks if \(|g\_N|\leq\theta\). If so, it sets \(Conceptual\_Leaf\) stored in \(N\) for \(g\) to \(True\) and creates a new tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) for \(g\) in \(N.partial\_qid\_table\) (Lines 2-4). Next, for each \(N\)'s child node \(\hat{N}\), MergeNonLeaf checks if \(Conceptual\_Leaf\) stored in \(\hat{N}\) for \(g\) is set to \(True\). If so, given the tuple \(\langle g.bv,partial\_qid\_list\rangle\) maintained in \(\hat{N}.partial\_qid\_table\), MergeNonLeaf inserts all the query identifiers contained in \(partial\_qid\_list\) into \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) (Lines 5-8). Next, given the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in each \(\hat{N}.full\_qid\_table\), for each query \(q\) referred to by each query identifier contained in \(full\_qid\_list\), MergeNonLeaf checks if \(q\).\(R\) is covered by or partially intersects \(N\). If so, it inserts the query identifier of \(q\) into \(partial\_qid\_list\) of the tuple \(\langle g.bv,partial\_qid\_list\rangle_{new}\) (Lines 9-12).