kd-tree

k-dimension tree

1. Calculating the variance for each feature.
2. For the feature which has the largest variance, we find the medium value of the data in this feature and split from this data
3. continue 1 and 2

Kd-tree has $O(k\cdot n log(n))$ where k is the dimension for features, n is the number of the data

And the process of searching is