是否存在用于存储关系的概率数据结构？

Question

我有包含用户订阅主题的数据库。目前大约有 20 000 个主题， SQL 数据库中存储了 2000 万用户和 2 亿订阅。由于其大小，数据库按主题分区，所以我无法在一个数据库查询中获取信息。有几个主题有 1000 万订阅，有 100 000 个，其他主题有数百个或更少。

当一个事件发生时，它通常会匹配几个主题，所以为了通知用户，我需要执行类似"give me all users subscribed to topics x, y, z and perform union of sets"的查询，这样一个用户即使订阅了主题x和z.

约束是：

联合集中不能有重复项。（用户无法二次获取内容）
联合集中可以缺少一定数量的用户。（如果有时用户没有得到内容，那还不错，但不能总是同一主题的同一用户）
无需重新构建整个主题就可以订阅新主题。

我考虑过为每个主题使用一组布隆过滤器，但它们的限制是相反的："user either not subscribed for sure or probably subscribed"。我需要像 "user subscribed for sure or probably not".

这样的东西

有损哈希表可能是个好主意，但我不确定它们是否能像 bloom 过滤器一样高效存储，我担心，它总是同一个用户，会丢失他的内容主题。

你是否知道任何其他数据结构，可以帮助解决这个问题？

Answer 1

如果每个用户记录都有一个代表所有主题的 BIT FIELD 会怎么样。

TABLE Users(ID INT, UserName VARCHAR(16), Topics BINARY(8000))

二进制 8k 将允许您拥有 64000 个主题。我可能会使用多个 BINARY(1024) 列，这样我就可以轻松添加更多主题。

现在，当一个事件到来时，它被标记为主题 1、10、20、30、40。我必须搜索每个用户，但这可以并行化并且总是 N 复杂度，其中 N 是总用户数。

SELECT ID 
FROM Users (READPAST)
WHERE 
    SUBSTRING(Topics, 1 / 8, 1) & (1 * POWER(2, (1 % 8))) > 0
    OR
    SUBSTRING(Topics, 10 / 8, 1) & (1 * POWER(2, (10 % 8))) > 0
    OR
    SUBSTRING(Topics, 20 / 8, 1) & (1 * POWER(2, (20 % 8))) > 0
    OR
    SUBSTRING(Topics, 30 / 8, 1) & (1 * POWER(2, (30 % 8))) > 0
    OR
    SUBSTRING(Topics, 40 / 8, 1) & (1 * POWER(2, (40 % 8))) > 0
OPTION (MAXDOP = 64)

没有重复我们只扫描一次用户，所以我们不用担心联合
一些用户缺少 READPAST 提示将跳过当前锁定（正在更新）的所有行，因此结果中可能缺少一些用户。
订阅您可以[取消]订阅主题，只需切换“主题”列中的主题位即可。

Answer 2

正如我在评论中所说，基于内存的精确解当然是可行的。

但是如果你真的想要一个近似的数据结构，那么你正在寻找一个具有随机驱逐的大小限制集（每个主题的用户）。

您还需要在查询到达时快速计算并集。这里没有有用的预计算。如果主题集有重复的倾向，可以考虑缓存经常使用的联合。

表示集合的所有常用方法都适用。哈希 tables（封闭和开放）、树和跳跃列表（都包含用户 ID 键；不需要值）是最有可能的。

如果您使用具有良好哈希函数的封闭哈希 table，伪随机逐出会自动发生。发生碰撞时，只需替换之前的值。封闭散列的问题总是为您需要表示的集合选择一个好的 table 大小。请记住，要恢复集合元素，您必须遍历整个开放的 table 包括空条目，因此从巨大的 table 开始并不是一个好主意；而是从一个小的开始并重组，每次增长一个因子，因此重组分摊到每个存储元素的恒定时间开销。

对于其他方案，当 table 变得太大时，您可以真正地进行伪随机驱逐。公平驱逐的最简单方法是存储用户 ID 的 a table 并设置大小受限的存储索引。通过在 table 中生成随机索引并在添加新 ID 之前删除该 ID 来驱逐。

也可以通过使用 order statistic tree 从 BST 集合表示中公平地逐出：存储每个节点中的后代数。然后你总能找到键排序顺序中的第 n 个元素，其中 n 是伪随机的，并将其逐出。

我知道您正在寻找布隆过滤器的按位 space 效率，但保证没有误报似乎排除了这种可能性。

Answer 3

这可能不是您正在寻找的解决方案，但您可以利用 ElasticSearch 的 terms filter 并为每个用户创建一个这样的文档：

{
  "id": 12345,
  "topics": ["Apache", "GitHub", "Programming"]
}

术语过滤器直接响应查询 "which users subscribe to at least one of these topics" 并且 ES 在如何缓存和重新利用过滤器方面非常聪明。

它不会是概率数据结构，但可以非常有效地解决这个问题。您需要使用 scan api 来序列化检索可能较大的 JSON 响应。如有必要，您可以将此解决方案扩展到分布在多台计算机上的数十亿用户，并获得 10 - 100 毫秒的响应时间。您还可以找到主题之间的相关性（重要术语聚合）并使用 ES 作为进一步分析的引擎。

编辑：我在Python中实现了搜索和扫描/滚动API用法，并得到了一些有趣的结果。我对 2000 万用户和 20000 万订阅数据集进行了 "users who subscribe to any three of these topics" 查询，一般来说，搜索本身会在 4 - 8 毫秒内完成。查询 return 350.000 - 750.000 个用户。

即使使用 scan/scroll API，从 ES 中获取用户 ID 也会出现问题。在 Core i5 上，我似乎每秒只有 8200 个用户，所以它不到 50 万/分钟（"_source": false）。查询本身如下所示：

{
  "filtered": {
    "filter": {
      "terms": {
        "topics": [ 123, 234, 345 ],
        "execution": "plain",
        "_cache": false
      }
    }
  }
}

在生产中，我会使用 "execution": "bool" 以便可以缓存部分查询结果并在其他查询中重新使用。我不知道获取结果的瓶颈是什么，服务器的 CPU 使用率为 50% 而我运行客户端的 python 脚本在同一台机器上，利用 elasticsearch.helpers.scan.

Answer 4

[此解决方案与 Louis Ricci 的解决方案类似，只是反转了主题 table - 这可能会降低订阅更新的实用性，请注意！]

（概率数据结构方法很酷，但对于您当前的数据大小来说是不必要的。我最初是在寻找非概率解决方案的压缩位集，因为它们非常擅长执行集合操作在内存中，但我认为这也太过分了。Here is a good implementation for this type of use-case. 如果你有兴趣。）

但是查看数据的 稀疏性 ，位集浪费 space 超过整数数组。即使使用整数数组，考虑到 每个主题平均只有 10,000 个订阅，union 操作仍然相当便宜。

所以也许，只是也许，给定您的用例的一个非常简单的数据结构很简单：

Topic 1 => [array of subscriber IDs]
Topic 2 => [array of subscriber IDs]
...
Topic 20,000 => [array of subscriber IDs]

存储（平均）10,000 个订阅者 ID（假设 32 位整数）每个主题仅需要 40kb space。

[在数组类型或 BLOB 中，具体取决于您的数据库]

有 20,000 个主题，这只会向您的主题添加 800mb 的数据 table ... 通知时需要将其中很少的数据（平均约 200kb）加载到内存中事件发生！

那么当平均事件（影响5个主题）发生时，需要发生的是：

查询/拉取相关主题的数据（平均5条记录）到内存中（平均 ~200kb，共 I/O）
将它们转储到 Set 数据结构中（删除重复订阅者列表）
提醒集合中的订阅者。

是否存在用于存储关系的概率数据结构？

Is there a probabilistic data structure for storing relations?

algorithm

set

storing-data

data-structures