Indexing Massive Datasets with Algorithmic Engineered Compression Techniques on Modern Computer Architectures

根据2022财年的研究计划，我们的主要目标是：1.在允许索引矩阵的情况下，改进压缩空间中的矩阵-向量乘法。实际上设计了用于存储小位宽的一组动态整数的紧凑哈希表1。对于压缩空间中的索引矩阵，我们提供了三种不同的压缩方法。在第一种方法中，我们使用Vigna的Webgraph框架，该框架对二进制矩阵使用基于行的引用压缩。另一种方法是在将二进制矩阵解释为图的邻接矩阵时提取双线。最后一种方法适用于任意值矩阵，方法是对通过唯一定界符将行连接在一起而线性化为字符串的行上应用语法压缩器。如果存储在矩阵中的数据被结构化，使得语法压缩器可以利用结构化重复，则该方法是有利的。小的文法导致微小的算术电路，我们将其构建为加速矩阵-向量乘法的压缩索引。我们可以设计一个紧凑的哈希表，用现代的SIMD指令来提高速度。哈希表布局基于带链接的哈希，但使用数组而不是列表。虽然这些阵列的线性扫描很慢，但可以通过SIMD指令加速此操作。鉴于现代计算机体系结构为SIMD指令迅速获得更大的高速缓存大小和更大的位宽度，而处理器时钟速度的改进已经变得微不足道，这种方法是有前景的。

Following the research plan for the fiscal year 2022, our main objectives were:1. Improving matrix-vector multiplication in compressed space when indexing the matrix is allowed2. Practically engineering a compact hash table for storing a dynamic set of integers of small bit widths1. We provided three different compression approaches for indexing matrices in compressed space. In the first approach, we used the WebGraph framework of Vigna, which uses a row-based referencing compression for binary matrices. Another approach is the extraction of bicliques when interpreting the binary matrix as the adjacency matrix of a graph. The last approach works on arbitrarily-values matrices by applying a grammar compressor on the rows linearised to a string by concatenating the rows by unique delimiters. This approach is favorable if the data stored in the matrix is structured such that a grammar compressor can make use of the structured repetitions. Small grammars lead to tiny arithmetic circuits, which we build as a compressed index for accelerating matrix-vector multiplication.2. We could devise a compact hash table that gains speed-ups with modern SIMD instructions. The hash table layout is based on hashing with chaining, but with arrays instead of lists. While a linear scan of these arrays is slow, this operation can be accelerated via SIMD instructions. This approach is prospective in the light that modern computer architectures gain rapidly larger cache sizes and larger bit widths for SIMD instructions while processor clock speed improvements have become marginal.