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

Question

我需要一种存储任意大小的集合的方法,以便以后快速查询.我将需要查询已存储的子集或集合的结果数据结构.

===后来的编辑:为了澄清,这个问题的一个被接受的答案将是一个研究的链接,该研究提出了解决这个问题的方法.我不希望人们自己开发算法.我一直在研究这里发现的元组聚类算法,但它并不完全是我想要的,因为从我的理解它将元组"聚类"成更简单,离散/近似的形式并失去原始元组.

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

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

查询:

[alpha, delta]

结果:

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

所以set元素就是那些独特的,无关的元素.忘记类型和价值观.可以在它们之间测试元素是否相等,就是这样.我正在寻找一种既定的算法(可能有一个名称和科学论文),而不仅仅是现场创建一个.

==原始示例:

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

[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

拥有一个由哈希值构建的反向索引怎么样？

假设您有不同类型的值int A, char B, 。bool C使用std::hash（或任何其他哈希函数）您可以创建数字哈希​​值size_t Ah, Bh, Ch。

然后定义一个映射，将索引映射到指向元组的指针向量

std::map<size_t,std::vector<TupleStruct*> > mymap;

或者，如果您可以使用全局索引，只需

std::map<size_t,std::vector<size_t> > mymap;

对于通过查询X和进行检索Y，您需要

1. 获取查询的哈希值Xh并Yh
2. 得到相应的“集合”mymap
3. 与集合相交mymap[Xh]并且mymap[Yh]