权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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。实际设计一个紧凑的哈希表，用于存储一组具有小位宽的动态整数1。我们为在压缩空间中索引矩阵提供了三种不同的压缩方法。在第一种方法中，我们使用了Vigna的WebGraph框架，它对二进制矩阵使用基于行的引用压缩。另一种方法是在将二进制矩阵解释为图的邻接矩阵时提取双曲线。最后一种方法处理任意值的矩阵，方法是通过使用唯一分隔符连接行，对线性化为字符串的行应用语法压缩器。如果存储在矩阵中的数据是结构化的，语法压缩器可以利用结构化重复，那么这种方法是有利的。小语法导致小算术电路，我们将其构建为加速矩阵-向量乘法的压缩索引。我们可以设计一个紧凑的哈希表，通过现代SIMD指令获得加速。哈希表的布局基于带有链的哈希，但使用的是数组而不是列表。虽然这些阵列的线性扫描速度很慢，但可以通过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

Dalhousie University(カナダ)

达尔豪西大学（加拿大）

DOI：
发表时间：
2019
期刊：
影响因子：
0
作者：
通讯作者：

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

接尾辞木に基づくLZ77とLPF配列の変種の計算

基于后缀树的 LZ77 和 LPF 数组变体的计算