mysql - 将值与潜在的大数据集进行比较

Question

我正在尝试找出最有效的方法来比较一个值与一个潜在的巨大数据集。问题是我不知道我在找什么。我对排序和搜索算法(此处非计算机专业)进行了一些研究，但我发现的大部分内容都会返回差异或对数据进行排序。虽然这可能会派上用场，但我正在尝试找出一种方法(或者如果我的想法正确的话)来最小化要计算的结果。

应用程序将在发布帖子时将给定用户的纬度和经度(纬度/经度绑定(bind)到帖子而不是用户)与数据库中的每个其他帖子进行比较，以返回给定距离(比如 5 英里)内的所有帖子。

我的应用程序的第一个版本(仍在开发中)只是将帖子与数据库中的所有其他帖子进行比较，以返回帖子之间的确切距离，并仅显示 5 英里半径内的帖子。它适用于数十个测试用户，但我意识到，当它上线时，有一天可能会有数百万用户/帖子，并且在整个数据库上用 PHP 执行这些计算并不理想。

我的一个想法是创建一个临时表，其中包含最近 72 小时的帖子，这些帖子的纬度为查询帖子的 +/- 5 分钟(~5 英里)，然后使用 PHP 计算实际距离这个较小的集合有效地消除了不相关的经度。我也可以探索在此查询中使用经度，但由于它的距离不同，因此不会非常准确。可能使用夸大的 5 度经度仍然会落在两极 5 英里以内，并且仍然会减少赤道数据集的大小(顺便说一句，我预计两极不会有很多用户)。

是这个声音还是有更好的方法？

有什么想法或建议的阅读 Material 吗？

Answer 1

A k-d tree如果可能的话肯定是要走的路，但问题是你正在寻找“给定半径内的所有帖子”，其中可能有很多(100s 甚至 10000s)。但是，您可能还想考虑集群帖子以避免高度集中的情况，以及其他一些好处，但代价是半径(5 公里)是近似值。可以做到这一点的一种方法是对 smallest-circle 使用线性算法。 .

def cluster_posts(points,cluster_radius):
    clusters = dict()
    for p in posts:
        # This inner part is also done whenever a new post is added
        clusters[p] = Cluster([p])
    points_set = set(points)
    While points_set:
        # This inner part is also done whenever a new post is added
        p = points_set.pop()
        q = kd_tree.nearest_neighbor(p)
        dist = distance(p,q)
        radius_p = clusters[p].smallest_circle_radius()
        radius_q = clusters[q].smallest_circle_radius()
        if radius_p + dist + radius_q < cluster_radius:
            new_cluster = clusters[p].merge(clusters[q])
            r = new_cluster.smallest_circle_radius()
            if r < cluster_radius:
                c = new_cluster.smallest_circle_center()
                points_set.remove(q)
                clusters.remove(q)
                clusters.remove(p)
                kd_tree.remove(p)
                kd_tree.remove(q)
                points_set.add(c)
                kd_tree.add(c)
                clusters[c] = new_cluster

以上尝试根据 cluster_radius 将两个集群合并为一个集群。有一些优化空间，但它应该在 O(N log N) 左右运行。由于我没有编写某些类和函数的代码，它不会编译，但希望它能理解这个想法。它假设点(帖子的纬度/经度)已经输入到 k-d 树中。将纬度和经度从 degrees-minutes-seconds.fractions 转换为 seconds.fractions 也可能不是一个坏主意。 5 km 可能足够小，可以将坐标视为欧几里得点而不会引入太多误差，因为它在聚类中是近似的。

查询只是通过 k-d 树找到用户位置 (query_radius - cluster_radius) 内的所有集群，并且至少包括最近的集群。您提供的数字将使查询半径为 5 公里。集群半径的几种可能性:

• 5 公里(全半径)
• 2.5 公里(半半径)
• 几百英尺(按 block 排列)