## 5 The Group-Aware Query Region Tree (GQR-Tree)
### Description
: _Given a spatial query range \(q.R\) and a subspace (a GQR-tree node) \(N\), there can be four overlap relationships as follows._  
* _Cover relationship_ _(See Figure_ 5_a): We say that_ \(q.R\) _covers_ \(N\) _if (_\(q.R\cap N=\
eg\emptyset\)_)_ \(\&\&\) _(_\(q.R-N=\
eg\emptyset\)_)_ \(\&\&\) _(_\(N-q.R=\emptyset\)_), where_ \(-\) _denotes difference._
* _Covered by relationship_ _(See Figure_ 5_b): We say that_ \(q.R\) _is_ _covered by_ \(N\) _if (_\(q.R\cap N=\
eg\emptyset\)_)_ \(\&\&\) _(_\(q.R-N=\emptyset\)_)_ \(\&\&\) _(_\(N-q.R=\
eg\emptyset\)_)._
* _Partially intersect relationship_ _(See Figure_ 5_c): We say that_ \(q.R\) _partially intersects_ \(N\) _if (_\(q.R\cap N=\
eg\emptyset\)_)_ \(\&\&\) _(_\(q.R-N=\
eg\emptyset\)_)_ \(\&\&\) _(_\(N-q.R=\
eg\emptyset\)_)._
* _Equal relationship_ _(See Figure_ 5_d): We say that_ \(q.R\) _equals_ \(N\) _if (_\(q.R\cap N=\
eg\emptyset\)_)_ \(\&\&\) _(_\(q.R-N=\emptyset\)_)_ \(\&\&\) _(_\(N-q.R=\emptyset\)_)._  
It should be noted that, in this paper, if a spatial query range \(q.R\)_meets_ (or _touches_) a subspace \(N\), we consider that \(q.R\) and \(N\) are disjoint although (\(q.R\cap N=\
eg\emptyset\)) \(\&\&\) (\(q.R-N=\
eg\emptyset\)) \(\&\&\) (\(N-q.R=\
eg\emptyset\)). Now, we describe the structure and properties of the GQR-tree. A leaf node of the GQR-tree stores, for each query group \(g\in\mathcal{G}\), a tuple of the form \(\langle g.bv,partial\_g\_list\rangle\), where \(g.bv\) is a group bit-vector of \(g\) and \(partial\_g\_list\) is a list that contains at most \(\theta\) query identifiers. A non-leaf node of the GQR-tree stores two entries of the form \(\langle ptr,N\rangle\), where \(ptr\) is a pointer to a child node (_i.e._, non-leaf or leaf node) and \(N\) is a subspace that corresponds to the child node pointed to by \(ptr\). **Definition 4**. : _Given a query group \(g\in\mathcal{G}\) and a leaf node \(N\) of the GQR-tree, the list \(partial\_g\_list\), with its size \(|partial\_g\_list|\leq\theta\), contains only the query identifier of each element (query) \(q\in g\) whose spatial query range \(q.R\) is covered by or partially intersects \(N\) (i.e., query identifier of each query \(q\in g\_N\))._  
The GQR-tree satisfies the following properties:  
1. A tuple \(\langle g.bv,partial\_g\_list\rangle\) for each query group \(g\in\mathcal{G}\) can be stored in a leaf node \(N\) only if there exists at least one element (query) \(q\in g\) whose spatial query range \(q.R\) is covered by or partially intersects \(N\) (_i.e._, \(g\_N\
eq\emptyset\)). 2. A tuple \(\langle g.bv,partial\_g\_list\rangle\) for each query group \(g\in\mathcal{G}\) can be redundantly stored in several leaf nodes if there exists an element \(q\in g\) whose spatial query range \(q.R\) partially intersects all of these leaf nodes. Figure 5: Classification of the overlap relationship. (**a**) \(q_{1}.R\) and \(q_{2}.R\) cover \(N\); (**b**) \(q_{1}.R\) and \(q_{2}.R\) are covered by \(N\); (**c**) \(q_{1}.R\) and \(q_{2}.R\) partially intersect \(N\); (**d**) \(q_{1}.R\) and \(q_{2}.R\) equal \(N\). 3. For each entry \(\langle ptr,\hat{N}\rangle\) stored in a non-leaf node \(N\), \(\hat{N}\) represents one of the equal halves of \(N\)'s space. 4. Each (non-leaf or leaf) node \(N\) stores, for each query group \(g\in\mathcal{G}\), the cardinality \(|g\_N|\) of \(g\_N\) (_i.e._, the total number of \(g\)'s elements whose spatial query ranges are covered by or partially intersect \(N\)). In case that \(N\) is a non-leaf node, \(N\) additionally stores, for each query group \(g\in\mathcal{G}\), a single bit flag \(Conceptual\_Leaf\), which is set to \(True\) if \(0\leq|g\_N|\leq\theta\) and set to \(False\) otherwise. 5. Each (non-leaf or leaf) node \(N\) is associated with a data structure \(N.full\_qid\_table\), which is a set of tuples of the form \(\langle g.bv,full\_qid\_list\rangle\), where \(g.bv\) is a group bit-vector of a query group \(g\in\mathcal{G}\) and \(full\_qid\_list\) (See Definition 5 below) is a list that contains arbitrary number of query identifiers. 6.