Regarding space filling curves some implementations would be: 1) http://code.google.com/p/uzaygezen/ http://code.google.com/p/uzaygezen/ (Hilbert) 2) http://w

Regarding space filling curves some implementations would be: 1) http://code.google.com/p/uzaygezen/ http://code.google.com/p/uzaygezen/ (Hilbert) 2) http://www.h2database.com/html/features.html#multi_dimensional http://www.h2database.com/html/features.html#multi_dimension... (Z-order) Other space transformations could be employed like the Pyramid technique or the iDistance (http://obsearch.net http://obsearch.net). Nevertheless, if the "intrinsic dimensionality" of your objects is too high then the curse of dimensionality comes into play and sequential scan might be cheaper. In such a case the Va-file, IQ-Tree or even "sketches" might be the only way to go.