Trees to speed up the inference

An array is not the only possible candidate for KNN's memory implementation. To make neighbors search faster, many implementations use special data structures such as a KD tree or a ball tree.

Check scikit-learn documentation if you're interested in more details: http://scikit-learn.org/stable/modules/neighbors.html#nearest-neighbor-algorithms.