快速过滤数据的数据结构

当涉及到特定数据的许多属性时，我正在做一些有关过滤算法的研究。对于我学习新的数据结构来说，这是一个有趣的项目。快速过滤数据的数据结构

例如，我想要所有RPG游戏机上的英文版。

现在我想允许更复杂的查询。

是否有一个很好的数据结构来处理像这样的过滤属性，而不需要提供所有的属性。相反，我只能提供几个，仍然可以找到正确的游戏？

我目前打算让“水桶”来描述一个属性，例如所有类型的游戏ID都会在一个桶中，等等。然后我将使用散列算法将1添加到该游戏中，并且仅在搜索之后使用具有正确值的游戏。

但我想尝试找到一个更快或更简单的方法，任何建议，当涉及到过滤许多属性来查找套项目？

谢谢，

来源

2017-06-01 Krum110487

你是什么意思，“不需要给所有的属性”？你是否说你有N个属性，并且你想找到与这些属性匹配的项目，或者你是否说你不想计算每个属性的索引？

将每个属性散列为存储桶将给你O（1）时间以牺牲O（n）空间来存储每个索引。
你可以排序由一个或两个属性列表在不得不做的排序提前为0的费用，使一些查找O（LOGN）（nlogn）时间
你可以得到与bloom filters为还挺聪明的你属性并让一些属性重叠。这会导致一些误报，但你可以在事后将其过滤掉。这在平均情况下给你恒定时间的恒定空间查询（但在最差情况下为O（n）时间）。

来源

2017-06-01 23:20:36 Ryan

这很有趣，因为我一直在考虑使用第二个，至少类似于它，我想我会跟踪每个桶中有多少物品，所以我可以找到最小的桶作为我的“基地”来过滤掉。这样我就从这个特定的过滤器可能的最小量开始。我同意我的存储问题，因为我必须考虑属性的组合，比如同时拥有“动作”和“RPG”类型的游戏需要一个索引“动作RPG”会看起来和自己一样。 – Krum110487

我想知道是否有一个好的方法来预测碰撞，例如10号，15号，19号和30号总是在相同的位置，所以对于单场比赛，我需要每场比赛都有10分重叠，这意味着有每个属性可以重叠只有10个数字......我会看看这个，如果没有其他人提供更好的东西，我会将其作为答案。谢谢。 – Krum110487

多重索引的东西就是数据库要做的事情。如果过滤'X = 1和Y = 2'，它将使用统计信息（桶的大小）生成查询计划，并查找所有具有“X = 1”的项目，然后与项目有'Y = 2'。数据库也有复合索引，可以完成你指出的“动作RPG”技巧。 – Ryan

快速过滤数据的数据结构

回答

相关问题