3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.