<p>The <a href="http://www.mathworks.com/help/stats/kdtreesearcher-class.html" rel="nofollow noreferrer">code</a> builds a <a href="http://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search" rel="nofollow noreferrer">KD-tree</a> space-partitioning structure to speed up <a href="https://en.wikipedia.org/wiki/K-nearest_neighbors_algorithm" rel="nofollow noreferrer">nearest neighbor search</a>, think of it like building <a href="https://en.wikipedia.org/wiki/Database_index" rel="nofollow noreferrer">indexes</a> commonly used in RDBMS to speed up lookup operations.</p>

<p>In addition to nearest neighbor(s) searches, this structure also speeds up <a href="http://www.mathworks.com/help/stats/kdtreesearcher.rangesearch.html" rel="nofollow noreferrer">range-searches</a>, which finds all points that are within a distance <code>r</code> from a query point.</p>

<p>As pointed by @SamRoberts, the core of the code is implemented in C/C++ as a MEX-function.</p>

<p>Note that <code>knnsearch</code> chooses to build a <a href="http://www.mathworks.com/help/stats/classification-using-nearest-neighbors.html#bsfsm9c" rel="nofollow noreferrer">KD-tree</a> only under certain conditions, and falls back to an exhaustive search otherwise (by naively searching all points for the nearest one).</p>

<p>Keep in mind that in cases of very high-dimensional data (and few instances), the algorithm degenerates and is no better than an exhaustive search. In general as you go with dimensions <code>d&gt;30</code>, the cost of searching KD-trees will increase to searching almost all the points, and could even become worse than a brute force search due to the overhead involved in building the tree.</p>

<p>There are other variations to the algorithm that deals with high dimensions such as the <a href="https://en.wikipedia.org/wiki/Ball_tree" rel="nofollow noreferrer">ball trees</a> which partitions the data in a series of nesting hyper-spheres (as opposed to partitioning the data along Cartesian axes like KD-trees). Unfortunately those are not implemented in the official Statistics toolbox. If you are interested, here is <a href="http://arxiv.org/abs/1007.0085" rel="nofollow noreferrer">a paper</a> which presents a survey of available kNN algorithms.</p>

<p><img src="https://i.stack.imgur.com/l9xPN.png" alt="kdtree_search"></p>

<p><em>(The above is an illustration of searching a kd-tree partitioned 2d space, borrowed from the docs)</em></p>
Can someone tell me about the kNN search algo that Matlab uses?
<p>I wrote a basic O(n^2) algorithm for a nearest neighbor search. As usual Matlab 2013a's knnsearch(..) method works a lot faster.</p>

<p>Can someone tell me what kind of optimization they used in their implementation?</p>

<p>I am okay with reading any documentation or paper that you may point me to.</p>

<p>PS: I understand the documentation on the site mentions the paper on kd trees as a reference. But as far as I understand kd trees are the default option when column number is less than 10. Mine is 21. Correct me if I'm wrong about it.</p>