php - 如何在不遍历整个数据库的情况下获得最佳匹配？

Question

我有一个函数可以返回 2 个用户之间的兼容性百分比。

    function get_compatibility(user1, user2) {
      ...
      return compatibility;
    }

我正在寻找一种方法来查找给定用户的前 10 个最高兼容性匹配项，而无需遍历整个数据库。这可能吗？

如果用户数量很少，遍历数据库不会有问题。但是如果假设数据库增长到十万用户，那么我将不得不计算大约十万次兼容性%并对结果进行排序。显然，这是不可扩展的。

Answer 1

正如cobarzan所说，这完全取决于你所说的“兼容性”。

假设我们正在谈论属性以及它们彼此之间的接近程度，您最好的选择可能是使用类似于 MinHash 的东西第一次构建一个查找表，在其中为每个用户预先计算一个索引，为他们提供一个散列(见上文)，引用一个“通用”集，所有值都为最大值，然后按该集排序。

然后，每次添加用户时，您都会检查该用户在兼容性查找中的位置，并将其放入正确的“相似”列表中。

例如，假设您将年龄和鞋码作为兼容性参数。假设年龄的最大值为 99，鞋码的最大值也为 99。

然后你决定你的散列函数是什么。这只是一个示例，为简单起见，我们假设哈希为 (age+shoe_size)/age/99。

年龄为 27 岁且鞋码为 43 的用户的索引为 (27+43)/27/99=0.0261 。年龄为 80 岁且鞋码为 40 的用户的索引为 (80+40)/80/99=0.0151。

第一次，您必须为每个用户执行此操作并按该索引排序。 然后每次添加新用户或用户中的一个值发生变化时，只需将其放在正确的位置即可，这很容易，因为列表已经排序。

同样，这只是猜测，因为您没有解释什么是“兼容性”。