计算邮政编码与用户之间的距离。

Question

这不是我紧急需要的问题，更是一个挑战性的问题，所以不要整日花在那些家伙上。

我在2000年左右建立了一个约会网站（早已消失），其中一项挑战是计算用户之间的距离，以便我们可以在X英里半径内显示您的“匹配项”。仅给出以下数据库架构，仅说明问题：

用户表UserId用户名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表中将包含很多行。这不是完全不可行的，但确实很大。另外，它还需要对整个数据集进行完整的准备工作，这也不是无法管理的，但不一定是令人满意的。

无论如何，我想知道你们中的某些大师会采取什么样的方法。另外，我认为这是程序员经常要解决的常见问题，尤其是当您考虑算法上相似的问题时。我对一个彻底的解决方案感兴趣，该解决方案在所有方面都至少包含提示，以确保快速有效地完成此任务。谢谢！

Answer 1

您可以将空间划分成大小大致相等的区域-例如，将地球近似为布基球或二十面体。如果更容易的话，这些区域甚至可以重叠一点（例如，使其成为圆形）。记录每个邮政编码所在的区域。然后，您可以预先计算每个区域对之间的最大距离，该区域与计算所有邮政编码对具有相同的O（n ^ 2）问题，但n较小。现在，对于任何给定的邮政编码，您都可以获得绝对在给定范围内的区域列表以及跨边界的区域列表。对于前者，只需获取所有邮政编码。对于后者，请深入每个边界区域并针对各个邮政编码进行计算。这肯定在数学上更加复杂，尤其是必须选择区域的数量以在表的大小和动态计算所花费的时间之间取得良好的平衡，但是它可以将预先计算的表的大小减小余量。