Answers.Body: <p>The exhaustive nearest neighbor search performs an exhaustive search of the nearest neighbor (i.e. the closest image or matches, depending on your application). Here an exhaustive search means that you will compare your query image with any other image, or, in the case of feature matching, you will compare every feature of the query image with every other feature of the target/reference image.</p>
  
  <p>The <span class="math-container">$k$</span>-nearest neighbor search finds the <span class="math-container">$k$</span> closest images. You typically do that by first building a KD-tree with your query (or target) image, so that to speed up the search for the <span class="math-container">$k$</span>-nearest neighbors of your query image. </p>
  
  <p>(Btw, in case you are interested in the concept of feature matching, in OpenCV, the class that you can use to perform an exhaustive search for the matches between two images is the <code>BFMatcher</code> (which stands for Brute Force Matcher), while the class to perform the search with a KD-tree for the k-nearest neighbhours is <code>FlannBasedMatcher</code>).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-02T21:27:46.210Z
Answers.LastActivityDate: 2020-06-02T22:11:44.267Z
Answers.LastEditDate: 2020-06-02T22:11:44.267Z
Answers.UserDisplayName: nbro
Body: <p>I have two lists of feature vectors calculated from pre-trained CNN for image retrieval task:</p>
  
  <p>Query: <code>FV_Q</code> and Reference <code>FV_R</code>.</p>
  
  <pre><code>&gt;&gt;&gt; FV_R.shape
  (3450, 128)
  
  &gt;&gt;&gt; FV_Q.shape
  (3450, 128)
  </code></pre>
  
  <p>I am a little confused between the concept of <strong>exhaustive nearest neighbor search</strong> and <strong>k-nearest neighbor search</strong>. </p>
  
  <p>In python, I use <code>from sklearn.neighbors import KDTree</code> to extract top <code>k = 5</code> similar images from the reference database, given the query image!</p>
  
  <p>Can somebody explain if there might be any similarities/differences between these two concepts? </p>
  
  <p>Am I making a mistake somewhere in my feature vector comparison?</p>
  
Tags: <convolutional-neural-networks><python><comparison><computer-vision><image-recognition>
Title: What is the difference between exhaustive nearest neighbor search and k-nearest neighbour search?
UserDisplayName: doplano
ThreadText: # What is the difference between exhaustive nearest neighbor search and k-nearest neighbour search?
  
  (Asked by: username_0 on 2020-02-14)
  
  I have two lists of feature vectors calculated from pre-trained CNN for image retrieval task:
  
  Query: `FV_Q` and Reference `FV_R`.
  
  ```
  >>> FV_R.shape
  (3450, 128)
  
  >>> FV_Q.shape
  (3450, 128)
  
  ```
  
  I am a little confused between the concept of **exhaustive nearest neighbor search** and **k-nearest neighbor search**.
  
  In python, I use `from sklearn.neighbors import KDTree` to extract top `k = 5` similar images from the reference database, given the query image!
  
  Can somebody explain if there might be any similarities/differences between these two concepts?
  
  Am I making a mistake somewhere in my feature vector comparison?
  
  **Tags:** convolutional-neural-networks, python, comparison, computer-vision, image-recognition
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-02. Score: 1
  
  The exhaustive nearest neighbor search performs an exhaustive search of the nearest neighbor (i.e. the closest image or matches, depending on your application). Here an exhaustive search means that you will compare your query image with any other image, or, in the case of feature matching, you will compare every feature of the query image with every other feature of the target/reference image.
  
  The $k$-nearest neighbor search finds the $k$ closest images. You typically do that by first building a KD-tree with your query (or target) image, so that to speed up the search for the $k$-nearest neighbors of your query image.
  
  (Btw, in case you are interested in the concept of feature matching, in OpenCV, the class that you can use to perform an exhaustive search for the matches between two images is the `BFMatcher` (which stands for Brute Force Matcher), while the class to perform the search with a KD-tree for the k-nearest neighbhours is `FlannBasedMatcher`).
  
  
  ---
  
  