如何提高匹配算法的性能

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具有类似的兴趣"exercise"和"Praying",而user1和user3没有类似的兴趣.

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

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

这将检查可能影响我的应用程序性能的每个配置文件.我不想使用这种方法,因为这不会很长时间.我应该使用什么算法来获得高性能？

Answer 1

您可以构建一个倒排索引，其中键是“组”中的标记之一（即锻炼、旅行等），值是属于该组的用户列表。例如，您的倒排索引将如下所示：

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

无论您想要基于树、位图还是基于哈希表的倒排索引，您都可以根据您的空间/时间权衡进行选择。

现在，当您获得一个新用户时，假设 User99 拥有组（锻炼和祈祷），您可以快速检索“锻炼”令牌的值（即用户），然后检索“祈祷”令牌的值，最后执行“AND”操作'（两者的交集）。

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