距离计算设备/节点数量庞大 [英] Distance Calculation for massive number of devices/nodes

问题描述

我的 N 的移动设备/节点（比如100K），我定期地获得自己的位置（纬度，经度）值。

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

一些装置被逻辑连接到大致的 M 的其它设备（例如10）。 我的程序周期性地比较的距离的每个设备和其在逻辑上连接的设备之间，并确定如果该距离在阈值内（例如100米）。

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.

暴力破解方法的复杂性顺序将是N * M或Θ（N2）

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

该程序将执行每3秒（所有设备都是移动），从而100K * 10 = 3M计算，每3秒是不好的。

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 ?

推荐答案

（为了简化我的解释，我省略了细节只有逻辑上连接到M〜= 10其他设备每台设备。）

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

在空间分割设备的位置。如果你只关心对设备的开不到100米，考虑以下两种算法。

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. 对于i = 1..N，J = 1 ... N，我！= j的，设备i和j之间的计算距离。

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

对于i = 1..N，计算该网格的纬度和经度的设备我就在于，在网格单元100米见方。现在对所有非空的网格单元，只有在相同的细胞或装置的8个相邻小区中的一个比较在该电池装置

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.

的数据结构这一做法将主要是由网格指数（S，T），在该网格单元的设备列表中的映射M。

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.

第一种方法是幼稚和将花费Θ（N ² ）。第二种方法将，假设有一些装置的恒定最大密度，在实践中接近Θ（N）。一个100米半径的是的相当小的。

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.

伪code的第二种方法看起来像下面这样。

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"

这篇关于距离计算设备/节点数量庞大的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！