1

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

该应用程序将在发布帖子（与帖子而非用户相关的纬度/经度）与数据库中的所有其他帖子时比较给定用户的纬度和经度，以返回给定距离内的所有帖子（比如说 5 英里）。

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

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

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

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

4

2 回答 2

1

如果可能的话， kd 树肯定是要走的路，但问题是您正在寻找“给定半径内的所有帖子”，其中可能有很多（100 到甚至 10000）。但是，您可能还需要考虑集群化帖子以避免高度集中的情况，以及其他一些好处，代价是半径（5 公里）是近似值。可以做到这一点的一种方法是使用最小圆的线性算法。

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) 左右运行。由于我没有编写某些类和函数的代码，因此它不会编译，但希望它能够传达这个想法。它假设点（帖子的纬度/经度）已经输入到 kd 树中。将 lat 和 long 从 degree-minutes-seconds.fractions 转换为 seconds.fractions 也可能不是一个坏主意。5 km 可能足够小，可以将坐标视为欧几里得点而不会引入太多误差，因为无论如何它都是聚类的近似值。

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

  • 5公里（全半径）
  • 2.5公里（半半径）
  • 几百英尺（按块排列）
于 2013-05-29T12:21:54.237 回答
0

看起来您可能希望将您的帖子存储在数据库中（该表将包含纬度、经度和帖子文本，并且您将索引纬度和经度），然后执行范围查询以检索适当的帖子（选择* 来自（纬度在 10 到 20 之间）和（经度在 40 到 50 之间）的帖子

如果所有数据都在内存中，那么范围树或kd 树就是您想要的数据结构，但是如果您正在谈论拥有数百万个帖子，那么您将需要使用数据库

SQLite是一个很好的免费轻量级数据库，你可以使用

于 2013-05-28T21:59:29.747 回答