21

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

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

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

这个可以吗？在第 3 步中，我将计算每个查询的接近度。有一个 PROXIMITY 表来列出每个企业和几个参考位置之间的距离会更好吗？

4

3 回答 3

13

如果有足够的记录对速度很重要，这里有一种方法可以提前对它们进行索引。

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

于 2008-11-03T23:38:23.043 回答
13

我们用它来做成千上万的点。如果您在 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
于 2008-11-04T00:18:12.573 回答
2

我们为大约 1200 个地点执行此操作。我会即时使用 Haversine 公式，尽管取决于您的应用程序，将其存储在 PHP 而不是 SQL 中可能会更好。（我们的实现是在 .net 中，因此您的里程可能会有所不同）。

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

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

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

于 2008-11-04T00:03:28.720 回答