Evaluating Effect of Agility

We first evaluate effects of agility and moving speed of data points. The CPU time of both algorithms is reported in Fig. . It demonstrates that when more location updates are issued at each time stamp, CPM's performance decreases more rapidly than CircularTrip. This is because to update results of the affected queries, CPM has to re-examine cells in their visit lists which causes more cells to be accessed during continuous monitoring. On the other hand, both algorithms are not sensitive to the moving speed of data points.

= -1mm = -1mm

Figure: Data Movement

[Varying Agility ($\%$ )]

[Varying Speed]

Figure: Query Movement

[Varying Agility ($\%$ )]

[Varying Speed]

Figure: Time Efficiency

[Initial Cost]

[Monitoring Cost]

Similarly, effects of agility and moving speed of queries are evaluated and the results are shown in Fig. . Due to the fact that CPM always deletes and issues new queries to update the moving queries, its time cost increases when more queries move. Performance of CircularTrip is stable because it takes advantages of previous computed results when handling query updates. Also, moving speed of queries does not affect both algorithms.

In the last set of experiments, we study the efficiency of initial computation and continuous monitoring separately. In the first experiment, all queries are moving and all data points are static. We slightly modify our algorithm so that it handles moving queries as the same as CPM. Clearly, for both algorithm all costs are initial computation cost only. Fig. (a) illustrates the results with respect to the data points cardinality. Although both algorithms access minimum number of cells, sCircularTrip's initial cost is $2$ to $4$ times smaller than CPM's because CPM has to maintain extra book-keeping information for each query. The second experiment studies continuous monitoring cost where all queries are static and their initial costs are omitted. As shown in Fig. (b), it is confirmed that CircularTrip accesses less cells than CPM during continuous monitoring.

As a short summary, our performance evaluation indicates that compared with CPM, CircularTrip-based $k$ NN algorithm is not only more time-efficient but also more space-efficient. Moreover, our algorithm is more scalable than CPM regarding cell size, $k$ , and cardinality as well as agility and moving speed of data points and queries.