Расчет расстояний для массивного количества устройств/узлов

Question

У меня есть N мобильных устройств/узлов (скажем, 100K), и я периодически получаю их значения местоположения (широта, долгота).

Некоторые устройства «логически подключены» примерно до M другие устройства (скажем, 10). Моя программа периодически сравнивает расстояние между каждым устройством и его логически подключенными устройствами и определяет, находится ли расстояние в пределах порога (скажем, 100 метров).

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

Сложность порядок грубой силы подход будет Н * М или Θ (N 2)

Программа делает это через каждые 3 секунды (все устройства являются мобильными), таким образом, 100K * 10 = расчеты 3M каждые 3 секунды является нехорошо.

Любые хорошие/классические алгоритмы для этой операции?

Answer 1

(Чтобы упростить мое объяснение, я опустил детали о каждом устройстве только быть логически связанным с М ~ = 10 других устройств.)

Пространственно разметить места вашего устройства. Если вас интересуют только пары устройств на расстоянии менее 100 метров, рассмотрите следующие два алгоритма.

1. Для i = 1..N, j = 1..N, i! = J, вычислить расстояние между устройствами i и j.

2. Для i = 1..N, вычислите ячейку сетки, где широта и долгота для устройства i находятся, где ячейки сетки составляют 100 метров. Теперь для всех непустых ячеек сетки сравните устройства в этой ячейке только с устройствами в одной и той же ячейке или одной из восьми соседних ячеек.

   Структура данных для этого подхода будет в основном представлять собой карту M из индекса ячейки сетки (s, t) в список устройств в этой ячейке сетки.

Первый подход наивный и будет стоить Q (N 2 ). Второй подход будет, если предположить, что существует некоторая «постоянная максимальная плотность устройств», быть ближе к Θ (N) на практике. Радиус 100 метров - довольно маленький.

Псевдокод для второго подхода выглядел бы следующим образом.

M = {} 

for i = 1..N 
    (s,t) = compute_grid_cell(i) 
    if ((s,t) not in M) 
    M[(s,t)] = [] 
    M[(s,t)].push(i) 

for i = 1..N 
    (s,t) = compute_grid_cell(i) 
    for s' in [s-1, s, s+1] 
    for t' in [t-1, t, t+1] 
     if (s',t') in M 
     for j in M[(s',t')] 
      if i != j and distance(i, j) < 100 
      report (i,j) as a pair of devices that are "close" 

Answer 2

Вы можете использовать квадранты или кривую morton. Это уменьшает размеры и облегчает решение.