Отображение N-мерного значения в точку на кривой Гильберта

Мне не ясно, как это сделает то, что Вы хотите. Рассмотрите этот trival 3D случай:

001 ------ 101
 |\         |\
 | \        | \
 |  011 ------ 111
 |   |      |   |
 |   |      |   |
000 -|---- 100  |
  \  |       \  |
   \ |        \ |
    010 ------ 110

, который может быть "Hilbertized" следующим путем:

001 -----> 101
  \          \
   \          \
    011        111
     ^          |
     |          |
000  |     100  |
  \  |       \  |
   \ |        \ V
    010        110

в 1D порядок:

000 -> 010 -> 011 -> 001 -> 101 -> 111 -> 110 -> 100

Вот противный бит. Рассмотрите список пар и 1D расстояния ниже:

000 : 100 -> 7
010 : 110 -> 5
011 : 111 -> 3
001 : 101 -> 1

Во всех случаях, лево-и правые значения являются тем же 3D расстоянием друг от друга (+/-1 в первом положении), которые, кажется, подразумевают подобную "пространственную местность". Но линеаризуя любым выбором размерного упорядочивания (y, затем z, затем z, в вышеупомянутом примере) повреждения та местность.

Другой способ сказать это - то, что взятие начальной точки и упорядочивание остающихся точек их расстоянием от той начальной точки обеспечат существенно отличающиеся результаты. Взятие 000 как запуск, например:

1D ordering : distance    3D ordering : distance
----------------------    ----------------------
        010 : 1           001,010,100 : 1
                          011,101,110 : sqrt(2)
                              111     : sqrt(3)
        011 : 2
        001 : 3
        101 : 4
        111 : 5
        110 : 6
        100 : 7

Этот эффект растет экспоненциально с количеством размеров (предполагающий, что каждый размер имеет тот же "размер").

Другая возможность состояла бы в том, чтобы создать kd-дерево на Ваших данных, и затем ко чтобы обход дерева для получения упорядочивания. Построение kd-дерева только требует, чтобы у Вас был хороший находящий средний алгоритм, которого существуют многие.

, который я не вижу, как можно использовать Гильбертову кривую в одном размере.

, Если Вы интересуетесь отображением точек к более низкому размеру при сохранении расстояний (с минимальной ошибкой) затем, можно изучить "Многомерное Масштабирование" алгоритмы.

Моделируемый отжиг является одним подходом.

Редактирование: Спасибо за комментарий. Я вижу то, что Вы подразумевали под Гильбертовым подходом Кривой теперь. Однако это - тяжелая проблема, и данный N=100 и 10 миллионов точек данных, я не думаю, что любой подход будет сохранять местность хорошо и работать за разумное количество времени. Я не думаю, что kd-деревья будут работать здесь.

При нахождении общего упорядочивания не важно для Вас, затем можно изучить находящееся на местности хеширование и другие приблизительные ближайшие соседние схемы. Иерархическое многомерное масштабирование с блоками точек для сокращения входного размера могло бы дать Вам хорошее упорядочивание, но снова это сомнительно в таком высоком размере.

Алгоритм отображения n-> 1 и 1-> n приведен здесь «Вычисление сопоставлений между одномерными и n-мерными значениями с использованием кривой заполнения гильбертова пространства» Дж. К. Лоудер

Если вы Google поищите «модуль SFC и наложение Kademlia», вы найдете группу, которая утверждает, что использует его как часть их система. Если вы посмотрите исходный код, вы, вероятно, сможете извлечь соответствующую функцию.