代码之家 › 专栏 › 技术社区 › driAn

匹配数以百万计的人:K-D树还是位置敏感的散列?

locality-sensitive-hash kdtree nearest-neighbor azure-cosmosdb algorithm

4

driAn · 技术社区 · 8 年前

我正在寻找一个性能算法来匹配大量的人位置 , 性别和年龄根据此数据结构:

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

算法应按距离(lat/long)的顺序返回前100个候选C。算法应该针对搜索和更新进行优化,因为人们可能经常更改他们的位置。

我现在的想法是 k-d 树 可能比 位置敏感散列 为了这些需要,我应该朝这个方向努力。

你对我有什么建议?我该找什么?你看到了什么风险?

谢谢!

更新 :

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

1 回复 | 直到 8 年前

1

TilmannZ 8 年前

Here 是Microsoft提供的一些如何使用空间索引的信息(“Spatial”是您要搜索的关键字)。

您要查找的查询是k=100的k-最近邻查询(knn search)。

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

关于其他索引:

我对强迫症没有经验,所以不能说太多。不过,我知道一件事,因为它在内部是一个散列图,所以您需要特别小心,使它能够使用大量数据进行扩展。这无疑增加了复杂性。另一个问题是,我不确定LSH是否适合KNN搜索,你必须查一下。
kd树非常简单,应该用于作业,但不利于序列化,并且可能会有很大的内存开销,除非实现的版本在每个节点中可以有多个条目。kd树经常更新时也会退化,因此可能需要重新平衡。
否则我建议使用四叉树,例如 qthypercube2 . 它们也非常简单,内存非常快,非常适合频繁更新,特别是当条目移动距离很小时。