Java Program to Find Nearest Neighbour using Linear Search

«
»
This is a Java Program to find nearest neighbor using linear search. The simplest solution to the NNS problem is to compute the distance from the query point to every other point in the database, keeping track of the “best so far”. This algorithm, sometimes referred to as the naive approach, has a running time of O(Nd) where N is the cardinality of S and d is the dimensionality of M. There are no search data structures to maintain, so linear search has no space complexity beyond the storage of the database. Naive search can, on average, outperform space partitioning approaches on higher dimensional spaces.

Here is the source code of the Java Program to Find Nearest Neighbor Using Linear Search. 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 using a simple linear search
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. public class Linear_Search_Nearest
  6. {
  7.     public static void main(String args[])
  8.     {
  9.         Random random = new Random();
  10.         Scanner sc = new Scanner(System.in);
  11.         int datasetSize = 10;
  12.         double[][] data = new double[10][2];
  13.  
  14.         for (int i = 0; i < datasetSize; i++)
  15.             for (int j = 0; j < 2; j++)
  16.                 data[i][j] = random.nextDouble() * 10;
  17.  
  18.         System.out.println("Randomly generated Data set: ");
  19.         for (int i = 0; i < datasetSize; i++)
  20.             for (int j = 0; j < 2; j++)
  21.                 System.out.println(data[i][j++] + " ," + data[i][j]);
  22.  
  23.         System.out.println();
  24.         System.out.println("Enter the co-ordinates of the point: <x> <y>");
  25.         double x = sc.nextDouble();
  26.         double y = sc.nextDouble();
  27.  
  28.         double xmin = data[0][0], ymin = data[0][1], xclose = 0, yclose = 0;
  29.         for (int i = 0; i < datasetSize; i++)
  30.         {
  31.             if (Math.abs(data[i][0] - x) < xmin)
  32.             {
  33.                 xmin = data[i][0] - x;
  34.                 xclose = data[i][0];
  35.             }
  36.         }
  37.  
  38.         for (int i = 0; i < datasetSize; i++)
  39.         {
  40.             if (Math.abs(data[i][1] - y) < ymin)
  41.             {
  42.                 ymin = data[i][1] - x;
  43.                 yclose = data[i][1];
  44.             }
  45.         }
  46.  
  47.         System.out.println("The nearest neighbor is : (" + xclose + ", "
  48.                 + yclose + ")");
  49.  
  50.         sc.close();
  51.     }
  52. }

Output:

advertisement
$ javac Linear_Search_Nearest.java
$ java Linear_Search_Nearest
 
Randomly generated Data set: 
3.171455377670047 ,1.052119263026371
3.949033565232699 ,8.565344250655025
0.0208421026579253 ,5.963319480178625
5.9198056196163495 ,4.424992495072658
6.083654323496389 ,2.592835352360611
5.996752857974297 ,2.1046723166354777
3.165362843381636 ,5.1640243122381415
4.175425572150399 ,2.965443123350698
8.734700795907905 ,3.3650152184786064
5.5317982332184235 ,1.5076066489140683
 
Enter the co-ordinates of the point: <x> <y>
1 2
The nearest neighbor is : (0.0208421026579253, 1.052119263026371)

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
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 & technical discussions at Telegram SanfoundryClasses.