计算大型数据集的地理点之间的距离

Question

我正在构建一个在线 Symfony 应用程序，作为开发过程的一部分，我的任务是根据与登录用户的距离对大量数据库记录进行排序；表示用户可以随意扩大搜索半径，最大可达整个世界。

我随时可以访问登录用户的 GPS 坐标，并且在数据库中 table 我保存了各个兴趣点的纬度和经度。

目前，POIs 中只有 400 条记录 table，但由于每次访问它都必须提取大量数据，查询时间已经超过一秒。将 400 个三角函数添加到这样的工作负载将很快使这样的执行时间超出可接受范围。

因此我需要一种既快速又准确的方法来计算这样的距离；

我读过多篇建议使用 Haversine 公式的文章，但我发现它对我的需求来说太慢了，甚至像 this 这样的详尽文章也没有任何帮助；

考虑到我很快就会达到成千上万的 POI，同时有来自世界各地的数千名用户同时登录，我该如何处理（并有望解决）这样的问题？

我正在使用 PHP 7.0、Symfony 3.2 和 Doctrine； pdo 连接到 Mysql 服务器，使用 innoDB 作为数据库引擎
我的客户更看重准确性而非速度，但无法忍受超过 5 秒的等待
查询结果是分页的，不能委托给客户端排序
数据库和php服务器共享同一个（糟糕的）资源池，而且这个资源池要与其他应用程序共享

附带说明，某些 POI 可能会在特定日期后过期

Answer 1

你要我加，我就加。

您确定性能下降来自 Haversine 吗？我们已经在我的工作中成功地在生产中使用了这个公式的 PHP 实施大约 2 年，并且我们进行了大量的搜索（高峰时间每分钟大约 150k）。

我无法详细介绍我的工作，但我可以说我们结合使用了 sphinx、mongoDB、mysql 和 RabbitMq。

在任何情况下，sphinx 和 mysql 都存在距离计算执行不佳的问题，在 100 英里的距离处损失了大约 2 英里的精度。（这就是我们使用它的原因）

您可以做的一件事是对运行 Haversine 公式所花费的时间进行基准测试，当您遇到性能问题时，良好的基准测试是第一步。

虽然我不是 symphony 用户，但我确实有一个 class 我专门为这个东西制作的。它是我在业余时间构建的更大框架 (Evolution) 的一部分。您可以在此处获取 class

https://github.com/ArtisticPhoenix/Evo/blob/master/Evo/Benchmark.php

使用起来非常简单

$mark = Benchmark::getInstance()->mark();

... code to time ...

echo Benchmark::getInstance()->format($mark);

并且会输出类似

的内容

10 milliseconds
5 minutes 3 milliseconds
ect..

它的设计让您可以使用多个 marks

$mark = Benchmark::getInstance()->mark();

... code to time ...

$mark1 = Benchmark::getInstance()->mark();

 ... more code to time ...

echo "TotalTime: ".Benchmark::getInstance()->format($mark);
echo "MethodTime: ".Benchmark::getInstance()->format($mark1);

etc..

当你调用 mark() 和 returns 标识符时，它基本上只记录 microtime(true) （true 是浮点数）然后如果你调用 mark($mark) 和标识符，它将从当前 microtime(true) 中减去它。调用 format($mark) 只会使其更 "Human" 可读。

希望对您有所帮助！

计算大型数据集的地理点之间的距离

Calculating distance between Geo points for large datasets

php

mysql

symfony

geographic-distance