Какова наилучшая структура данных для хранения данных, чувствительных к расстоянию?

Question

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

Чтобы решить эту проблему для каждого города, мне нужно найти набор ближайших метеостанций в каком-то радиусе и усреднить их данные. Брутфорс - это вычисление расстояний от каждого города до каждой метеостанции, но для моих данных это слишком медленно. Поэтому я подумал, что здесь может помочь структура данных дерева. Я попытался использовать R-деревья для разделения метеостанций по координатам, но есть проблема - такой подход позволяет мне находить метео-станции в каком-то узле дерева, но он не дает мне информации о соседних узлах, чтобы быстро вычислить условие радиуса (например, если город очень близок к границе узла R-дерева).

Существует ли стандартная структура данных дерева, которая позволяет быстро найти нужный узел, но также предоставляет набор пространственных соседей на одном уровне дерева?

Answer 1

Вы должны, вероятно, не беспокоиться о «соседей по же уровне "или такой, эта информация не обязательно означает много. Я думаю, вы должны, вероятно,

1. Решите, хотите ли вы, чтобы все метеорологические станции находились на заданном расстоянии (запрос диапазона) или ближайшие метеорологические станции.
2. Тогда я бы просто использовал API индекса, который вы используете, чтобы найти станции.
3. Затем вычислите расстояние.

R-деревья в порядке, но они обычно довольно медленны для загрузки. Если время загрузки является проблемой, вы можете попробовать дерево R +, дерево R * или, возможно, Quadtrees (для небольших наборов данных) или PH-Tree (для больших наборов данных, моя реализация на Java).

Как данные обрабатываются внутри дерева, не должно вызывать беспокойства. Кто когда-либо реализовал дерево, вероятно, реализовал наиболее эффективный способ поиска желаемых соседей.

Answer 2

Как насчет использования базы данных? А затем запросите его, чтобы найти точки, близкие к определенной точке? Многие базы данных уже поддерживают геопространственных данных, которые можно индексировать и запрос:

• posgis
• MongoDB geospatial
• MySQL extension