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

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

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

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

Больше информации:

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

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

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

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

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

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

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

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

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

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

Заключение

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

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

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

Спасибо всем