database - 具有固定列数的可搜索位矩阵的一个好的表示形式是什么？

Question

原始数据可以描述为固定数量的列（大约几千列）和很大数量的行（大约数十亿行）。每个细胞都有一点。所需的查询类似于查找设置了位1232929123020的所有行。有点像

for (i=0;i< max_ents;i++) 
    if (entry[i].data & mask == mask) 
        add_result(i);

在典型情况下，在任何特定行中设置的位都不多（例如5%），但这是不能保证的，存在一定程度的可变性。
在更高的层次上，数据描述条目的位指纹，并且数据本身是一种搜索索引，因此需要最大速度。哪种算法适合这种搜索？目前，我正在考虑分别为每一列使用单独的稀疏（压缩/压缩）位向量。但我怀疑它是否是最佳的。

Answer 1

这看起来类似于“文本搜索”，特别是交叉反向索引。让我来看看最简单的算法。
首先，您应该在设置每个位的地方创建排序的数字列表。例如，对于数字表：
第1行->10110
第2行->00111
第3行->11110
第4行->00011
第5行->01010
第6行->10101
可以创建反向索引：
位0在->2、4、6中设置
位1设置在->1、2、3、4、5中
位2设置在->1、2、3、6中
等。
现在，对于一个查询（比方说位0&1&2），您只需要使用类似于合并排序的算法来合并这些排序过的列表。为此，您可以首先合并列表0，1，给出{2，4}，然后将其与列表2合并，给出{2}。
有几种优化是可能的，包括但不限于压缩这些列表，因为连续项之间的差异通常很小，可以进行更有效的合并等。
但是，为了省去更多的麻烦，为什么不重用其他人已经做过的工作呢？；）…你可以很容易地使用任何开源文本搜索引擎（我建议Lucene）来执行这个任务（应该可以在不到一天的编码时间内完成），它应该包含人们长期以来构建的几个优化；）。（提示：在文本搜索术语中，应该将每一行视为“doc”，将每一位视为“token”）。
编辑（根据问题作者的请求添加一些算法）：
a）压缩：你能做的最有效的事情之一是压缩发布列表（对应于每个位置的排序列表）。大多数算法通常取连续项的差异，然后根据一些编码（Gamma Coding，Varint Encoding）对其进行压缩。这将压缩倒排列表，使其占用更少的文件空间（从而减少文件I/O），或者使用更少的内存对同一组数字进行编码。在您的情况下，我可以估计每个发布列表将包含~5%*1e9=5e7元素。如果它们均匀分布在0-1e9之间，那么间隔应该在20左右，所以我们假设每个间隔的编码平均需要大约8b（这是一个很大的高估值），加起来高达500mb。所以对于1000个列表，您需要500GB的空间，这肯定需要一个磁盘空间。这反过来意味着您应该尽可能使用好的压缩算法，因为更好的压缩意味着更少的文件I/O，而且您将受到I/O的限制。
b）交集顺序：您应该始终从最小的开始交集列表，因为这样可以保证通过下面所示的技术创建最小大小的中间列表，这意味着以后更少的比较。
c）合并算法：由于索引几乎肯定会溢出到磁盘，因此在算法级别上可能做不了多少事情。但是，使用的一些想法是使用基于二进制搜索的过程来合并两个列表，而不是简单的线性合并过程，以使列表中的一个比另一个小得多（这将导致O(N*log(M))复杂性而不是O(N+M)这里M >> N）。但是对于基于文件的索引，这几乎不是一个好主意，因为二进制搜索会进行许多随机访问，这会完全增加磁盘延迟，而线性合并过程是严格按顺序进行的。
d）Skip Lists：这是另一个伟大的数据结构，用于存储已排序的投递列表，它还可以支持前面提到的高效“二进制搜索”。这里的关键思想是，跳过列表的上层可以保存在内存中，这可以大大加快交集算法的最后阶段，这时您可以简单地搜索内存中的上层以获得磁盘偏移量，然后从那里进行磁盘访问。有一点是二进制搜索+基于skiplist的合并比线性合并更有效，并且可以通过实验找到。
e）缓存：无需考虑。如果某些术语经常出现，请将它们缓存在内存中，以便将来更有效地获取它们。请注意，缓存也可以是，例如更快的基于闪存的磁盘，它可以提供更好的吞吐量，也可能缓存大量更频繁的项（32GB内存只能容纳约64个列表，而256GB闪存可以容纳约512个）。