权益分类	功能权益	普通用户	{{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 数组变体的计算