有效计算距离

Question

我正在尝试查找 30 英里半径内每个地点的地点数量。例如，对于伊利诺伊州斯普林菲尔德，30 英里半径范围内有多少个城镇？

对于每个地方，我都有名称、纬度和经度，n = 30k。

如果数据集较小，这个问题会相对简单：

PROC SQL; 
    CREATE TABLE Distance_Table_1 AS 
        SELECT 
             MASTER.PlaceID AS PlaceID 
            ,Master.INTPTLAT AS LAT1
            ,Master.INTPTLONG AS LONG1
            ,Match.INTPTLAT AS LAT2
            ,Match.INTPTLONG AS LONG2
            ,GEODIST(Master.INTPTLAT, Master.INTPTLONG, Match.INTPTLAT,Match.INTPTLONG,'M') AS DISTANCE
        FROM MASTER_TABLE_CLEANED_ MASTER
        CROSS JOIN MASTER_TABLE_CLEANED_ AS MATCH
        ; 
QUIT;

然后我会为每个地方创建 30 英里范围内所有地方的计数。

问题是这会产生一个大得离谱的 table，我的 SAS 无法处理（900M 行）。

我怎样才能更有效地处理这个问题？

Answer 1

Gord 在评论中提到了这一点，只需在查询中添加一个过滤器，就可以去掉重复计算和计算与自己的距离。

PROC SQL; 
    CREATE TABLE Distance_Table_1 AS 
        SELECT 
             MASTER.PlaceID AS PlaceID 
            ,Master.INTPTLAT AS LAT1
            ,Master.INTPTLONG AS LONG1
            ,Match.INTPTLAT AS LAT2
            ,Match.INTPTLONG AS LONG2
            ,GEODIST(Master.INTPTLAT, Master.INTPTLONG, Match.INTPTLAT,Match.INTPTLONG,'M') AS DISTANCE
        FROM MASTER_TABLE_CLEANED_ MASTER
        CROSS JOIN MASTER_TABLE_CLEANED_ AS MATCH
        where match.PlaceID < master.PlaceID
        ; 
QUIT;

添加 where 子句：

where match.PlaceID < master.PlaceID

这将 return 449,985,000 条记录 ( (n^2-n)/2 )。希望它足够小，可以处理。

（这需要 1:05 到运行测试 table 我的笔记本电脑上有 30k 条记录）

Answer 2

当您加入 table 对抗自身时，您想尝试完成一些有助于提高性能的事情：

使生成的数据集尽可能小
尽可能简单地比较两个条目

看到问题了吗？您根本没有减少数据集，而是执行了 30k x 30k 次复杂的距离计算。与其尽可能快地消除尽可能多的记录，不如继续并暴力破解所有内容。

马上，提高性能的一种简单方法是执行以下操作：

select *
from cities c1
JOIN cities c2
on c1.ID < c2.ID
and c2.Lat between c1.Lat - 30 miles and c1.Lat + 30 miles
and c2.Long between c1.Long - 30 miles and c1.Long + 30 miles

...这将为您提供多的可能候选人名单。这不是最终答案——您将拥有位于另一个城市以北 25 英里和以西 25 英里的城市，总距离超过 30 英里。但是您大大减少了需要执行的距离检查总数，以及您正在执行操作的数据集。

之后，您应该在 table 上使用索引。我的猜测是您需要一个包含 Lat 和 Long 列的索引，这样您只需要一个索引即可执行操作。

这应该能带您到达您需要去的地方 - 我猜这就是您需要的所有优化。但如果你需要让事情变得更快，你可以细分数据。毕竟，该国西部的任何地方都不会在东部 30 英里以内。（不过，您需要考虑分水岭边缘的城市。）

Answer 3

减少配对选择space。

使用 DomPazz PlaceId 来限制要评估的对集，并使用网格方法要求每个纬度和经度值有 30 英里的接近度近似值。

成对选择标准为

where
  fromCity.placeId < toCity.placeId
  and abs(fromCity.lat - toCity.lat) < &precomputed_Max30mileLatRange
  and abd(fromCity.lont - toCity.long) < &precomputed_Max30mileLongRange

使用 http://longitudestore.com/how-big-is-one-gps-degree.html 处的信息：

纬度标度名义上是线性的，纬度为“1 度”。是 ~ 69 英里
经度尺度不同，需要的度数更长。您离北极或南极越近，距离为 30 英里。在北纬 80 度，经度 1 度大约是 12 英里

因此，假设您的地图数据中没有纬度超过 80 的地方，以下选择标准将大大减少需要计算地理距离的配对。

where
  fromCity.placeId < toCity.placeId
  and abs(fromCity.lat - toCity.lat) < 0.5 /* ~35 miles */
  and abs(fromCity.lont - toCity.long) < 2.5 /* anywhere from ~36 miles (at 80 lat to ~175mi at equator */

这一切都假定地球是球形的。

有效计算距离

Efficiently computing distance

sql

sas

proc-sql

proc