algorithm - 如何提高匹配算法的性能

Question

我正在编写一个基于兴趣和位置进行匹配的算法。假设我有这些用户数据

{
    "users": [{
            "location": "Delhi, India",
            "interests": ["Jogging", "Travelling", "Praying"],
            "groups": ["exercise", "travelling", "Praying"]
        },
        {
            "location": "Delhi, India",
            "interests": ["Running", "Eating", "Praying"],
            "groups": ["exercise", "Eating", "Praying"]
        }, {
            "location": "Delhi, India",
            "interests": ["Shopping"],
            "groups": ["Shopping"]
        }
    ]
}

这里他们 user1 和 user2 有相似的兴趣“锻炼”和“祈祷”，而 user1 和 user3 没有相似的兴趣。

如果我每次在接收来自移动应用程序的请求时都使用带有 where 子句的 SQL 查询，那么要在超过 1000 万用户的数据库中找到相似兴趣的人可能会影响我的数据库性能。

SELECT * FROM users WHERE groups = "exercise" OR groups = "travelling" OR groups = "Praying";

这将检查可能影响我的应用程序性能的每个配置文件。我不想使用这种方法，因为它不会长期有效。我应该使用什么算法来实现高性能？

Answer 1

你可以构造一个 inverted index其中键是“组”中的标记之一(即锻炼、旅行等)，值是属于该组的用户列表。例如，您的倒排索引看起来像这样:

Key: ListOfValues
Exercise: User1 -> User2
Praying: User1 -> User2
Travelling: User1 -> User3 -> User8 -> User14
Shopping: User3

无论您想要基于树、位图还是基于哈希表的倒排索引，都将取决于您的空间/时间权衡。

现在，当您获得新用户时，假设 User99 拥有组(练习和祈祷)，您可以快速检索“练习” token 的值(即用户)，然后检索“祈祷” token 的值，最后执行两者的“与”(交集)。

请注意，第一次运行它会进行批处理，但是当你开始获得新用户时，你的运行时间复杂度几乎是恒定的(如果你有智能数据结构，比如压缩位图，这将适用您在倒排索引中的“用户”值的发布列表，否则交集不会比 O(n) AFAIK 快)