缓存特定于用户的邻近搜索

Question

形势和目标

假设一个用户搜索系统从用户自己的位置提供邻近搜索，该位置由十进制纬度/经度组合指定。例如，亚特兰大居民的位置将由33.756944,-84.390278表示，该用户进行的周边搜索应该会在其区域半径为10 mi、50 mi等范围内生成其他用户。

表值函数计算距离并相应地向用户提供相应的服务，按向开始搜索的用户的上升距离排序。它始终是一个实时查询，而且是一个非常困难和频繁的查询。现在，我们希望构建某种缓存来减少负载。

在解决问题的道路上

到目前为止，所有用户都是按照lat/long的整数部分分组的。这样做的目的是从网格方格创建所有用户的缓存文件，因此访问相关的缓存文件将非常容易。如果网格正方形包含的用户比缓存文件所包含的用户多，则将网格正方形划分为八块，以此类推。为了充分利用正方形及其缓存文件，需要考虑多个叠加方格。这种方法的一个缺点是，将高密度的城市地区和宽敞的农村地区划分为覆盖缓存文件的网格和营区可能不是最佳选择。

阅读之后，我偶然发现了一些主题，比如最近邻搜索、曼哈顿距离和树式空间分割技术，比如k-d树、四叉树或二进制空间分区。此外，Server还提供了自己的地理数据类型和函数(尽管我认为纯数学的FLOAT方法具有足够的性能)。当然，关键在于使以用户为中心的邻近搜索可以缓存。

问题！

我在这方面没有找到多少资料，但我肯定我不是第一个有这个计划的人。记住，这不是关于搜索，而是关于缓存。

• 我能放弃我的做法吗？

​

• 是否有办法将用户划分成大小相等的地理区域？
• 是否有最佳做法来存储空间用户信息，以便进行有效的邻近搜索？
• 你对上面提到的技术(四叉树等)有什么看法？如何将它们与缓存结合起来呢？
• 您知道成功缓存特定用户邻近搜索的示例吗？

Answer 1

我能放弃我的做法吗？

您可以调整您的appoach，因为正如您已经注意到的，一个四叉树使用这种技术。或者你使用地理空间扩展。这也适用于MySql。

是否有办法将用户划分成大小相等的地理分区？

当位置分布均匀或面积很小时，大小相同的简单固定网格是很好的。地理位置分布很难相等。通常采用地理空间结构。见下一个答复：

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

你对上面提到的技术(四叉树等)有什么看法？如何将它们与缓存结合起来呢？

汉南·萨米特( Hannan )做了一些工作，描述了四叉树和缓存。