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

Question

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

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

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

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

Answer 1

我会推荐一个哈希表实现。这将确保您获得持续的时间查找。您可以实现一种称为线性探测的技术。链表是一个糟糕的实现，因为你会占用O(N)搜索时间。

如果约束是它必须是一个关系数据库，您可以使用诸如 memcache 之类的东西（FB 使用它），以保留本质上是朋友的朋友问题。

Answer 2

有关如何以随机顺序从数据库返回条目的信息，请参阅此答案。现在，您可以简单地跟踪用户在随机序列中的位置（对于每个类别）和 Skip() 和 Take() 以获取下一组记录以显示它们。您可以存储每个用户的随机 XOR 值，以便每个用户看到不同的序列。