0

我有一个数据集，目前只存储在一个 JSON 文件中，其中包含大约 40k 个不同的地理位置。它看起来像这样：

[
    {"title": "Place 1", "loc": {"x": "00.000", "y": "00.00000"}},
    {"title": "Place 2", "loc": {"x": "00.000", "y": "00.00000"}},

]

一个地方loc只是它的坐标。

我希望能够对此数据运行查询，因此，对于任何给定的用户输入loc，我都可以获得n最近的地点。

或者换句话说，我想编写一些函数f以便它工作：

def f(loc, n): ...
f({"x": "5", "y": "5"}, 3) #=> [{"title": "Place 1", "distance": 7.073}, {"title": "Place 2": "distance": 7.073}, {"title": "Place 3", "distance": 7.073}]

如果有一个地方 1、2 和 3 都在{x: 0, y: 0}。

我不知道解决此类问题的标准方法是什么。使用带有预先计算距离索引的 SQL DB 是行不通的，因为所提供的距离loc是任意的。遍历整个数据库并计算所有内容的距离太低效，也太慢了。（我需要 < 30 毫秒的响应时间。）

唯一有意义的解决方案是以某种方式制作靠近位置的“桶”（在r彼此之间），然后计算用户给定的 loc 和桶的 loc 之间的距离以首先缩小选项。但是我觉得自己创建这样的解决方案就像根本不使用数据库一样；必须有更有效/行业标准的方法。有吗？

4

3 回答 3

0

You can use a database with a point data type and a spatial index like MySQL. You can also use a quadkey or a quadtree. It's subdivide the plane and reduce the dimension. You can download my PHP class Hilbert-curve@ phpclasses.org. It's uses a quadkey and can help to organize locations in buckets and build a proximity searching. A quadkey can reduce overlapping searches because of a special database.

于 2013-09-22T06:07:41.473 回答
0

Oracle 提供空间数据功能。它有一个内置的最近邻函数SDO_NN可以为您完成这项工作。只有无意中听到的会将所有数据放入数据库中，其余的将由 oracle db 处理。

于 2013-09-22T06:17:48.323 回答
0

这是最近邻问题（更正式地称为k-最近邻）的广义形式。你是对的，有意义的解决方案使用存储桶。您可以将存储桶存储在允许您利用 SQL 的数据库中，只需过滤掉不在适当存储桶中的所有点。根据您的数据库，这实际上可能已经为您实现，这将是您建议的“行业标准”方法。

否则，自己编写它是非常有效的，并且可以在不偏离数据库太多的情况下完成。

于 2013-09-22T02:32:04.943 回答