Java Program to Find Nearest Neighbour for Dynamic Data Set

This is a Java Program to implement 2D KD Tree and find the nearest neighbor for dynamic input set. In computer science, a k-d tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. k-d trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). k-d trees are a special case of binary space partitioning trees.

Here is the source code of the Java Program to Find Nearest Neighbor for Dynamic Data Set. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to find nearest neighbor for dynamic data set
  2. import java.io.IOException;
  3. import java.util.Scanner;
  4.  
  5. class KDN
  6. {
  7.     int axis;
  8.     double[] x;
  9.     int id;
  10.     boolean checked;
  11.     boolean orientation;
  12.  
  13.     KDN Parent;
  14.     KDN Left;
  15.     KDN Right;
  16.  
  17.     public KDN(double[] x0, int axis0)
  18.     {
  19.         x = new double[2];
  20.         axis = axis0;
  21.         for (int k = 0; k < 2; k++)
  22.             x[k] = x0[k];
  23.  
  24.         Left = Right = Parent = null;
  25.         checked = false;
  26.         id = 0;
  27.     }
  28.  
  29.     public KDN FindParent(double[] x0)
  30.     {
  31.         KDN parent = null;
  32.         KDN next = this;
  33.         int split;
  34.         while (next != null)
  35.         {
  36.             split = next.axis;
  37.             parent = next;
  38.             if (x0[split] > next.x[split])
  39.                 next = next.Right;
  40.             else
  41.                 next = next.Left;
  42.         }
  43.         return parent;
  44.     }
  45.  
  46.     public KDN Insert(double[] p)
  47.     {
  48.         x = new double[2];
  49.         KDN parent = FindParent(p);
  50.         if (equal(p, parent.x, 2) == true)
  51.             return null;
  52.  
  53.         KDN newNode = new KDN(p, parent.axis + 1 < 2 ? parent.axis + 1 : 0);
  54.         newNode.Parent = parent;
  55.  
  56.         if (p[parent.axis] > parent.x[parent.axis])
  57.         {
  58.             parent.Right = newNode;
  59.             newNode.orientation = true; //
  60.         } else
  61.         {
  62.             parent.Left = newNode;
  63.             newNode.orientation = false; //
  64.         }
  65.  
  66.         return newNode;
  67.     }
  68.  
  69.     boolean equal(double[] x1, double[] x2, int dim)
  70.     {
  71.         for (int k = 0; k < dim; k++)
  72.         {
  73.             if (x1[k] != x2[k])
  74.                 return false;
  75.         }
  76.  
  77.         return true;
  78.     }
  79.  
  80.     double distance2(double[] x1, double[] x2, int dim)
  81.     {
  82.         double S = 0;
  83.         for (int k = 0; k < dim; k++)
  84.             S += (x1[k] - x2[k]) * (x1[k] - x2[k]);
  85.         return S;
  86.     }
  87. }
  88.  
  89. class KDTreeDynamic
  90. {
  91.     KDN Root;
  92.  
  93.     int TimeStart, TimeFinish;
  94.     int CounterFreq;
  95.  
  96.     double d_min;
  97.     KDN nearest_neighbour;
  98.  
  99.     int KD_id;
  100.  
  101.     int nList;
  102.  
  103.     KDN CheckedNodes[];
  104.     int checked_nodes;
  105.     KDN List[];
  106.  
  107.     double x_min[], x_max[];
  108.     boolean max_boundary[], min_boundary[];
  109.     int n_boundary;
  110.  
  111.     public KDTreeDynamic(int i)
  112.     {
  113.         Root = null;
  114.         KD_id = 1;
  115.         nList = 0;
  116.         List = new KDN[i];
  117.         CheckedNodes = new KDN[i];
  118.         max_boundary = new boolean[2];
  119.         min_boundary = new boolean[2];
  120.         x_min = new double[2];
  121.         x_max = new double[2];
  122.     }
  123.  
  124.     public boolean add(double[] x)
  125.     {
  126.         if (nList >= 2000000 - 1)
  127.             return false; // can't add more points
  128.  
  129.         if (Root == null)
  130.         {
  131.             Root = new KDN(x, 0);
  132.             Root.id = KD_id++;
  133.             List[nList++] = Root;
  134.         } else
  135.         {
  136.             KDN pNode;
  137.             if ((pNode = Root.Insert(x)) != null)
  138.             {
  139.                 pNode.id = KD_id++;
  140.                 List[nList++] = pNode;
  141.             }
  142.         }
  143.  
  144.         return true;
  145.     }
  146.  
  147.     public KDN find_nearest(double[] x)
  148.     {
  149.         if (Root == null)
  150.             return null;
  151.  
  152.         checked_nodes = 0;
  153.         KDN parent = Root.FindParent(x);
  154.         nearest_neighbour = parent;
  155.         d_min = Root.distance2(x, parent.x, 2);
  156.         ;
  157.  
  158.         if (parent.equal(x, parent.x, 2) == true)
  159.             return nearest_neighbour;
  160.  
  161.         search_parent(parent, x);
  162.         uncheck();
  163.  
  164.         return nearest_neighbour;
  165.     }
  166.  
  167.     public void check_subtree(KDN node, double[] x)
  168.     {
  169.         if ((node == null) || node.checked)
  170.             return;
  171.  
  172.         CheckedNodes[checked_nodes++] = node;
  173.         node.checked = true;
  174.         set_bounding_cube(node, x);
  175.  
  176.         int dim = node.axis;
  177.         double d = node.x[dim] - x[dim];
  178.  
  179.         if (d * d > d_min)
  180.         {
  181.             if (node.x[dim] > x[dim])
  182.                 check_subtree(node.Left, x);
  183.             else
  184.                 check_subtree(node.Right, x);
  185.         } else
  186.         {
  187.             check_subtree(node.Left, x);
  188.             check_subtree(node.Right, x);
  189.         }
  190.     }
  191.  
  192.     public void set_bounding_cube(KDN node, double[] x)
  193.     {
  194.         if (node == null)
  195.             return;
  196.         int d = 0;
  197.         double dx;
  198.         for (int k = 0; k < 2; k++)
  199.         {
  200.             dx = node.x[k] - x[k];
  201.             if (dx > 0)
  202.             {
  203.                 dx *= dx;
  204.                 if (!max_boundary[k])
  205.                 {
  206.                     if (dx > x_max[k])
  207.                         x_max[k] = dx;
  208.                     if (x_max[k] > d_min)
  209.                     {
  210.                         max_boundary[k] = true;
  211.                         n_boundary++;
  212.                     }
  213.                 }
  214.             } else
  215.             {
  216.                 dx *= dx;
  217.                 if (!min_boundary[k])
  218.                 {
  219.                     if (dx > x_min[k])
  220.                         x_min[k] = dx;
  221.                     if (x_min[k] > d_min)
  222.                     {
  223.                         min_boundary[k] = true;
  224.                         n_boundary++;
  225.                     }
  226.                 }
  227.             }
  228.             d += dx;
  229.             if (d > d_min)
  230.                 return;
  231.  
  232.         }
  233.  
  234.         if (d < d_min)
  235.         {
  236.             d_min = d;
  237.             nearest_neighbour = node;
  238.         }
  239.     }
  240.  
  241.     public KDN search_parent(KDN parent, double[] x)
  242.     {
  243.         for (int k = 0; k < 2; k++)
  244.         {
  245.             x_min[k] = x_max[k] = 0;
  246.             max_boundary[k] = min_boundary[k] = false; //
  247.         }
  248.         n_boundary = 0;
  249.  
  250.         KDN search_root = parent;
  251.         while (parent != null && (n_boundary != 2 * 2))
  252.         {
  253.             check_subtree(parent, x);
  254.             search_root = parent;
  255.             parent = parent.Parent;
  256.         }
  257.  
  258.         return search_root;
  259.     }
  260.  
  261.     public void uncheck()
  262.     {
  263.         for (int n = 0; n < checked_nodes; n++)
  264.             CheckedNodes[n].checked = false;
  265.     }
  266.  
  267. }
  268.  
  269. public class Dynamic_Nearest
  270. {
  271.  
  272.     public static void main(String args[]) throws IOException
  273.     {
  274.         int numpoints = 10;
  275.         Scanner sc = new Scanner(System.in);
  276.         KDTreeDynamic kdt = new KDTreeDynamic(numpoints);
  277.         double x[] = new double[2];
  278.  
  279.         System.out.println("Enter the first 10 data set : <x> <y>");
  280.         for (int i = 0; i < numpoints; i++)
  281.         {
  282.             x[0] = sc.nextDouble();
  283.             x[1] = sc.nextDouble();
  284.             kdt.add(x);
  285.         }
  286.  
  287.         System.out.println("Enter the co-ordinates of the point: <x> <y>");
  288.  
  289.         double sx = sc.nextDouble();
  290.         double sy = sc.nextDouble();
  291.  
  292.         double s[] = { sx, sy };
  293.         KDN kdn = kdt.find_nearest(s);
  294.         System.out.println("The nearest neighbor for the static data set is: ");
  295.         System.out.println("(" + kdn.x[0] + " , " + kdn.x[1] + ")");
  296.         sc.close();
  297.     }
  298. }

Output:

$ javac Dynamic_Nearest.java
$ java Dynamic_Nearest
 
Enter the first 10 data set :
1.2 3.3
2.3 3.4
4.5 5.6
6.7 7.8
8.9 9.0
10.1 11.3
15.6 19.4 
20.5 25.4
52.8 65.3
62.6 56.3
 
Enter the co-ordinates of the point: <x> <y>
60 34.2
 
The nearest neighbor for the static data set is: 
(62.6 , 56.3)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.