## 5 The Group-Aware Query Region Tree (GQR-Tree)
### Description
\right.\]Then, the query bit-vectors \(q_{1}.bv\), \(q_{2}.bv\), \(q_{3}.bv\), \(q_{4}.bv\), and \(q_{5}.bv\) generated for \(q_{1}.V\), \(q_{2}.V\), \(q_{3}.V\), \(q_{4}.V\), and \(q_{5}.V\) are \(01000110\) (\(0100+01+10\)), \(00100101\) (\(0010+01+01\)), \(0100**10\) (\(0100+**10\)), \(*****1001\) (\(*****+10+01\)), and \(01001001\) (\(0100+10+01\)), respectively. Given a set of queries \(\mathcal{Q}=\{q_{1},q_{2},\,\cdots,q_{|\mathcal{Q}|}\}\), we partition \(\mathcal{Q}\) into a set of _query groups_\(\mathcal{G}=\{g_{1},g_{2},\,\cdots,g_{|\mathcal{G}|(\leq|\mathcal{Q}|)}\}\) such that each query group \(g\) consists of the queries that have the same query bit-vector. Then, each query group \(g\) can be identified by a unique query bit-vector, which we call _group bit-vector_. Let \(|C_{i}|\) and \(|IV_{j}|\) be the number of categories per each categorical attribute \(a_{i\,(1\leq i\leq k)}\) and the number of intervals per each numerical attribute \(a_{j\,(1\leq j\leq n-k)}\), respectively, where \(k\) (\(\leq n\)) is the number of categorical attributes. Then, the maximum possible number of generated query groups (or the maximum possible number of generated group bit-vectors) is  
\[\prod_{i=1}^{k}|C_{i}|\cdot\prod_{j=1}^{n-k}|IV_{j}| \tag{2}\]  
Figure 4 shows an example of partitioning the queries \(q_{1}\sim q_{5}\) in Figure 3 into three query groups based on their query bit-vectors \(q_{1}.bv\sim q_{5}.bv\). Notice that if a query bit-vector \(q.bv\) contains bit positions filled with \"\(*\)\", the corresponding query \(q\) can become an element of multiple query groups because \"\(*\)\" is a wildcard, which matches any bit in those positions. For example, the query \(q_{3}\) in Figure 4 can be an element of two query groups; the query group \(g_{1}\) whose group bit-vector \(g_{1}.bv\) is \(01000110\) and another query group (though not as yet generated) whose group bit-vector is \(01001010\). The GQR-tree is a space partitioning query indexing structure, which is built by recursively splitting two-dimensional entire workspace into two subspaces. Given a set of query groups \(\mathcal{G}=\{g_{1},g_{2},\,\cdots,g_{|\mathcal{G}|}\}\) on the entire workspace that corresponds to the root, if there exists a query group \(g\) (\(\in\mathcal{G}\)) whose cardinality (_i.e._, the number of queries that are the elements of \(g\)) is greater than the split threshold \(\theta\), the entire workspace is split into two subspaces, each of which corresponds to a child node \(N\) of the root. Without ambiguity, we use the symbol \"\(N\)\" to denote both a tree node and its corresponding subspace. This process recursively continues until, for each \(g\) (\(\in\mathcal{G}\)), the number of its elements (queries) whose spatial query ranges are _covered by_ or _partially intersect_ every subspace \(N\) is no more than \(\theta\). Hereafter, we denote a set of \(g\)'s elements whose spatial query ranges are covered by or partially intersect \(N\) as \(g\_N\) (\(\subseteq g\)). We classify the _overlap relationship_ between a spatial query range \(q.R\) and a subspace (_i.e._, GQR-tree node) \(N\) into four categories according to whether the intersection and difference of \(q.R\) and \(N\) are empty or non-empty. Figure 4: An example of query grouping. **Definition 3**.