## 6 Performance Evaluation
### Simulation Results  
#### 6.2.1 Effect of the Number of Queries  
In the first simulation, we varied the cardinalities of _Uniform_ and _Skewed_ from 1000 to 10,000 and studied the effect of the number of queries on the server workload and communication cost. The purpose of this simulation was to show the scalability of GQRT with regard to the number of queries. Figure 8 shows the effect of the number of queries (_i.e._, cardinalities of _Uniform_ and _Skewed_) on the CPU-time the server takes for query evaluation. In MQM, QRT, BQRT, and GQRT, the CPU-time performance is mainly affected by the search process for assigning resident domains to moving objects, whereas, in SR, the CPU-time performance is mainly affected by safe region computation. As shown in the figure, SR performs worst for _Uniform_ because as the number of queries becomes larger, the size of a safe region assigned to each moving object \(o\) becomes smaller. Therefore, \(o\) easily exits its current small safe region and contacts the server in order to receive a new safe region. This leads the server to frequently determine \(o\)'s new safe region with intensive computation. It is also observed from the figure that BQRT and GQRT perform much better than QRT and MQM for _Uniform_ and _Skewed_. This is due to the fact that the BQR-tree and GQR-tree store the bit-vector information in order to assign each moving object \(o\) a larger resident domain. As a result, the server can reduce the frequency of search process for assigning a new resident domain to \(o\) that exits its current resident domain. \begin{table}
\begin{tabular}{c c} \hline \hline
**Simulation Parameter** & **Value Used (Default)** \\ \hline Cardinality of _Uniform/Skewed_ & 1000 \(\sim\) 10,000 (**5000**) \\ Side length of spatial query ranges & 500 m \(\sim\) 5000 m (**2500 m**) \\ Number of moving objects & 10,000 \(\sim\) 100,000 (**50,000**) \\ Number of non-spatial attributes & 1 \(\sim\) 10 (**5**) \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Simulation parameters and their values. Figure 8: CPU-time _vs._ cardinalities of _Uniform_ and _Skewed_. (**a**) _Uniform_; (**b**) _Skewed_. However, GQRT performs much better than BQRT. This is because the BQR-tree is a naive form of the enhanced QR-tree, where tree construction is based mostly on the spatial information, and thus, similarly to MQM and QRT, in the BQRT, when assigning a resident domain to \(o\), the capability \(o.Cap\) of \(o\) is measured by the number of spatial query ranges without any consideration of the non-spatial information. On the other hand, in GQRT, when assigning the resident domain to \(o\), the GQR-tree, which groups the queries according to their non-spatial information when being built on their spatial query ranges, enables \(o.Cap\) to be measured by the number of only the queries that are the elements of the query group \(g\) whose group bit-vector \(g.bv\) is matched to the object bit-vector \(o.bv\) of \(o\). This helps the server assign a larger resident domain to \(o\). GQRT takes 76.2% of the server workload, as compared to BQRT for _Uniform_. Meanwhile, GQRT takes 67.7% of the server workload, as compared to BQRT for _Skewed_. Figure 9 shows the effect of the number of queries on the total number of messages communicated between the server and moving objects. As the number of queries increases, the performances of all the methods degrade. However, BQRT and GQRT outperform SR, MQM, and QRT for _Uniform_ and _Skewed_. This is because, in BQRT and GQRT, the server can assign moving objects large resident domains together with only qualified spatial query ranges with the help of bit-vector information. This not only makes the moving objects to reduce the number of sending \(RequestDomain\) messages and \(UpdateResult\) messages to the server for receiving new resident domains and letting the server update some query results, respectively, but also makes the server to reduce the communication overhead for assigning new resident domains to the moving objects.