algorithm - 从大量条目中随机详尽(非重复)选择

Question

假设我有一个大型 (300-500k) 文本文档集合存储在关系数据库中。每个文档可以属于一个或多个(最多六个)类别。我需要用户能够随机选择特定类别中的文档，以便永远不会重复单个实体，就像 StumbleUpon 的工作方式一样。

我真的看不出有什么方法可以通过对大量用户和文档使用慢速 NOT IN 查询来实现这一点，所以我想我可能需要为此目的实现一些自定义数据结构。也许已经有一篇论文描述了一些可能适合我需要的算法？

目前我正在考虑以下方法:

• 从数据库中读取所有条目
• 根据属于该类别的文档的 ID，为每个类别创建一个基于链表的索引。随机播放
• 创建一个包含特定用户查看的所有条目的布隆过滤器
• 使用迭代器遍历索引，使用 Bloom Filter 随机选择项目以挑选未查看的项目。

Answer 1

如果您通过表格跟踪用户看到的条目...试试这个。我将使用 mysql，因为这是我能想到的最快的示例，但要点应该很清楚。

在“使用”的链接上...

insert into viewed (userid, url_id) values ("jj", 123)

正在寻找链接...

select p.url_id
from pages p left join viewed v on v.url_id = p.url_id
where v.url_id is null
order by rand()
limit 1

这会导致数据库继续执行一对一联接，并且您将查询限制为仅返回一个用户尚未看到的条目。

只是一个建议。

编辑:可以进行这一操作，但不能保证 url 会成功传递给用户。