Evaluating Efficiency

In this subsection, we evaluate efficiency of our continuous $k$ NN algorithm against different settings. The first set of experiments is conducted on various cell sizes. Fig.  shows the experimental results of CPU time and space requirement.

The larger the cells are, the larger the influence region of a query is. Here, influence region of a query $q$ is the total area of cells $c$ whose $mindist(c,q)\leq q.dist_k$ . As a result, the time costs of both algorithms on grid index with larger cells is more than ones with smaller cells. On the other hand, when the cells are too small (i.e., $\delta = \frac{1}{2048}$ ), many cells are empty which introduces more costs. It is clear that CircularTrip outperforms CPM on all cell sizes and CPM is more sensitive to cell size than CircularTrip. As described before, CircularTrip does not keep any book-keeping information. So, its memory space is always less than CPM's. The numbers above bars in Fig.  (b) are ratios of their memory spaces.

= -1mm = -1mm

Figure: Effect of $\delta$

[Time]

[Space]

Figure: Effect of $k$

[Time]

[Space]

Figure: Effect of $N$ and $n$

[Varying $N$ ($\times 1K$ )]

[Varying $n$ ($\times 1K$ )]

The second experiment tests an effect of $k$ . From the experiment results as shown in Fig. , we can see that CircularTrip is always $2$ times faster than CPM while its memory space is at most $78\%$ of CPM's.

The final experiment in this part is to evaluate an impact of cardinality of data points and queries. The experiment results are depicted in Fig. . Following the trends in the previous experiments, CircularTrip is faster than CPM on all settings. It is interesting that with the number of queries increasing, performance of CPM degrades more significantly than CircularTrip. This is because our algorithm minimizes both initial $k$ NN computation costs and continuous monitoring cost while only the cost of initial $k$ NN computation is minimized in CPM. When $n = 10K$ , CPM is $4$ times slower than CircularTrip.