php - 查找超过 100K 个位置之间的距离

Question

我有两个带有位置的 MySQL 表，table1 和 table2(见下文)。每个表中有 > 100K 行。我想使用它们的地理位置找到这两个表中每个位置之间的距离。

这是用于查找单个地理位置(例如 (-37.22, 88.88))与 table1 中所有位置之间的距离的 MySQL 查询。

$lat = -37.22;
$long = 88.88;

SELECT id, latitude, longitude, name
        ((2 * 3960 *
          ATAN2(
            SQRT(
              POWER(SIN((RADIANS($lat - latitude))/2), 2) +
              COS(RADIANS(latitude)) *
              COS(RADIANS($long)) *
              POWER(SIN((RADIANS($long - longitude))/2), 2)
            ),
            SQRT(1-(
              POWER(SIN((RADIANS($lat - latitude))/2), 2) +
              COS(RADIANS(latitude)) *
              COS(RADIANS($long)) *
              POWER(SIN((RADIANS($long - longitude))/2), 2)
            ))
          )
        )) AS distance FROM table1 ORDER BY distance;

Table1
id name latitude longitude
1   foo1    -37.12   62.34
2   foo2    -47.12   72.34
3   foo3    -57.12   82.34

Table2
id name latitude longitude
1   bar1    -38.22   66.11
2   bar2    -48.22   76.11
3   bar3    -58.22   86.11

鉴于这也是一个大数据，我不确定从哪里开始。想法？

Answer 1

• 如果您想优化旅行或靠近位置，您应该使用空间功能 http://dev.mysql.com/doc/refman/5.7/en/spatial-extensions.html

• 但看起来您想要每次计算，所以是的，您将需要进行 100 亿次运算。

  • 我想时间在这里并不是真正的问题。因为一旦你拥有它，你就可以使用它。如果新位置到达，只需计算与该位置的距离。
  • 但是你必须优化。查询中成本最高的部分是计算 SIN() 和 COS()，因此为具有这些值的每一行创建附加字段。所以你只需要为每一行做一次而不是 100k 次
  • 最后运行一个循环，以便您以 block 的形式创建数据。

编辑:

阅读您的最后一条评论后。你需要一个空间索引。与您在数据库中搜索一个 ID 的方式相同，空间索引将优化您附近的搜索。

您还可以进行框搜索。您不是搜索整个宇宙，而是围绕您的点创建一个框并在该框内搜索。使用普通的浮点索引，你可以做这样的事情

  SELECT t1.name, t2.name,  mysql.Distancefunction(t1,t2) as distance
  from t1
  cross join t2
  WHERE t2.x between (t1.x - 0.001) and (t1.x + 0.001)   -- use x float index
    and t2.y between (t1.y - 0.001) and (t1.y + 0.001)   -- use y float index
    and mysql.Distancefunction(t1,t2) < 100 km           -- use spatial index

您可以使用 delta 0.001。如果得到太多结果，则使用 0.0001。如果你得到的结果很少，你只对那些没有 100 个邻居的位置执行第二步，将 0.01 设置为 0.01。