3

我发现了各种问题的解决方案与此问题类似，但到目前为止还没有什么钱。非常感谢任何帮助。

我有一个 mysql (v.5.6.10) 数据库，其中有一个名为 POSTS 的表，它在地图上存储数百万行纬度/经度的兴趣点。每个点都被归类为几种不同类型中的一种。每行的结构如下id, type, coords：

  • id+unsigned bigint主键。这对于插入的每个新行都会自动递增。
  • type用于unsigned tinyint编码兴趣点的类型。
  • coordsPOINT表示兴趣点的纬度/经度的 mysql 地理空间数据类型。

“坐标”上有一个空间索引。

我需要找到一种有效的方法来查询表格并返回特定纬度/经度位置（“位置”）的半径（“ R ”）内最近插入的 X 个点。数据库是非常动态的，因此请假设每次查询表时数据都完全不同。

如果 X 是无限的，那么问题是微不足道的。我只需要执行如下查询：

SELECT id, type, AsText(coords) FROM POSTS WHERE MBRContains(GeomFromText(BoundingBox, Position))

其中 'BoundingBox' 是一个 mysql POLYGON 数据类型，它完美地包围了一个从位置开始的半径为 R 的圆。使用边界框当然不是一个完美的解决方案，但这对于我试图解决的特定问题并不重要。我可以使用“ORDER BY ID DESC”对结果进行排序，以首先检索和处理最近插入的点。

如果 X 小于无限，那么我只需要将上面的内容修改为：

SELECT id, type, AsText(coords) FROM POSTS WHERE MBRContains(GeomFromText(BoundingBox, Position)) ORDER BY id DESC LIMIT X

我要解决的问题是，当该区域中的点高度聚集时（例如，在地图搜索区域的城市内），如何从地图上的给定区域获得一组具有代表性的结果。例如：

在此处输入图像描述

在上面的示例中，我站在 X 处并在黑框边界框中搜索最近插入的 5 个黑色类型点。如果这些点都插入到右下角的集群中（假设集群是伦敦），那么我的结果集将不包括搜索区域右上角附近的黑点。这对我的应用程序来说是个问题，因为我不希望用户认为在点聚集的任何区域之外没有兴趣点。

我已经考虑了一些潜在的解决方案，但是当行数很大（数百万）时，我找不到有效的解决方案。到目前为止我尝试过的方法包括：

  1. 将搜索区域划分为 S 个正方形（即，将其变成网格）并在每个正方形内搜索最多 x/S 个点 - 即，对网格中的每个正方形执行单独的 mysql 查询。这适用于少量行，但当行数很大时效率低下，因为您需要将区域划分为大量正方形以使该方法有效工作。只有少数方格，您不能保证每个方格都不会包含人口密集的集群。大量的正方形意味着大量的 mysql 搜索，这会导致事情发生。

  2. 向表中的每一行添加一列，用于存储每个点到最近邻居的距离。将点插入表中时，会计算给定点的最近邻距离。使用这种结构，我可以按最近邻距离列对搜索结果进行排序，以便最后返回聚类中的任何点。此解决方案仅在我搜索搜索区域内的所有点时才有效。例如，考虑上图中的情况。如果我想查找最近插入的 5 个green类型的点，则为每个点记录的最近邻距离将不正确。为每个查询重新计算这些距离的成本太高了，即使使用 KD 树这样的高效算法也是如此。

事实上，当行数变大时，我看不到任何需要对表行中的数据进行预处理（或者换句话说，“接触”相关搜索区域数据集中的每个点）的方法是可行的。我已经考虑过 k-means / DBSCAN 等算法，但鉴于上述用例，我找不到任何能以足够效率工作的方法。

有珍珠吗？我的直觉告诉我这可以解决，但到目前为止我很难过。

4

1 回答 1

1

在这种情况下，后处理似乎更有效。获取给定类型的最后 X 个点。查找是否存在一些聚类，例如：相对于您的视点距离而言，太多点太靠近。删除其中最旧的（或非常接近的 - 可能是您的数据引用了相同的 POI）。多少 - 取决于你。获取下一个 X 点并查看其中是否有一些不在集群中，或者您可以根据距离和最近为每个点计算一个值，并根据该值丢弃点。

于 2013-06-10T22:55:16.977 回答