Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
Some space filling curves like the Hilbert Curve are able to map an n-dimensional space to a one dimensional line whilst preserving locality. Does that mean that we could map a dataset of high dimensional points to a line and expect the order of the nearest neighbors to be preserved?
If so, wouldn't that be more efficient than building a Ball tree?
Space filling curves are sometimes used for nearest neighbor search. See these applications of Z-order curves and Hilbert curves.
The idea is as follows. Let $f$ be a space-filling curve. Given a point $x$, index it as $f^{-1}(x)$.* Given a query point $y$, return all points indexed in an interval around $f^{-1}(y)$. If $y$ is close to $x$, there is a good chance that $x$ will be returned so long as $f^{-1}$ tends to preserve locality. Different space filling curves have this property to different degrees.
* Note that space-filling curves are not injective so the inverse is not uniquely defined. But in practice we choose a finite grid on $[0, 1]^n$ and an appropriate iterate that is bijective so we don't have a problem.
Preserving "locality" is a desirable property in space-filling curves, especially in this context. But we cannot hope to actually preserve the ordering of the nearest neighbors for all points. (The discrete versions of Hilbert's curve put adjacent cells nearly on opposite ends of the curve; in wikipedia's illustrations, see the top-central region.)
This idea might still be useful, as an sort of k approximately-nearest neighbor algorithm; but I'm not convinced that producing an appropriate (discrete version of) a space-filling curve for a dataset and querying new points onto that curve will actually be substantially faster than ball-tree. Another problem is that the error in the approximations of "nearest" are dependent on the location along the curve, so that which curve you select will have a substantial impact on the correctness of the approximations for different sample points.
