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

Question

我正在寻找一种高效的算法，根据以下数据结构，通过“位置”、“性别”和“年龄”来匹配大量人员：

- 经度（表示个人位置） - 纬度（表示个人位置） - 性别（表示个人性别） - 出生日期（表示个人出生日期） - 寻找的性别（表示个人寻找的性别） - 寻找的最小年龄（表示个人寻找的最小年龄） - 寻找的最大年龄（表示个人寻找的最大年龄） - 寻找的半径（表示个人寻找的最大距离） - 已处理（表示此人已处理的其他人）

对于任何人P，该算法应返回符合以下条件的候选人C：

- C的性别必须等于P的LookingForGender - P的性别必须等于C的LookingForGender - C的出生日期必须在P的LookingForMinAge和LookingForMaxAge之间 - P的出生日期必须在C的LookingForMinAge和LookingForMaxAge之间 - P和C之间的纬度/经度距离必须小于或等于P的LookingForRadius - P和C之间的纬度/经度距离必须小于或等于C的LookingForRadius - P的Processed中不得包含C

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

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

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

谢谢！

更新：

• 我是否愿意为更好的时间复杂度而牺牲空间复杂度？是的，我愿意为更好的时间复杂度而牺牲空间复杂度。但是，我更喜欢一个 O(log n) 的解决方案，它让我可以理解和维护，而不是一个我无法理解的 O(1) 解决方案 :)
• 数据是否适合放入主存储器中？不适合。数据将分布在分布式文档数据库（Azure Cosmos DB SQL API）的不同节点上。
• 你想要精确的结果还是近似的结果？近似的结果可以接受，但应该精确筛选出年龄/性别。
• 添加了“已处理”到算法中，之前漏掉了！
• 人们多久会更改他们的位置？用户每次打开应用程序并寻找候选人时都会更改其位置。因此，每天活跃用户将一天内更改自己的位置一次或多次。然而，位置变化可能只是一些公里。从100个应用程序下载中，有15个用户将在一个月内使用该应用程序一次或多次，3个用户将每天使用一次或多次。

- driAn

---

你更愿意为了更好的时间复杂度而牺牲空间复杂度吗？还是相反？ - smeso

更多问题：数据是否适合主内存？您想要精确的结果还是近似的结果（例如，不是最接近的100个候选人，而是150个最接近的候选人中的100个）可以吗？ - SaiBot

简短回答：使用具有GIS功能的数据库。 - wildplasser

@Jim Mischel 不幸的是，我没有关于这个问题的写作。只是根据我的经验：研究方面，我还没有找到一个有说服力的解决方案的论文。主要问题在于空间索引非常高效，但不易并行化（就像二分查找一样）。别误会，你可以将空间索引分布在n台机器上，并且比朴素方法更快。但你不能期望获得n倍的改进。在大多数应用程序中（如OP），你需要做更多的空间搜索，这有利于大数据框架。 - SaiBot

@JimMischel 感谢您的数学知识;) 在我的评论的第二句话中，我并不是指RAM，而是指具有二级存储器的机器（即SSD可以极大地改善HDD上的空间索引）。 - SaiBot

Answer 1

这里有微软提供的关于如何使用他们的空间索引（“spatial”是您想要搜索的关键字）的一些信息。

您要查找的查询是k最近邻查询（kNN Search），其中k = 100。

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

关于其他索引：

• 我没有使用LHS的经验，所以对它不能做出太多评价。但有一件事我知道，因为它内部是一个HashMap，你需要特别注意使它能够承载大量数据以实现可伸缩性。这肯定会增加复杂度。另一个问题是，我不确定LSH是否适合kNN搜索，你需要查阅相关资料。
• KD树非常简单且应该能胜任此任务，但在序列化方面表现较差，并且可能存在较大的内存开销，除非你实现一个可以在每个节点中具有多个条目的版本。KD树也可能在经常更新时退化，因此可能需要重新平衡。
• 否则，我建议使用四叉树，例如qthypercube2。它们也相当简单，在内存中非常快速，并且非常适合频繁更新，尤其是如果条目只移动了很小的距离。

- TilmannZ