在具有相同域的大量集合上执行子集测试操作的最快方法

假设我们在某处存储了数万亿个集合。每个集合的域都是相同的。它也是有限的和离散的。因此，每个集合可以存储为相对较短长度的比特字段（例如：0000100111 ...）（例如：1024）。也就是说，位域中的位X指示项目X（1024个可能的项目）是否包括在给定集合中。现在，我想设计一个存储结构和算法来有效地回答查询：数据存储中的哪些集合将Y设置为子集。集合Y本身不存在于数据存储中，并在运行时指定。现在解决这个问题的最简单方法是将数据存储器中每组的位字段与集合Y的位字段逐一进行AND运算，选择其AND结果与Y的位域匹配的位。我怎样才能加快速度呢？是否有树结构（索引）或一些智能算法，允许我执行此查询而无需AND每个存储集的位域？是否有数据库已经支持大型集合上的此类操作？

已邀请:

6 个回复

爆山

如果您可以预处理集合，则子集关系可以表示为DAG（因为您正在描述一个poset）。如果计算了传递减少，那么我认为你可以避免通过从最大集合开始执行DFS来测试所有集合，并且只要Y不再是被访问的当前集合的子集就停止。

谷靛

根据绘制所有集合的集合的基数，一个选项可能是构建从元素到包含它们的集合的反向索引映射。给定一个集合Y，然后您可以通过找到包含每个元素的所有集合并计算它们的交集来找到所有具有Y作为子集的集合。如果按排序顺序存储列表（例如，通过使用值0,1等编号对数据库中的所有集合进行编号），那么您应该能够相当有效地计算此交集，假设也没有包含任何元素很多套。

抬澈帅沮

我倾向于说答案是否定的，因为比特场的基数非常低。

门锑腺潮

这将是基于您的音量的传统RDBMS的一个延伸，您是否看过基于图形存储模型的Neo4j？

骚瓤

快速浏览一下让我想到BDD--这与DAG解决方案的想法有些相似。或者是ZDD。

哭木算

如果RDBMS是您唯一的选择，我建议您查看有关在SQL中建模DAG的有趣文章： http://www.codeproject.com/KB/database/Modeling_DAGs_on_SQL_DBs.aspx?msg=3051183 如果您买不起Oracle或MSSQL，请查看支持递归查询的PostgresQL 9。它也支持交叉连接很长一段时间。

要回复问题请先登录或注册

在具有相同域的大量集合上执行子集测试操作的最快方法

6 个回复

发起人

set_theory

问题状态

在具有相同域的大量集合上执行子集测试操作的最快方法

与内容相关的链接

6 个回复

发起人

set_theory

问题状态