邻近搜索

Question

应用程序如何执行邻近搜索？ 例如，用户输入邮政编码，然后应用程序会按距离排序列出 20 英里内的所有企业。

我想用 PHP 和 MySQL 构建类似的东西。 这种做法正确吗？

1. 获取我感兴趣的位置的地址并将其存储在我的数据库中
2. 使用 Google 的地理编码服务对所有地址进行地理编码
3. 编写包含半正弦公式的数据库查询以进行邻近搜索和排序

可以吗？ 在步骤 3 中，我将计算每个查询的邻近度。 是否有一个列出每个企业与一些参考位置之间距离的 PROXIMITY 表会更好？

Answer 1

如果有足够的记录来保证速度，可以采用以下方法提前对它们建立索引。

定义一个边长约 20 英里的垃圾箱网格。 将垃圾箱编号与每个商店的记录一起存储。 在搜索时，计算与搜索点 20 英里半径相交的所有 bin 的数量。 然后检索任何这些箱中的所有商店，并像以前一样继续。

Answer 2

我们用它来完成数千个点。 如果您在 SQL 中执行此操作以在纬度和经度列上建立索引，这一点很重要。 我们尝试在 SQL 2008 中使用空间索引执行此操作，但我们确实没有看到我们预期的性能提升。 不过，如果您想在距离邮政编码一定距离内进行计算，您需要考虑是否要使用邮政编码质心或邮政编码的多边形表示。

Haversine forumla 是一个很好的起点。

我们在动态计算距离时没有遇到性能问题，对于某些我们提前知道点并且将有数百万条记录的应用程序，我们确实提前计算了它。

SELECT
        [DistanceRadius]=
        69.09 *
        DEGREES(
          ACOS(
            SIN( RADIANS(latitude) )*SIN( RADIANS(@ziplat) ) 
           +
            COS( RADIANS(latitude) )*COS( RADIANS(@ziplat) ) 
           *
            COS( RADIANS(longitude - (@ziplon)) )
          )
        )
        ,*
        FROM
            table

    ) sub
WHERE
    sub.DistanceRadius < @radius

Answer 3

我们为大约 1200 个地点执行此操作。 我只是即时使用半正矢公式，但根据您的应用程序，最好将其存储在 PHP 而不是 SQL 中。 （我们的实现是在 .net 中进行的，因此您的情况可能会有所不同）。

事实上，我们实现它的方式的最大缺点是，每个计算（直到最近）都必须在数据层上计算，这非常慢（当我说慢时，我真的指的是非瞬时的，它需要一秒钟左右的时间） ），但这是因为它必须根据提供的邮政编码计算所有 1200 个位置的距离。

根据您选择的路线，可以通过查看经度和纬度并删除预定义范围之外的经度和纬度来加快数字距离计算速度（例如，如果您正在查看 20 英里内的所有地址，则有一个您可以计算出所有地址必须位于 20 英里之外的经度范围。）如果需要，这可以加快您的查询速度。

我们实际上考虑过将所有可能的组合存储在我们的数据库中。 实际上，听起来它可能是一个大型数据存储，但它实际上并不在大范围内。 使用索引，它可以非常快，而且您不必担心算法优化等问题。我们决定反对它，因为我们在 C# 中有方程，它允许我们缓存在 C# 中进行所有计算所需的信息。业务层。 两者都可以正常工作，这只是您的偏好的问题。