0

形势与目标

想象一个用户搜索系统,它提供从用户自己的位置进行的邻近搜索,该位置由十进制纬度/经度组合指定。例如,亚特兰大居民的位置将由 表示,33.756944,-84.390278并且该用户的周界搜索应该从半径 10 英里、50 英里等产生他所在区域内的其他用户。

表值函数计算距离并相应地为用户提供,按与开始搜索的用户的距离升序排列。它总是一个实时查询,而且是一个艰难而频繁的查询。现在,我们想要构建某种缓存来减少负载。

在寻求解决方案的路上

到目前为止,所有用户都按其纬度/经度的整数部分分组。这个想法是用网格方块中的所有用户创建缓存文件,因此访问相关的缓存文件会很容易。如果一个方格包含的用户多于缓存文件应包含的用户数,则该方格将被四等分或进一步分成八块,依此类推。为了充分利用正方形及其缓存文件,可以考虑多个重叠正方形。这种方法的一个缺陷是,将高密度大都市地区和宽敞的乡村地区划分为网格和四等分覆盖缓存文件可能不是最佳的。

继续阅读,我偶然发现了最近邻搜索、曼哈顿距离和树式空间划分技术(如 kd 树、四叉树或二进制空间划分)等主题。此外,SQL Server 提供了自己的地理数据类型和函数(尽管我猜纯数学FLOAT方式具有足够的性能)。当然,关键是让以用户为中心的邻近搜索可缓存。

问题!

我在这方面没有找到太多资源,但我确信我不是第一个有这个计划的人。请记住,这不是关于搜索,而是关于缓存。

  • 我可以放弃我的方法吗?;-)
  • 有没有办法将用户有利地划分为大小相等的地理区域?
  • 是否有存储空间用户信息以实现高效邻近搜索的最佳实践?
  • 您如何看待上述技术(四叉树等)以及如何将它们与缓存配对?
  • 您知道成功缓存特定于用户的邻近搜索的示例吗?
4

1 回答 1

1

我可以放弃我的方法吗?

您可以调整您的方法,因为正如您已经指出的,四叉树使用这种技术。或者您使用地理空间扩展。这也适用于 MySql。

有没有办法将用户有利地划分为大小相等的地理分区

当位置均匀分布或区域非常小时,一个简单的相同大小的固定网格就可以了。地理位置几乎分布不均。通常使用地理空间结构。看下一个答案:

是否存在存储空间用户信息以实现高效邻近搜索四叉树、k-dTree 或 R-Tree 的最佳实践。

您如何看待上述技术(四叉树等)以及如何将它们与缓存配对?

Hannan Samet 的一些工作描述了四叉树和缓存。

于 2013-06-14T13:21:00.470 回答