Distance Calculation for massive number of devices/nodes

Question

I have N mobile devices/nodes (say 100K) and I periodically obtain their location ( latitude , longtitude ) values.

Some of the devices are "logically connected" to roughly M other devices (say 10). My program periodically compares the distance between the each device and its logically connected devices and determines if the distance is within a threshold (say 100 meters).

I need a robust algorithm to calculate these distances to the logically connected devices.

The complexity order of brute force approach would be N*M or Θ(N2)

The program does this every 3 seconds (all devices are mobile), thus 100K*10 = 3M calculations every 3 seconds is not good.

Any good/classical algorithms for this operation ?

Answer 1

(To simplify my explanation, I have omitted the detail about each device only being logically connected to M ~= 10 other devices.)

Spatially partition your device locations. If you are only interested in pairs of devices less than 100 meters apart, consider the following two algorithms.

1. For i = 1..N, j = 1..N, i != j, compute distance between devices i and j.

2. For i = 1..N, compute which grid cell the latitude and longitude for device i lies in, where grid cells are 100 meters square. Now for all nonempty grid cells, compare devices in that cell only with devices in the same cell or one of the eight adjacent cells.

   The data structure for this approach would basically be a map M from grid cell index (s,t) to list of devices in that grid cell.

The first approach is naive and will cost Θ(N²). The second approach will, assuming there is some "constant maximum density of devices," be closer to Θ(N) in practice. A 100 meter radius is fairly small.

The pseudocode for the second approach would look something like the following.

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

You can use a quadtree or a morton curve. It's reduce the dimensions and make the solution easier.