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

Question

Я хочу использовать структуру данных для сортировки данных пространства-времени (x, y, z, время).

В настоящее время алгоритм обработки ищет набор из 4D (x, y, z, времени) точек, учитывая сферический (3d) пространственный радиус и линейный (1d) временной радиус, отмечая для каждой точки, какие другие точки находятся в пределах эти радиусы. Причина в том, что после обработки я могу запросить любую точку 4D для всех ее соседей за O (1) раз.

Однако в некоторых распространенных конфигурациях пространственных и временных радиусов первый запуск алгоритма занимает около 12 часов. Хотите верьте, хотите нет, но это действительно быстро по сравнению с тем, что существует в нашей отрасли. Тем не менее, я хочу помочь ускорить начальные запуски и поэтому хочу знать: Подходит ли kd-дерево для 4-мерных данных пространства-времени?

Обратите внимание, что я не ищу реализации поиска ближайшего соседа или поиска k ближайших соседей.

Подробнее:

Пример набора данных имеет 450 000 4D точек.

Некоторые наборы данных ограничены во времени, поэтому упорядочение по времени, безусловно, экономит обработку, но все же приводит ко многим проверкам расстояния.

Время представлено датами в стиле Excel с типичными диапазонами от 30 000 до 39 000 (приблизительно). Пространственные диапазоны иногда являются более высокими значениями, иногда более низкими значениями, но диапазон между каждой пространственной координатой аналогичен времени (например, maxX-minX ~ maxT-minT).

Еще больше информации:

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

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

Временной интервал этих наборов данных колеблется между 5-20 годами данных.

Для действительно старых данных (> 8 лет) события часто были очень пространственно плотными по двум причинам: 1) тогда было относительно мало доступных датчиков, и 2) датчики были расположены близко друг к другу, так что соседние события может быть правильно подтверждено с низкой ошибкой. Дальнейшие события могут быть записаны, но у них слишком высокая ошибка

Для более новых данных (<8 лет) события часто бывают очень плотными во времени по обратным причинам: 1) обычно доступно много датчиков, и 2) датчики размещаются через равные промежутки времени на большем расстоянии . </p>

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

Заключение

Я явно должен задавать больше вопросов на этом сайте.

В течение следующего времени я буду тестировать несколько решений, которые будут включать в себя 4d-дерево kd, 3d-дерево kd с последующей проверкой временного расстояния (предложенное Дрю Холлом) и текущий алгоритм, который у меня есть. Кроме того, мне предложили другую структуру данных, называемую деревом TSP (разбиение пространства-времени), которая использует октре для пространства и bsp на каждом узле для времени, поэтому я также могу проверить это.

Предполагая, что я помню, я обязательно опубликую некоторые тесты профилирования для различных конфигураций радиусов времени / пространства.

Спасибо всем

Answer 1

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

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

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

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

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

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

Answer 2

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

Answer 3

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

Answer 4

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

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

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

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