Mastering Machine Learning Algorithms

KD Trees

As all KNN queries can be considered search problems, one of the most efficient way to reduce the overall complexity is to reorganize the dataset into a tree structure. In a binary tree (one-dimensional data), the average computational complexity of a query is O(log M), because we assume we have almost the same number of elements in each branch (if the tree is completely unbalanced, all the elements are inserted sequentially and the resulting structure has a single branch,  so the complexity becomes O(M)). In general, the real complexity is slightly higher than O(log M), but the operation is always much more efficient than a vanilla search, which is O(M²).

However, we normally work with N-dimensional data and the previous structure ...