Подходит ли kd-дерево для данных 4D пространства-времени (x, y, z, время)?

Чтобы немного расширить мои комментарии к ответу выше:

Согласно литературе, для kd-деревьев требуются данные с евклидовыми координатами. Они, вероятно, не являются строго необходимыми, но их, безусловно, достаточно: гарантия того, что все координаты являются евклидовыми, гарантирует применение нормальных пространственных правил и позволяет легко разделить точки по их местоположению и построить древовидную структуру.

Время немного странное. По правилам специальной теории относительности вы используете метрику Минковского, а не стандартную евклидову метрику, когда работаете с временными координатами. Это вызывает всевозможные проблемы (наиболее серьезные из них разрушают смысл «одновременности») и обычно заставляет людей бояться временных координат. Однако этот страх необоснован, потому что, если вы знаете, что работаете над физикой, ваша временная координата почти наверняка будет на практике евклидовой.

Что означает, что координата является евклидовой? Она должна быть независима от всех остальных координат. Сказать, что время является евклидовой координатой, означает, что вы можете ответить на вопрос: «Эти две точки близки друг к другу во времени?» просматривая только их временные координаты и игнорируя любую дополнительную информацию. Легко понять, почему отсутствие этого свойства может нарушить схему, разделяющую точки по значениям их координат; если две точки могут иметь радикально разные временные координаты, но все же считаться «близкими во времени», то дерево, которое сортирует их по временным координатам, не будет работать очень хорошо.

Примером евклидовой временной координаты может быть любое время, указанное в одном согласованном часовом поясе (например, время UTC). Если у вас есть двое часов, одни в Нью-Йорке и одни в Токио, вы знаете, что если у вас есть два измерения с пометкой «12:00 UTC», то они были сделаны в одно и то же время. Но если измерения производятся по местному времени, то есть один говорит «12:00 по нью-йоркскому времени», а другой — «12:00 по токийскому времени», вам придется использовать дополнительную информацию о местоположении и часовых поясах городов, чтобы выяснить сколько времени прошло между двумя измерениями.

Таким образом, пока ваша временная координата последовательно измеряется и находится в здравом уме, она будет евклидовой, а это означает, что она будет прекрасно работать в kd-дереве или аналогичной структуре данных.

Если бы вы сохранили индекс для ваших точек, отсортированных по временному измерению, не могли бы вы сначала выполнить первоначальную обрезку в одномерном временном измерении, сократив таким образом количество вычислений расстояния? (Или это упрощение?)

Вы действительно не дали достаточно информации, чтобы ответить на этот вопрос.

Но, конечно, в целом kd-деревья идеально подходят для 4-х (или 5-ти, или 6-ти, или...) размерных данных --- если пространственное (или, в вашем случае, пространственное/временное) распределение поддается декомпозиции kd-дерева . Другими словами, это зависит (звучит знакомо?).

kd-деревья — это всего лишь один из методов пространственной декомпозиции, который подходит для определенных локализованных поисков. По мере того, как вы переходите к более высоким измерениям, проблема проклятия размерности, конечно, поднимает голову, но 4d не так уж и плох (хотя вы, вероятно, хотите, по крайней мере, несколько сотен точек).

Чтобы узнать, сработает ли это для вас, вы должны проанализировать некоторые другие критерии. Достаточно ли хорош приблизительный поиск NN (это может очень помочь). Балансировка дерева может быть дорогой? и Т. Д.

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