Nearest Neighbor Applet

How to use the applet?

  1. Enter the data set by clicking in the canvas with your mouse to create new points or click on the "Uniform Dist" button to add 100 new points uniformly distributed or click on the "Normal Dist" button to add 100 new points normaly distributed. You can press these buttons more than once to add new points to the data set.
  2. Switch to search mode by clicking on the "Nearest neighbor" button. (You can always switch back to edit points after.)
  3. While in search mode, click in the canvas to search the k nearest point(s) from your click position.
  4. You can change the number of nearest points to search by pushing the "+" and "-" buttons.

Note: The mean of the normal distribution is the center of the canvas and the standard deviation is 1/4 of the width. The points are generated using the polar method described in "Random variate generation in one line of code". Other links on random number generation can be found at Random Number Generation (Luc Devroye) .

Nearest Neighbor Search mode:

The search mode is where the projection methodsearch algorithm is tested. If you click in the canvas, you can see 5 things:

  1. A red point representing the test point you created;
  2. Green point(s) representing the k-nearest neighbor(s);
  3. A dark gray circle around the test point showing the minimum circle that contains the k-nearest neighbor(s);
  4. A light gray circle showing the maximum radius (rd) for the nearest point on the projected axis;
  5. Two light gray lines showing the boundary of the region in which the points are tested for finding nearest neighbor(s).

You will also find a message text field with some information about the nearest neighbors' search:

  1. The number of distance computed while searching for the k-nearest neighbor(s);
  2. The number of computation needed for the brute force method (i.e.looking at all the points in the data set).
  3. The ratio (%) between the previous results.

Simulation of random test points:

The search mode previously described allows you to input only a single test point at a time. However, we are also interested to see the average results of a lot of test points to observe how the algorithm performs in the long run. To accomplish that, the applet has a button "Go Simulation" that start a series of a 1000 uniformly distributed random tests point. The result of this series of test is the average number of distance computed per test compared to the brute force method. It is displayed in the message text field at the bottom of the applet. Here is an example with 300 normaly distributed points in the data set and k = 1:

Average Number Of Compare: 54/300 (18%)

"54" is the average number of compare (or distance computations) done per test and "300" is the number of compare using the bute force method. The ratio (%) is also displayed.

This option allows you to study the influence of the data set's distribution and size as well as the number of nearest neighbors to search.

Too bad! Reactivate your java or get a new browser!

Java Source :

(right click and save) Nearest.java