mysql - 使用mysql在 map 上搜索点时处理聚类

Question

我已经找到了各种问题的解决方案类似于这个问题，但没有完全在钱到目前为止。非常感谢你的帮助。
我有一个mysql（v.5.6.10）数据库，其中有一个名为POSTS的表，在地图上存储数百万行lat/long兴趣点。每一点都被归类为几种不同类型中的一种。每一行的结构如下：
id, type, coords主键。对于插入的每一新行，此值将自动递增。
id用于编码感兴趣点类型的unsigned bigint。
type一个mysql地理空间数据类型，表示关注点的纬度/经度。
“coords”上有一个空间索引。
我需要找到一种有效的方法来查询表，并返回在特定纬度/经度位置（“位置”）的半径（“R”）内最近插入的点的X。数据库是非常动态的，所以请假设每次查询表时数据都是完全不同的。
如果X是无穷大的，问题就很简单了。我只需要执行如下查询：

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

其中“BoundingBox”是一个mysql多边形数据类型，它从位置完美地包围了一个半径为R的圆。当然，使用边界框并不是一个完美的解决方案，但这对于我试图解决的特定问题并不重要。我可以使用“orderbyiddesc”对结果进行排序，以便首先检索和处理最近插入的点。
如果X小于无穷大，那么我只需要将上面的修改为：

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

我试图解决的问题是，当地图上的某个区域中的点严重聚集时（例如，在地图搜索区域中的城市内），如何从该区域中获得一组具有良好代表性的结果。例如：
在上面的示例中，我站在X处，在黑框边界框中搜索最近插入的5个黑色类型的点。如果这些点都被插入到右下角的集群中（假设集群是伦敦），那么我的结果集将不包括搜索区域右上角附近的黑点。这是我的应用程序的一个问题，因为我不希望给用户留下这样的印象：在点聚集的任何区域之外都没有兴趣点。
我已经考虑了一些可能的解决方案，但是我找不到一个在行数巨大（10百万）时有效工作的解决方案。到目前为止，我尝试的方法包括：
将搜索区域划分为S个正方形（即将其转换为网格），并在每个正方形内搜索最多x/S个点，即对网格中的每个正方形执行单独的mysql查询。对于少量的行来说，这是可行的，但是当行的数量很大时，这会变得效率低下，因为您需要将区域划分为大量的正方形以使方法有效地工作。只有少量的方块，不能保证每个方块都不包含人口稠密的簇。大量的方块意味着大量的mysql搜索，这会导致事情变得一团糟。
向表中的每一行添加一列，该列存储每个点到最近邻居的距离。当点插入到表中时，将计算给定点的最近邻距离。使用这种结构，我可以按最近邻距离列对搜索结果进行排序，以便最后返回集群中的任何点。只有在搜索区域内的所有点时，此解决方案才有效。例如，考虑上图中的情况。如果我想找到最近插入的5个绿色点，则为每个点记录的最近邻距离将不正确。即使使用像KD树这样的高效算法，为每个查询重新计算这些距离也将非常昂贵。
事实上，我看不出有任何方法需要在表行中预处理数据（或者换句话说，在相关搜索区域数据集中“接触”每个点）以便在行数变大时可行。我已经考虑过像k-means/DBSCAN等算法，而且在上面解释的用例中，我找不到任何能够足够高效地工作的算法。
有珍珠吗？我的直觉告诉我这是可以解决的，但到目前为止我还很困惑。

Answer 1

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