database - 需要快速存储和检索(搜索)集合和子集的算法

Question

我需要一种方法来存储任意大小的集合，以便以后进行快速查询。 我将需要为已存储的子集或集合查询生成的数据结构。

=== 稍后编辑:为了澄清，这个问题的一个可接受的答案将是一个链接到一个研究，该研究提出了这个问题的解决方案。我不希望人们自己开发算法。 我一直在查看发现的元组聚类算法 here ，但这并不是我想要的，因为根据我的理解，它将元组“聚类”为更简单、离散/近似的形式，并丢失了原始元组。

现在，一个更简单的例子:

[alpha, beta, gamma, delta] [alpha, epsilon, delta] [gamma, niu, omega] [omega, beta]

查询:

[alpha, delta]

结果:

[alpha, beta, gama, delta] [alpha, epsilon, delta]

所以集合元素就是唯一的、不相关的元素。忘记类型和值。可以在其中测试元素是否相等，仅此而已。我正在寻找一种成熟的算法(可能有一个名字和一篇关于它的科学论文)，而不是现在就当场创建一个算法。

== 原始示例:

例如，假设数据库包含这些集合

[A1, B1, C1, D1], [A2, B2, C1], [A3, D3], [A1, D3, C1] 

如果我使用 [A1, C1] 作为查询，这两个集合应该作为结果返回:

[A1, B1, C1, D1], [A1, D3, C1]

示例 2:

数据库:

[Gasoline amount: 5L, Distance to Berlin: 240km, car paint: red]
[Distance to Berlin: 240km, car paint: blue, number of car seats: 2]
[number of car seats: 2, Gasoline amount: 2L]

查询:

[Distance to berlin: 240km]

结果

[Gasoline amount: 5L, Distance to Berlin: 240km, car paint: red]
[Distance to Berlin: 240km, car paint: blue, number of car seats: 2]

可以有无限数量的“字段”，例如Gasoline amount。解决方案可能涉及数据库分组和链接具有共同状态(例如 Gasoline amount: 240)的集合，以使查询尽可能高效。

有什么算法可以满足这种需求？

我希望这个问题已经有一个既定的解决方案，而不是仅仅试图在现场找到我自己的解决方案，这可能不如其他人随着时间的推移测试和改进的那样有效。

说明:

• 如果它有助于回答问题，我打算使用它们来存储状态: 简单示例: [有牛奶，没有鸡蛋，有糖]
• 我认为这样的要求可能需要图形或多维数组，但我不确定

结论 我已经实现了答案中提出的两种算法，即 Set-Trie 和 Inverted Index 并对它们进行了一些基本的分析。下面说明的是针对每个算法的给定集合的查询持续时间。两种算法都处理由整数集组成的相同随机生成的数据集。这些算法在性能方面似乎等效(或几乎):

Answer 1

我有信心现在可以为解决方案做出贡献。一种可能的非常有效的方法是:

Trie由 Frankling Mark Liang 发明

这种特殊的树用于例如拼写检查或自动完成，实际上接近您想要的行为，特别是允许非常方便地搜索子集。

您的情况的不同之处在于您对属性/特征的顺序不感兴趣。对于你的情况 Set-Trie由 Iztok Savnik 发明。

什么是集合树？一种树，其中除根节点外的每个节点都包含一个属性值(数字)和一个标记( bool 值)(如果该节点有数据条目)。每个子树仅包含其值大于父节点属性值的属性。 Set-Tree 的根是空的。搜索关键字是从根到树的某个节点的路径。搜索结果是从根到所有节点的路径集，其中包含您在沿着树向下并同时向上搜索键时到达的标记(见下文)。

但首先是我画的:

属性是{1,2,3,4,5}，实际上可以是任何东西，但我们只是枚举它们，因此自然会得到一个顺序。数据是 {{1,2,4}, {1,3}, {1,4}, {2,3,5}, {2,4}} 图中是从根开始的一组路径到任何圈子。圆圈是图中数据的标记。

请注意，根的右子树根本不包含属性 1。这就是线索。

搜索包括子集 假设您要搜索属性 4 和 1。首先您对它们进行排序，搜索关键字是 {1,4}。现在从根开始，你同时向上搜索关键字和向下搜索树。这意味着你取键中的第一个属性(1)并遍历属性小于或等于1的所有子节点。只有一个，即1。在里面你取键中的下一个属性(4)并访问所有属性值小于4的子节点，即全部。您继续，直到无事可做，并收集属性值恰好为 4(或键中的最后一个属性)的所有圆圈(数据条目)。这些是 {1,2,4} 和 {1,4} 但不是 {1,3}(没有 4)或 {2,4}(没有 1)。

插入非常容易。沿着树往下走，在适当的位置存储一个数据条目。例如，数据条目 {2.5} 将存储为 {2} 的子项。

动态添加属性 自然就做好了，可以马上插入{1,4,6}。它当然会低于 {1,4}。

我希望你能理解我想说的关于 Set-Tries 的内容。在 Iztok Savnik 的论文中对其进行了更详细的解释。它们可能非常高效。

我不知道你是否还想把数据存储在数据库中。我认为这会使事情进一步复杂化，我不知道那时最好做什么。