匹配数百万人：kd 树还是局部敏感哈希？

Question

我正在寻找一种高性能算法，根据以下数据结构按位置、性别和年龄匹配大量人员：

• 经度（表示该人的位置）
• 纬度（表示人的位置）
• 性别（表示人的性别）
• 出生日期（表示该人的出生日期）
• LookForGender（表示该人正在寻找的性别）
• LookForMinAge（表示该人正在寻找的最低年龄）
• LookForMaxAge（表示该人正在寻找的最大年龄）
• LookForRadius（表示该人正在寻找的最大距离）
• 已处理（表示此人已经处理了哪些其他人）

对于任何人 P，算法应返回适用的候选人 C：

• C 的性别必须相同 P.LookingForGender
• P 的性别必须相同 C.LookingForGender
• C 的出生日期必须介于 P.LookingForMinAge 和 P.LookingForMaxAge 之间
• P 的出生日期必须介于 C.LookingForMinAge 和 C.LookingForMaxAge 之间
• P 和 C 之间的纬度/经度距离必须小于或等于 P.LookingForRadius
• P 和 C 之间的纬度/经度距离必须小于或等于 C.LookingForRadius
• 加工后的P不得含有C

该算法应按距离（纬度/经度）顺序返回前 100 个候选 C。该算法应该针对搜索和更新进行优化，因为人们可能经常改变他们的位置。

我目前的想法是，kd 树可能比局部敏感哈希更适合这些需求，我应该朝这个方向发展。

您对我有什么建议？我应该寻找什么？您看到什么风险？

谢谢！

更新：

• 我是否愿意牺牲空间复杂度来获得更好的时间复杂度？是的，我更愿意牺牲空间复杂性。然而，我更喜欢有一个我真正理解并且可以维护的 O(log n) 解决方案，而不是一个我无法掌握的 O(1) 解决方案:)
• 数据是否适合主存？不，不是的。数据将分布在分布式文档数据库（Azure Cosmos DB SQL API）的不同节点上。
• 您想要精确的结果还是近似的结果？近似结果是可以的，但是应该精确过滤年龄/性别。
• 在算法中添加了“已处理”，抱歉错过了！
• 人们多久改变一次位置？用户每当启动应用程序并寻找候选人时都会改变他们的位置。因此，每日活跃用户每天会更改一次或多次位置。然而，位置变化可能很小，只有几公里。在 100 次应用下载中，15 位用户每月会使用该应用一次或多次，3 位用户每天会使用一次或多次。

Answer 1

以下是 Microsoft 提供的有关如何使用其空间索引的一些信息（“空间”是您要搜索的关键字）。

您正在查找的查询是 k-近邻查询（kNN 搜索），k=100。

如果您想自己序列化索引，请查看R+tree或R*trees，它们非常适合基于页面的序列化。这些树有很多开源示例。这是我自己用Java实现的，不幸的是它不支持序列化。

关于其他指标：

• 我没有使用LHS的经验，所以不能说太多。但我知道一件事，因为它内部是一个 HashMap，所以您需要特别小心，使其可扩展以处理大量数据。这无疑会增加复杂性。另一个问题，我不确定 LSH 是否适合 kNN 搜索，你必须查一下。
• KD 树非常简单，应该能够胜任工作，但不利于序列化，并且可能会产生大量内存开销，除非您实现一个在每个节点中可以有多个条目的版本。KD 树在经常更新时也会退化，因此它们可能需要重新平衡。
• 否则我会建议四叉树，例如qthypercube2。它们也非常简单，内存速度非常快，非常适合频繁更新，特别是当条目仅移动一小段距离时。