我编写了一个基本的O(n^2)算法来进行最近邻搜索。通常情况下，Matlab 2013a的knnsearch(..)方法运行得非常快。
有人能告诉我他们在实现中使用了什么样的优化吗？
我愿意阅读您指出的任何文档或论文。
附注：我知道网站上的文档提到了关于kd树的论文作为参考。但据我所知，当列数少于10时，kd树是默认选项。我的列数是21。如果我理解错了，请纠正我。
回答：
MathWorks在实现最近邻搜索时所做的最大优化是，所有复杂的部分都是用编译后的C语言在MEX文件中实现的，而不是用MATLAB实现的。
对于像kNN这样的算法（根据我的有限理解）是相当递归且难以向量化的，这种方式可能会带来如此大的改进，以至于O()分析只有在相当高的n值时才相关。
更详细地说，knnsearch命令在后台使用createns来创建一个NeighborSearcher对象。默认情况下，当X的列数少于10时，这将是一个KDTreeSearcher对象，而当X的列数超过10时，这将是一个ExhaustiveSearcher对象（KDTreeSearcher和ExhaustiveSearcher都是NeighborSearcher的子类）。
所有NeighbourSearcher类对象都有一个方法knnsearch（您很少会直接调用这个方法，而是使用便捷命令knnsearch）。KDTreeSearcher的knnsearch方法直接调用一个MEX文件来完成所有复杂的工作。这个文件位于matlabroot\toolbox\stats\stats\@KDTreeSearcher\private\knnsearchmex.mexw64中。
据我所知，这个MEX文件几乎执行了文档页面中引用的Friedman、Bentely和Finkel的论文中描述的算法，没有结构上的变化。正如论文标题所示，这个算法是O(log(n))而不是O(n^2)。不幸的是，无法检查MEX文件的内容来确认这一点。
