计算邮政编码...和用户之间的距离.

Question

这是一个挑战问题,而不是我迫切需要的东西,所以不要整天花在它们身上.

我在2000年左右建立了一个约会网站(早已不复存在),其中一个挑战是计算用户之间的距离,以便我们可以在半径X英里内展示您的"匹配".为了说明问题,给定以下数据库模式(粗略地):

USER TABLE UserId UserName ZipCode

ZIPCODE表ZipCode纬度经度

USER和ZIPCODE加入USER.ZipCode = ZIPCODE.ZipCode.

您将采取什么方法来回答以下问题:在给定用户的邮政编码的X英里范围内的其他用户使用的邮政编码.

我们使用了2000年人口普查数据,其中包含邮政编码表及其近似的经纬度.

我们还使用Haversine公式来计算球体上任意两点之间的距离......非常简单的数学.

至少对我们来说,这个问题是我们19岁的大学生,真正成为了如何有效地计算和/存储从所有成员到所有其他成员的距离.一种方法(我们使用的方法)是导入所有数据并计算从每个邮政编码到每个其他邮政编码的距离.然后,您将存储并索引结果.就像是:

SELECT  User.UserId
FROM    ZipCode AS MyZipCode
        INNER JOIN ZipDistance ON MyZipCode.ZipCode = ZipDistance.MyZipCode
        INNER JOIN ZipCode AS TheirZipCode ON ZipDistance.OtherZipCode = TheirZipCode.ZipCode
        INNER JOIN User AS User ON TheirZipCode.ZipCode = User.ZipCode
WHERE   ( MyZipCode.ZipCode = 75044 )
        AND ( ZipDistance.Distance < 50 )

当然,问题是ZipDistance表中会有很多行.它并非完全不可行,但它确实很大.此外,它需要对整个数据集进行完整的预处理,这也不是无法管理的,但不一定是可取的.

无论如何,我想知道你们中的一些大师会对这样的事情采取什么方法.此外,我认为这是程序员不时要解决的常见问题,特别是如果您考虑的算法类似的问题.我对一个彻底的解决方案很感兴趣,其中至少包括所有部分的HINTS,以便快速有效地完成这项工作.谢谢!

Answer 1

好的,对于初学者来说,你真的不需要在这里使用Haversine公式.对于距离较短的公式产生较大误差的较大距离,您的用户不关心匹配是加或减几英里,而对于更近的距离,误差非常小.地理距离维基百科文章中列出的公式更容易(计算).

由于邮政编码不是均匀分布的,因此任何将它们均匀分开的过程都会在它们紧密聚集的区域受到严重影响(DC附近的东海岸就是一个很好的例子).如果您想进行视觉比较,请查看http://benfry.com/zipdecode并将邮政编码前缀89与07进行比较.

处理索引此空间的更好方法是使用像Quadtree或R树这样的数据结构.此结构允许您对不均匀间隔的数据进行空间和距离搜索.

这是四叉树的样子:

要搜索它,可以使用其中较小单元格的索引向下钻取每个较大的单元格.维基百科更彻底地解释了它.

当然,由于这是一件相当普遍的事情,其他人已经为你做了很多困难.由于您尚未指定要使用的数据库,因此PostgreSQL扩展PostGIS将作为示例.PostGIS包括执行R树空间索引的功能,允许您进行有效的空间查询.

导入数据并构建空间索引后,查询距离就像是一个查询:

SELECT zip
FROM zipcode
WHERE
geom && expand(transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), 16093)
AND
distance(
   transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661),
   geom) < 16093

我会让你自己完成本教程的其余部分.

• http://unserializableone.blogspot.com/2007/02/using-postgis-to-find-points-of.html

以下是一些其他参考资料,可帮助您入门.

• http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_tut02
• http://www.manning.com/obe/PostGIS_MEAPCH01.pdf
• http://postgis.refractions.net/docs/ch04.html

Answer 2

我只需创建一个zip_code_distances表并预先计算美国所有42K邮编码之间的距离,这些邮政编码彼此之间的距离在20-25英里之内.

create table zip_code_distances
(
from_zip_code mediumint not null,
to_zip_code mediumint not null,
distance decimal(6,2) default 0.0,
primary key (from_zip_code, to_zip_code),
key (to_zip_code)
)
engine=innodb;

只包括彼此半径20-25英里范围内的邮政编码,可以减少您需要存储在距离表中的行数,从最大的17亿(42K ^ 2) - 42K到更易于管理的400万左右.

我从网上下载了一个zipcode数据文件,其中包含csv格式的所有美国官方邮政编码的经度和纬度:

"00601","Adjuntas","Adjuntas","Puerto Rico","PR","787","Atlantic", 18.166, -66.7236
"00602","Aguada","Aguada","Puerto Rico","PR","787","Atlantic", 18.383, -67.1866
...
"91210","Glendale","Los Angeles","California","CA","818","Pacific", 34.1419, -118.261
"91214","La Crescenta","Los Angeles","California","CA","818","Pacific", 34.2325, -118.246
"91221","Glendale","Los Angeles","California","CA","818","Pacific", 34.1653, -118.289
...

我写了一个快速而又脏的C#程序来读取文件并计算每个邮政编码之间的距离,但只输出半径25英里范围内的输出邮政编码:

sw = new StreamWriter(path);

foreach (ZipCode fromZip in zips){

    foreach (ZipCode toZip in zips)
    {
        if (toZip.ZipArea == fromZip.ZipArea) continue;

        double dist = ZipCode.GetDistance(fromZip, toZip);

        if (dist > 25) continue;

        string s = string.Format("{0}|{1}|{2}", fromZip.ZipArea, toZip.ZipArea, dist);
        sw.WriteLine(s);
    }
}

结果输出文件如下所示:

from_zip_code|to_zip_code|distance
...
00601|00606|16.7042215574185
00601|00611|9.70353520976393
00601|00612|21.0815707704904
00601|00613|21.1780461311929
00601|00614|20.101431539283
...
91210|90001|11.6815708119899
91210|90002|13.3915723402714
91210|90003|12.371251171873
91210|90004|5.26634939906721
91210|90005|6.56649623829871
...

然后我会使用加载数据infile将此距离数据加载到我的zip_code_distances表中,然后使用它来限制我的应用程序的搜索空间.

例如,如果您的用户的邮政编码是91210,并且他们想要找到距离他们不到10英里的人,那么您现在可以简单地执行以下操作:

select 
 p.*
from
 people p
inner join
(
 select 
  to_zip_code 
 from 
  zip_code_distances 
 where 
  from_zip_code = 91210 and distance <= 10
) search
on p.zip_code = search.to_zip_code
where
 p.gender = 'F'....

希望这可以帮助

编辑:将半径扩展到100英里,将邮政编码距离增加到3250万行.

快速性能检查邮政编码91210运行时0.009秒.

select count(*) from zip_code_distances
count(*)
========
32589820

select 
 to_zip_code 
from 
 zip_code_distances 
where 
 from_zip_code = 91210 and distance <= 10;

0:00:00.009: Query OK

Answer 3

您可以通过假设一个方框而不是圆形半径来简化计算.然后在搜索时,您只需计算给定点+"半径"的纬度/经度的下限/上限,只要您在纬度/经度列上有索引,就可以很容易地将所有记录都放在盒子内.