5

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

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

对于任何人 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 树可能比locality-sensitive-hashing更适合这些需求，我应该朝这个方向发展。

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

谢谢！

更新：

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

1 回答 1

1

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

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

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

关于其他指标：

  • 我对 LHS 没有经验，所以不能说太多。不过我知道的一件事是，由于它在内部是一个 HashMap，因此您需要特别注意使其可用于大量数据的可伸缩性。这肯定会增加复杂性。另一个问题，我不确定 LSH 是否适合 kNN 搜索，你必须查一下。
  • KD-trees 非常简单，应该适合这项工作，但不利于序列化，并且可能会产生大量内存开销，除非您实现的版本可以在每个节点中包含多个条目。KD-Trees 在经常更新时也会退化，因此它们可能需要重新平衡。
  • 否则我会建议四叉树，例如qthypercube2。它们也非常简单，内存非常快，非常适合频繁更新，特别是如果条目仅移动一小段距离。
于 2018-07-11T20:32:57.790 回答