## 5 The Group-Aware Query Region Tree (GQR-Tree)
### GQR-Tree Manipulations  
The GQR-tree can be manipulated with a set of algorithms, which specify how a query is inserted into and deleted from the GQR-tree, and how overflow and underflow of a GQR-tree node can be managed. Algorithm 3 is the pseudocode of the insert algorithm. When a new query \(q=(q.R,q.V)\) is issued by a client and is inserted into the query table, the insert algorithm generates a query bit-vector \(q.bv\), identifies the query group \(g\) whose group bit-vector \(g.bv\) is same as \(q.bv\) (Lines 1-2). Then, starting from the root, the insert algorithm recursively follows the paths of the GQR-tree, each of which consists of non-leaf and leaf nodes with which the spatial query range \(q.R\) of \(q\) overlaps. At a non-leaf node \(N\) in each path, the insert algorithm checks if \(q.R\) covers or equals \(N\) (Line 4). If so, it inserts the query identifier of \(q\) into \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\) (Line 5). Otherwise (_i.e._, \(q.R\) is covered by or partially intersects \(N\)), the insert algorithm increases \(|g\_N|\) by \(1\) and checks if \(Conceptual\_Leaf\) stored in \(N\) for \(g\) is set to \(True\) (Lines 6-8). If so, it inserts the query identifier of \(q\) into \(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 (Line 9). In case that \(|g\_N|\) becomes greater than \(\theta\) due to the insertion of \(q\), SplitNonLeaf, a split algorithm for a non-leaf node, is invoked (Line 10). When reaching a leaf node \(N\) in the path, the insert algorithm checks if \(q.R\) covers or equals \(N\) (Line 16). If so, it inserts the query identifier of \(q\) into \(full\_qid\_list\) of the tuple \(\langle g.bv,full\_qid\_list\rangle\) maintained in \(N.full\_qid\_table\) (Line 17). Otherwise, the insert algorithm increases \(|g\_N|\) by \(1\) and  
Figure 7: An example of the Group-Aware Query Region (GQR)-tree. inserts the query identifier of \(q\) into \(partial\_q\_list\) of the tuple \(\langle g.bv,partial\_q\_list\rangle\) stored in \(N\) (Lines 18-20). When \(N\) overflows (_i.e._, \(|g\_N|>\theta\)), SplitLeaf, a split algorithm for a leaf node, is invoked (Line 21). ```
1:\(N\): a GQR-tree node initially set to the root, \(q\): a newly issued query
2:map \(q\_V\) to \(q\_bv\);
3:identify the query group \(g\) whose group bit-vector \(g.bv\) is same as \(q.bv\);
4:if\(N\) is a non-leaf node then
5:if\(q.R\) covers or equals \(N\)then
6:insert the query identifier of \(q\) into \(full\_q\_list\) of the tuple \(\langle g.bv,full\_q\_list\rangle\) maintained in \(N.full\_q\_table\);
7:else\(q\_q.R\) is covered by or partially intersects \(N\)
8:increase \(|g\_N|\) by 1;
9:if\(Conceptual\_Lead\) stored in \(N\) for \(g\) is \(True\)then
10:insert the query identifier of \(q\) into \(partial\_q\_list\) of the tuple \(\langle g.bv,partial\_q\_list\rangle\) maintained in \(N.partial\_q\_table\);
11:SplitNonLeaf(\(N\),\(g.bv\)) in case that \(|g\_N|>\theta\);
12:else\(\
ot\)/\(Conceptual\_Lead\) for \(g\) is \(False\)
13:for each entry (\(ptr\), \(\hat{N}\)) stored in \(N\)do
14:if\(q.R\) overlaps with \(\hat{N}\)then
15:insert(\(N\), \(q\));
16:else/\(N\) is a leaf node
17:if\(q.R\) covers or equals \(N\)then
18: insert the query identifier of \(q\) into \(full\_q\_list\) of the tuple \(\langle g.bv,full\_q\_list\rangle\) maintained in \(N.full\_q\_table\);
19:else/\(q.R\) is covered by or partially intersects \(N\)
20:increase \(|g\_N|\) by 1;
21:insert the query identifier of \(q\) into \(partial\_q\_list\) of the tuple \(\langle g.bv,partial\_q\_list\rangle\) stored in \(N\);
22:SplitLeaf(\(N\),\(g.bv\)) in case that \(|g\_N|>\theta\);
```  
**Algorithm 3**Insert(\(N\), \(q\))  
Algorithm 4 is the pseudocode of SplitNonLeaf. Given a non-leaf node \(N\) and a group bit-vector \(g.bv\), SplitNonLeaf identifies the query group \(g\), which causes \(N\) to be overflowed, using \(g.bv\) (Line 1).