## 5 The Group-Aware Query Region Tree (GQR-Tree)  
### Description  
Similarly to the BQR-tree, we choose to extend the QR-tree to the GQR-tree because, to the best of our knowledge, the QR-tree is superior to existing index structures (e.g., the BP-tree) for evaluation of traditional spatial range monitoring queries. In addition, because the cost of implementing entirely new index structure can be more expensive than the cost of extending an already existing index structure; thus, for efficient evaluation of CM range monitoring queries, extending the QR-tree by adding new features can be an excellent alternative. For the tight integration of the spatial and the non-spatial specifications of the queries, we group the queries based on their _query bit-vectors_, after which we construct the GQR-tree based on their spatial query ranges. We represent non-spatial values (or intervals) specified by the queries as query bit-vectors. The query bit-vector is generated based on a mapping function predefined for each non-spatial attribute \(a_{i\,(1\leq i\leq n)}\in A\). If \(a_{i}\) is a categorical attribute with \(|C_{i}|\) categories \(c_{1},\,c_{2},\,\cdots,\,c_{|C_{i}|}\), given a non-spatial value \(q.v_{i\,(1\leq i\leq n)}\in q.V\) specified by a query \(q\) on \(a_{i}\), its mapping function \(f_{i\,(1\leq i\leq n)}\) maps \(q.v_{i}\) into a bit-string \((b_{1}b_{2}\cdots b_{|C_{i}|})\) such that \(b_{j\,(1\leq j\leq|C_{i}|)}=\) '\(1\)' if \(q.v_{i}=c_{j\,(1\leq j\leq|C_{i}|)}\), otherwise, \(b_{j}=\) '\(0\)'. On the other hand, if \(a_{i}\) is a numerical attribute, \(f_{i}\) divides \(a_{i}\)'s domain into \(|IV_{i}|\) disjoint intervals \(iv_{1},iv_{2},\cdots,iv_{|IV_{i}|}\) of equal length. Then, given a non-spatial interval \(q.v_{i}\), \(f_{i}\) maps \(q.v_{i}\) into a bit-string \((b_{1}b_{2}\cdots b_{|IV_{i}|})\) such that \(b_{j\,(1\leq j\leq|IV_{i}|)}=\) \"\(1\)\" if \(q.v_{i}\) overlaps with \(iv_{j\,(1\leq j\leq|IV_{i}|)}\), otherwise, \(b_{j}=\) \"\(0\)\". If \(q.v_{i}\) overlaps with more than one interval, say \(|IV_{i}|\) (\(\leq|IV_{i}|\)) intervals, then we consider \(q\) as \(|IV_{i}|\) distinct queries. **Definition 2**. : _Given a query \(q=\) (\(q.R\), \(q.V\)), suppose that there is a predefined mapping function \(f_{i\,(1\leq i\leq n)}\) for each non-spatial attribute \(a_{i\,(1\leq i\leq n)}\in A\). Then, a **query bit-vector**\(q.bv\) generated for \(q.V\) is \(f_{1}\)(\(q.v_{1}\)) + \(f_{2}\)(\(q.v_{2}\)) + \(\cdots\) + \(f_{n}\)(\(q.v_{n}\)), where \(+\) denotes the bit-string concatenation operator. When \(q.V\) does not contain the specified value (or interval) \(q.v_{i\,(1\leq i\leq n)}\) on \(a_{i}\), the bit-string for \(f_{i}\)(\(q.v_{i}\)) becomes \(**\cdots\)\(**\) with its length being equal to \(f_{i}\)(\(a_{i}\)), where the symbol \"\(*\)\" denotes a \"don't care\" condition. Although a bit can represent only two states \"\(0\)\" and \"\(1\)\", we assume that one bit represents \"\(0\)\", \"\(1\)\", and \"\(*\)\" for convenience._  
In the following, using the non-spatial values (or intervals) \(q_{1}.V\sim q_{5}.V\) specified on a subset of \(A=\{a_{1}\): _Age_, \(a_{2}\): _Dietary preference_, \(a_{3}\): _Gender_} in Figure 3 as an example, we show how query bit-vectors for \(q_{1}.V\sim q_{5}.V\) are generated. Suppose that there are three predefined mapping functions:  
\[f_{1}(x_{s},x_{e})=\left\{ \begin{array}{ll}1000\;\;\mbox{if}\;[x_{s},x_{e}) \cap[0,20)=-\emptyset;\\ 0100\;\;\mbox{if}\;[x_{s},x_{e})\cap[20,40)=-\emptyset;\\ 0010\;\;\mbox{if}\;[x_{s},x_{e})\cap[40,60)=-\emptyset;\\ 0001\;\;\mbox{otherwise, where}\;\;\cap\;\mbox{denotes intersection}. \end{array} \right.\]  
\[f_{2}(x)=\left\{ \begin{array}{ll}10\;\;\mbox{if}\;x=\mbox{\emph{Meat }\;\mbox{eater}};\\ 01\;\;\mbox{if}\;x=\mbox{\emph{Vegetarian}}.\end{array}