Efficient Construction of Neighborhood Graphs by the Multiple Sorting Method

Takeaki Uno, Masashi Sugiyama, Koji Tsuda

Neighborhood graphs are gaining popularity as a concise data representation in machine learning. However, naive graph construction by pairwise distance calculation takes $O(n^2)$ r…