匹配数百万人：k-d 树或局部敏感散列？
Matching millions of people: k-d tree or locality-sensitive hashing?
我正在寻找一种高性能算法来匹配大量按位置、性别和年龄的人 根据这个数据结构：
- 经度（表示人员位置）
- 纬度（表示人员位置）
- 性别（表示人物性别）
- 生日（表示此人的生日）
- LookingForGender（表示该人正在寻找的性别）
- LookingForMinAge（表示该人正在寻找的最低年龄）
- LookingForMaxAge（表示该人正在寻找的最大年龄）
- LookingForRadius（表示该人正在寻找的最大距离）
- 已处理（表示此人已经处理过哪些其他人）
对于任何人 P，算法应该 return 候选人 C 适用于：
- C 的性别必须相等 P.LookingForGender
- P 的性别必须相等 C.LookingForGender
- C 的生日必须在 P.LookingForMinAge 和 P.LookingForMaxAge 之间
- P 的生日必须在 C.LookingForMinAge 和 C.LookingForMaxAge 之间
- Lat/Long P 和 C 之间的距离必须小于或等于 P.LookingForRadius
- Lat/Long P 和 C 之间的距离必须小于或等于 C.LookingForRadius
- P的处理不能包含C
算法应该 return 前 100 个候选 C 按距离排序 (Lat/Long)。该算法应该针对搜索和更新进行优化，因为人们可能经常更改他们的位置。
我目前的想法是 k-d 树 可能比 locality-sensitive-hashing 更适合这些需求，我应该去到这个方向。
你对我有什么建议？我应该寻找什么？您认为有哪些风险？
谢谢！
更新:
- 我是否更愿意牺牲 space 复杂性以获得更好的时间复杂性？ 是的我更愿意牺牲 space 复杂性。但是，我更喜欢拥有一个我真正理解并可以维护的 O(log n) 解决方案，而不是一个我无法掌握的 O(1) 解决方案:)
- 数据适合主存吗？不适合。数据将分布在分布式文档数据库 (Azure Cosmos DB SQL API) 的不同节点上。
- 您想要精确结果还是近似结果？ 近似结果可以，但是 age/gender 应该精确过滤。
- 已将 "Processed" 添加到算法中，很抱歉错过了！
- 人们多久更改一次他们的位置？ 用户在启动应用程序并寻找候选人时都会更改他们的位置。因此，每日活跃用户每天会更改一次或多次位置。然而，位置变化可能很小，所以只有几公里。从 100 次应用下载中，15 位用户将每月使用该应用一次或多次，3 位用户将每天使用一次或多次。
Here 是 Microsoft 如何使用其空间索引的一些信息（'spatial' 是您要搜索的关键字）。
您要查找的查询是 k=100 的 k 最近邻查询（kNN 搜索）。
如果你想自己序列化索引，看看R+tree or R*trees, they are quite good for page based serialization. There are lots of open source example for these trees. Here是我自己在Java中的实现，不幸的是它不支持序列化。
关于其他索引：
- 我对LHS没有经验，所以不能多说。不过我知道一件事，因为它在内部是一个 HashMap，所以您需要特别注意使其可扩展到大量数据。这无疑增加了复杂性。另一个问题，我不确定 LSH 是否适用于 kNN 搜索，你必须查一下。
- KD 树非常简单，应该适合工作，但不利于序列化，并且会产生大量内存开销，除非您实现的版本可以在每个节点中包含多个条目。 KD 树在经常更新时也会退化，因此它们可能需要重新平衡。
- 否则我建议使用四叉树，例如qthypercube2。它们也非常简单，内存非常快，非常适合频繁更新，尤其是当条目只移动一小段距离时。
我正在寻找一种高性能算法来匹配大量按位置、性别和年龄的人 根据这个数据结构：
- 经度（表示人员位置）
- 纬度（表示人员位置）
- 性别（表示人物性别）
- 生日（表示此人的生日）
- LookingForGender（表示该人正在寻找的性别）
- LookingForMinAge（表示该人正在寻找的最低年龄）
- LookingForMaxAge（表示该人正在寻找的最大年龄）
- LookingForRadius（表示该人正在寻找的最大距离）
- 已处理（表示此人已经处理过哪些其他人）
对于任何人 P，算法应该 return 候选人 C 适用于：
- C 的性别必须相等 P.LookingForGender
- P 的性别必须相等 C.LookingForGender
- C 的生日必须在 P.LookingForMinAge 和 P.LookingForMaxAge 之间
- P 的生日必须在 C.LookingForMinAge 和 C.LookingForMaxAge 之间
- Lat/Long P 和 C 之间的距离必须小于或等于 P.LookingForRadius
- Lat/Long P 和 C 之间的距离必须小于或等于 C.LookingForRadius
- P的处理不能包含C
算法应该 return 前 100 个候选 C 按距离排序 (Lat/Long)。该算法应该针对搜索和更新进行优化，因为人们可能经常更改他们的位置。
我目前的想法是 k-d 树 可能比 locality-sensitive-hashing 更适合这些需求，我应该去到这个方向。
你对我有什么建议？我应该寻找什么？您认为有哪些风险？
谢谢！
更新:
- 我是否更愿意牺牲 space 复杂性以获得更好的时间复杂性？ 是的我更愿意牺牲 space 复杂性。但是，我更喜欢拥有一个我真正理解并可以维护的 O(log n) 解决方案，而不是一个我无法掌握的 O(1) 解决方案:)
- 数据适合主存吗？不适合。数据将分布在分布式文档数据库 (Azure Cosmos DB SQL API) 的不同节点上。
- 您想要精确结果还是近似结果？ 近似结果可以，但是 age/gender 应该精确过滤。
- 已将 "Processed" 添加到算法中，很抱歉错过了！
- 人们多久更改一次他们的位置？ 用户在启动应用程序并寻找候选人时都会更改他们的位置。因此，每日活跃用户每天会更改一次或多次位置。然而，位置变化可能很小，所以只有几公里。从 100 次应用下载中，15 位用户将每月使用该应用一次或多次，3 位用户将每天使用一次或多次。
Here 是 Microsoft 如何使用其空间索引的一些信息（'spatial' 是您要搜索的关键字）。
您要查找的查询是 k=100 的 k 最近邻查询（kNN 搜索）。
如果你想自己序列化索引，看看R+tree or R*trees, they are quite good for page based serialization. There are lots of open source example for these trees. Here是我自己在Java中的实现，不幸的是它不支持序列化。
关于其他索引：
- 我对LHS没有经验，所以不能多说。不过我知道一件事，因为它在内部是一个 HashMap，所以您需要特别注意使其可扩展到大量数据。这无疑增加了复杂性。另一个问题，我不确定 LSH 是否适用于 kNN 搜索，你必须查一下。
- KD 树非常简单，应该适合工作，但不利于序列化，并且会产生大量内存开销，除非您实现的版本可以在每个节点中包含多个条目。 KD 树在经常更新时也会退化，因此它们可能需要重新平衡。
- 否则我建议使用四叉树，例如qthypercube2。它们也非常简单，内存非常快，非常适合频繁更新，尤其是当条目只移动一小段距离时。