2

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

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

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

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

7 回答 7

2

这取决于用户如何获得它的随机条目。

选项1：

用户正在分页一些实体并在其中几个之后停止。例如，用户看到当前的随机实体，然后移动到下一个，阅读它并继续它几次，就是这样。下次此用户（或其他用户）从该类别中获取实体时，已查看的实体已清楚，您可以返回已查看的实体。

在该选项中，我建议保存一组（散列）已查看的实体 ID，并且每次用户要求随机实体时 - 从数据库中随机选择它并检查是否尚未在集合中。

因为集合太小而且你的数据太大，你得到一个已经查看过的 id 的机会太小了，大部分时间都需要 O(1)。

选项 2：

用户正在实体中分页，并且查看的实体正在所有用户之间以及每次用户访问您的页面时保存。在这种情况下，您可能会使用每个类别中的所有实体并保存所有查看的实体 + 检查是否查看了实体将需要一些时间。

在该选项中，我将获取该主题的所有 id - 将它们打乱并将其存储在链接列表中。当您想获得一个随机未查看的实体时 - 只需获取列表的头部并将其删除（O（1））。

于 2012-07-16T08:29:10.730 回答
2

如果您通过表格跟踪用户看到的条目......试试这个。我将使用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

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

只是一个建议。

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

于 2012-07-21T00:48:59.637 回答
1

我假设对于任何给定的 <user, category> 对，查看的文档数量相对于该类别中可用的文档总数来说非常小。

那么你可以只存储索引三元组 <user, category, document> 指示哪些文档已被查看，然后对随机选择的文档采取乐观的方法吗？在绝大多数情况下，用户不会阅读随机选择的文档。而且您可以快速检查，因为三元组已编入索引。

于 2012-07-16T08:30:04.893 回答
1

我会选择伪随机方法：

1.) 确定要查看的类别中的元素数 (SELECT COUNT(*) WHERE ...)
2.) 在 1 ... count 范围内选择一个随机数。
3.）选择单个文档（SELECT * FROM ... WHERE [与计数时相同] ORDER BY [生成稳定顺序]。根据使用的SQL方言，有不同的子句可用于仅检索部分您想要的结果集（MySQL LIMIT 子句、SQLServer TOP 子句等）

如果文档的数量很大，那么两次为同一用户提供同一文档的机会很小，可以忽略不计。使用上述方案，您根本不必存储任何状态信息。

于 2012-07-16T14:44:13.680 回答
1

您可能需要考虑像 Apache Cassandra 这样的 nosql 解决方案。这些似乎非常适合您的需求。有很多方法可以在一个环境中设计您需要的算法，您可以轻松地在运行中轻松地将新列添加到表（列族）中，并为非常稀疏的表提供出色的支持。

编辑：以下许多可能的解决方案之一：

  1. 为每个类别创建一个 CF（列族，即表）（即时创建这些非常容易）。
  2. 为属于该类别的每个文档在每个类别 CF 中添加一行。
  3. 每当用户点击文档时，您都会添加一个名为的列并将其设置为 true 到该行。显然，这张表会很大，有数百万列，而且可能非常稀疏，但没问题，读取这仍然是恒定的时间。
  4. 现在为某个类别中的用户查找新文档只需从 select * where == null 中选择任何结果即可。

如果您可以接受 Cassandra 的“最终一致”模型，您应该获得恒定的写入和读取时间、惊人的可扩展性等（即，用户永远不会获得重复文档并不是关键任务）

于 2012-07-17T15:21:43.027 回答
1

我过去通过使用Apache Lucene将关系数据库索引到面向文档的形式中解决了类似问题。这是在 NoSQL 服务器最近兴起之前，基本上是一样的，但它仍然是一种有效的替代方法。

您将为每个文本创建一个 Lucene文档，其中包含一个 textId（关系数据库 id）字段和多值 categoryId 和 userId 字段。适当地填充 categoryId 字段。当用户阅读文本时，将其 id 添加到 userId 字段。一个简单的查询将返回具有给定 categoryId 而没有给定 userId 的文档集 - 随机选择一个并显示它。

于 2012-07-19T11:20:05.800 回答
0
  1. 将用户过去的 X 个选择存储在 cookie 或其他东西中。
  2. 使用用户的新条件将最后的选择返回到服务器
  3. 随机选择满足条件的文本之一，直到它不是用户最后 X 个选择的成员。
  4. 返回此文本选择并更新最后 X 选择的列表。

我会尝试找到 X 的最佳值，但我想到的是像 16 的 X？

于 2012-07-20T21:52:33.233 回答