High dimensional kNN-graph construction using space filling curves
Sami Sieranoja · UEF eRepo (University of Eastern Finland) · 2015
The k nearest neighbor (kNN) graph has an important role in many computer science fields including machine learning and data mining. Although many fast methods exist for constructing kNN graph for low dimensional data, it is still an open question how to do it efficiently in high dimensional cases. We present a new method to construct approximate kNN graph for medium to high dimensional data. Our method uses space filling curves to construct initial graph and then continues to improve this using neighborhood propagation. It is targeted for Euclidean distance metric but has potential to be applied for general Minkowski distance metrics. Experiments show that the method is faster than compared methods with three different benchmark data sets which dimensionality ranges from 14 to 544.