高效计算距离

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 英里内所有地点的计数。

问题是这会产生一个我的 SAS 无法处理的大表(900M 行)。

如何更有效地处理此问题？

Answer 1

减少对选择空间。

使用 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 */

这一切都假定了一个球形地球的信念。

Answer 2

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

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

(这需要 1：05 才能在我的笔记本电脑上有 30k 条记录的测试台上运行)

Answer 3

当您将表与自身联接时，您需要尝试完成一些有助于提高性能的事情：

• 使生成的数据集尽可能小
• 尽可能轻松地比较两个条目

看到问题了吗？ 您根本没有缩减数据集，而是执行了 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英里。 但是，您大大减少了需要执行的距离检查总数以及要对其执行操作的数据集。

之后，您应该在桌子上玩弄索引。 我的猜测是，您需要一个同时包含 Lat 和 Long 列的索引，这样您只需要一个索引即可执行该操作。

这应该有望让您到达您需要去的地方 - 我的猜测是，这就是您需要的所有优化。 但是，如果您需要使事情更快，则可以细分数据。 毕竟，该国西部的任何东西都不会在东部30英里范围内。 (不过，您需要考虑处于分歧边缘的城市。