Experimental Study

In this section, we evaluate our continuous $ k$ NN algorithm. Since CPM significantly outperforms other existing algorithms, it is used as a benchmark algorithm in our evaluation. The following algorithms have been implemented by C++. All experiments were conducted on the PCs with P4 3.2GHz CPU and 2GB memory.

  1. CPM: CPM continuous $ k$ NN algorithm [MHP05].
  2. CircularTrip: our CircularTrip-based continuous $ k$ NN algorithm (Algorithm [*]).

In accordance with the experimental study of previous work [XMA05,MHP05], the same spatio-temporal data generator [] is employed. Specifically, this data generator outputs a set of data points moving on the road network of Oldenburg, a German city. Every data point is represented by its location at successive time stamps. Parameter data point agility indicates the percentage of total data points that report their location updates at each time stamp. After reaching its destination, a moving data point randomly selects a new destination and continues moving toward it. Moving speed may be slow, medium, and fast. Data points with slow speed move $ 1 / 250$ of the extent of space per time stamp. Medium and fast speed are $ 5$ and $ 25$ times faster than slow speed, respectively. Continuous $ k$ NN queries are generated in the similar way. All queries are evaluated at each time stamp and the length of evaluation is $ 100$ time stamps. Table below lists the parameters which may potentially have an impact on our performance study. In our experiments, all parameters use default values unless otherwise specified.


 
Parameter 
 
Range 
 Default Values 
 cell size ($ \delta$   $ \frac{1}{2048}$ , $ \frac{1}{1024}$ , $ \frac{1}{512}$ , $ \frac{1}{256}$ , $ \frac{1}{128}$ , $ \frac{1}{64}$     $ \frac{1}{256}$  
 number of NNs ($ k$  $ 1$ , $ 4$ , $ 16$ , $ 64$ , $ 256$    $ 16$  
 number of data points ($ N$  $ 30$ , $ 50$ , $ 70$ , $ 100$ , $ 150$ , $ 200$ ($ K$  $ 100K$  
 number of queries ($ n$  $ 1$ , $ 3$ , $ 5$ , $ 7$ , $ 10$ ($ K$  $ 5K$  
 data point agility   $ 10$ , $ 30$ , $ 50$ , $ 70$ ($ \%$  $ 50\%$  
 query agility   $ 10$ , $ 30$ , $ 50$ , $ 70$ ($ \%$  $ 30\%$  
 moving speed   slow, medium, fast   medium 



Subsections
Muhammad Aamir Cheema 2007-10-11