Approximate Nearest Neighbor Search using a Single Space-filling Curve and Multiple Representations of the Data Points
G. Mainar-Ruiz, Juan-Carlos Pérez-Cortés · 2006
In this work, a fast approximate nearest neighbour search algorithm using single space-filling curve (SPFC) mapping and a set of synthetic prototype representations is presented. The results are comparable to a multiple-spacefilling scheme, but achieving a much faster execution time, since computing multiple transformations and SPFC mapping is avoided, at the expense of having a more densely populated one-dimensional representation of the data-set. The advantages and limitations of the model are discussed, and an experimental evaluation with synthetic data and with a large, real high-dimensional optical character recognition data-set is presented