## 5 The Group-Aware Query Region Tree (GQR-Tree)
### GQR-Tree Manipulations
Now, \(N\)'s parent becomes \(N_{new}\)'s parent. ```
1:input\(N\): an overflowed leaf node, \(g\_bv\): a group bit-vector
2: identify the query group \(g\), which causes \(N\) to be overflowed, using \(g\_bv\);
3: create two new empty leaf nodes \(N_{left}\) and \(N_{right}\):
4: create a new empty non-leaf node \(N_{new}\);
5: insert entries \((ptr,N_{left})\) and \((ptr,N_{right})\) into \(N_{new}\);
6: copy the tuple \((g\_bv,full\_gid\_list)\) maintained in \(N.full\_gid\_table\) and paste it into \(N_{left}.full\_gid\_table\), \(N_{right}.full\_gid\_table\), and \(N_{new}.full\_gid\_table\);
7: for each group \(\hat{g}\in\mathcal{G}-\{g\}\) such that \(|\hat{g}\_N|>0\)do
8: copy the tuple \((\hat{g}.bv,partial\_{\_}{dist})\) stored in \(N\) and paste it into \(N_{new}.partial\_{\_}{d}\_{table}\);
9: set \(|\hat{g}\_N_{new}|\) and \(Conceptual\_Leaf\) created in \(N_{new}\) for \(g\) to \(|\hat{g}\_N|\) and \(True\);
10: set \(|g\_N_{new}|\) and \(Conceptual\_Leaf\) created in \(N_{new}\) for \(g\) to \(|\hat{g}\_N|\) and \(False\);
11: find the entry \((ptr,N)\) stored in \(N\)'s parent and redirect \(ptr\) to point to \(N_{new}\);
12: get the tuple \((g.bv,partial\_{\_}{dist})\) from \(N\);
13: for each query \(\hat{g}\) to be exactly identifier contained in \(partial\_{\_}{d}\_{dist}\)do
14: for each \(N_{new}\)'s child node \(\hat{N}_{new}\)do
15: if\(g\_N\) covers or equals \(\hat{N}_{new}\)then
16: insert the query identifier of \(q\) into \(full\_gid\_list\) of the tuple \(\langle g.bv,full\_gid\_list\rangle\) maintained in \(\hat{N}_{new}.full\_gid\_table\);
17: else if\(g.R\) is covered by or partially intersects \(\hat{N}_{new}\)then
18: increase \(|g\_N_{new}|\) by \(1\);
19: insert a new tuple \((g.bv,partial\_{\_}{dist})_{new}\) for \(g\) into \(\hat{N}_{new}\) (if it does not exist);
20: discard \(N\);
21:for each \(N_{new}\)'s child node \(\hat{N}_{new}\)do
22:if\(|g\_N_{new}|>\theta\)then
23: SplitLeaf(\(N_{new},g.bv\));
```  
**Algorithm 5**SplitLeaf(\(N,g.bv\))  
Next, given the tuple \(\langle g.bv,partial\_{\_}{d}\_{list}\rangle\) stored in \(N\), SplitLeaf checks for each query \(q\) referred to by each query identifier contained in \(partial\_{\_}{d}\_{list}\) if \(q.R\) covers or equals \(N_{left}\) (or \(N_{right}\)). If so, it inserts the query identifier of \(q\) into \(full\_gid\_list\) of the tuple \(\langle g.bv,full\_gid\_list\rangle\) maintained in \(N_{left}.full\_gid\_table\) (or \(N_{right}\)-\(full\_gid\_table\)) (Lines 11-15). On the other hand, if \(q.R\) is covered by or partially intersects \(N_{left}\) (or \(N_{right}\)), SplitLeaf increases \(|g\_N_{left}|\) (or \(|g\_N_{right}|\)) by \(1\) and inserts a new tuple \(\langle g.bv,partial\_{\_}{d}\_{list}\rangle_{new}\) for \(g\) into \(N_{left}\) (or \(N_{right}\)) (if it does not exist), and inserts the query identifier of \(q\) into \(partial\_{\_}{d}\_{list}\) (Lines 16-19). Finally, SplitLeaf discards \(N\) (Line 20). This split process propagates downward if necessary (Lines 21-23). When an existing query \(q=(q.R,q.V)\) is terminated by a client and is deleted from the query table, the delete algorithm is invoked. Algorithm 6 is the pseudocode of the delete algorithm. Similarly to the insert algorithm, after identifying the query group \(g\) whose group bit-vector \(g.bv\) is same as the query bit-vector \(q.bv\) of \(q\) (Lines 1-2), the delete algorithm recursively follows the paths of the GQR-tree, each of which consists of the non-leaf and leaf nodes that overlap with the spatial query range \(q.R\) of \(q\). At a non-leaf node \(N\) in each path, the delete algorithm checks if \(q.R\) covers or equals \(N\). If so, it deletes the query identifier of \(q\) from \(full\_gid\_list\) of the tuple \(\langle g.bv,full\_gid\_list\rangle\) maintained in \(N.full\_gid\_table\) (Lines 4-5). Otherwise (_i.e._, \(q.R\) is covered by or partially intersects \(N\)), the delete algorithm decreases \(|g\_N|\) by \(1\) and checks if \(Conceptual\_Leaf\) stored in \(N\) for \(g\) hasalready set to \(True\).