title: Finding Nearest neighboor with tuples of different size
body: <p>I am currently working on speech recognition. I have to compare the signature of an unknow sound (in term of frequencies) with other signatures of sounds that we know.<br>
  Concretely, we determine the "peaks" (=formants) in the spectrum of a sound, that are specific (that caracterise) to this sound. We memorize the frequencies of this peaks as tuples. We memorize the tuples of known sounds. There are thousands (if not hundred of thousands) of them.<br>
  For each new sound to identify, we compare the tuples of that sound to the tuples of the known sounds. That requires to make a lot of comparisons !</p>
  
  <p>I need to find a way to compare these tuples quickly.</p>
  
  <p>I already looked up and I found that it is a <strong>Nearest neighbor search</strong> problem.
  <strong>However I don't think that I can use theses algorithms.</strong></p>
  
  <p>Indeed, the tuples can have a different number of components.
  The components are just frequencies (in kHz).
  It can be (1 ; 2) or (1 ; 2.4 ; 4 ; 5 ; 6 ; 7 ; 7.1 ; 11 ; 12.1; 13) (up to 20 components).</p>
  
  <p><strong>So my question is :</strong> I don't have a dataset with tuples of the same "dimension", how can I find the nearest neighboor ?</p>
  
  <p>It is my understanding that in order to apply Nearest neighboor algorithms one has to have <em>tuples of the same dimension</em>. </p>
  
  <p>Thanks for reading me.<br>
  Have a nice day!</p>
  
  <p><strong>EDIT:</strong><br>
  I don't just need to find <strong>the</strong> closest neighboors, I actually need to find <strong>all</strong> the neighbooring points that are distant by less than a distance D to my reference point.</p>
  
  <p><strong>EDIT2:</strong><br>
  @random_hacker: No they don't. You can compare an element of the tuple with an element of another tuple, only if the difference between these two elements is &lt; threshold. </p>
  
  <p><strong>EDIT3:</strong><br>
  You're absolutly right mathias, I just typed something "random".
  In fact the elements of a tuple are frequencies sorted (ascending) and indeed each frequency of a tuple only appears once.
  So (4 ; 2) is wrong, it should be (2 ; 4) and (2 ; 2 ; 4) doesn't exist, it's (2;4) (no repeat)</p>