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

在现代计算机架构上使用算法工程压缩技术索引海量数据集

基本信息

批准号：
21K17701
负责人：
Koeppl Dominik
金额：
$ 3万
依托单位：
Tokyo Medical and Dental University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Early-Career Scientists
财政年份：
2021
资助国家：
日本
起止时间：
2021-04-01 至 2025-03-31
项目状态：
未结题

项目摘要

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.

遵循2022财政年度的研究计划，我们的主要目标是：1。允许在索引矩阵时改善压缩空间中的矩阵矢量乘法2。实际上，一张紧凑的哈希表来存储一个小宽度的动态整数。我们提供了三种不同的压缩方法，用于压缩空间中的索引矩阵。在第一种方法中，我们使用了Vigna的WebGraph框架，该框架使用基于行的引用压缩二进制矩阵。另一种方法是将二进制基质解释为图的邻接矩阵时提取双晶液。最后的方法通过将语法压缩机应用于线性的行中，通过将唯一的定界器串联到行中，将语法压缩机应用于线性的行中。如果矩阵中存储的数据结构化，以使语法压缩机可以利用结构化重复，则此方法是有利的。小语法导致微小的算术电路，我们将其作为加速矩阵矢量乘法的压缩索引构建。2。我们可以设计一个紧凑的哈希表，该表可以通过现代的SIMD说明获得加速的速度。哈希表布局基于链接的哈希，但带有数组而不是列表。尽管这些数组的线性扫描很慢，但可以通过SIMD说明加速此操作。鉴于现代计算机体系结构获得更大的高速缓存大小和更大的钻头宽度，而处理器时钟速度的提高已变得微不足道，这种方法是预期的。

项目成果

期刊论文数量（24）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Accessing the Suffix Array via $\phi^-1$-Forest

通过 $phi^-1$-Forest 访问后缀数组

DOI：
10.1007/978-3-031-20643-6_7
发表时间：
2022
期刊：
Proceedings of SPIRE
影响因子：
0
作者：
Tomohiro I;Dominik Koeppl;Dominik Koeppl;Dominik Koeppl and Simon J. Puglisi and Rajeev Raman;Daiki Hashimoto and Diptarama Hendrian and Dominik Koeppl and Ryo Yoshinaka and Ayumi Shinohara;Christina Boucher and Dominik Koeppl and Herman Perera and Massimiliano Rossi
通讯作者：
Christina Boucher and Dominik Koeppl and Herman Perera and Massimiliano Rossi

Linking Off-Road Points to Routing Networks

将越野点链接到路由网络

DOI：
10.3390/a15050163
发表时间：
2022
期刊：
Algorithms
影响因子：
2.3
作者：
Tomohiro I;Dominik Koeppl;Dominik Koeppl
通讯作者：
Dominik Koeppl

HOLZ: High-Order Entropy Encoding of {Lempel--Ziv} Factor Distances

HOLZ：{Lempel--Ziv} 因子距离的高阶熵编码

DOI：
10.1109/dcc52660.2022.00016
发表时间：
2022
期刊：
Proc. DCC
影响因子：
0
作者：
Tomohiro I;Dominik Koeppl;Dominik Koeppl;Dominik Koeppl and Simon J. Puglisi and Rajeev Raman;Daiki Hashimoto and Diptarama Hendrian and Dominik Koeppl and Ryo Yoshinaka and Ayumi Shinohara;Christina Boucher and Dominik Koeppl and Herman Perera and Massimiliano Rossi;Hideo Bannai and Keisuke Goto and Masakazu Ishihata and Shunsuke Kanda and Dominik Koeppl and Takaaki Nishimoto;Paolo Ferragina and Giovanni Manzini and Travis Gagie and Dominik Koeppl and Gonzalo Navarro and Manuel Striani and Francesco Tosoni;Koeppl Dominik;Koeppl Dominik;Dominik Koeppl and Gonzalo Navarro and Nicola Prezza
通讯作者：
Dominik Koeppl and Gonzalo Navarro and Nicola Prezza

Dalhousie University(カナダ)

达尔豪西大学（加拿大）