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

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

基本信息

  • 批准号:
    21K17701
  • 负责人:
  • 金额:
    $ 3万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    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
  • 期刊:
  • 影响因子:
    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
  • 期刊:
  • 影响因子:
    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
  • 期刊:
  • 影响因子:
    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 数组变体的计算
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    品川 和雅;縫田 光司;中島 祐人 and クップル ドミニク and 舩越 満 and 稲永 俊介;クップル ドミニク
  • 通讯作者:
    クップル ドミニク
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

Koeppl Dominik其他文献

クロスドメインマッチング相関分析を用いた画像とキャプションの同時埋め込み
使用跨域匹配相关性分析同时嵌入图像和标题
  • DOI:
  • 发表时间:
    2017
  • 期刊:
  • 影响因子:
    0
  • 作者:
    Mieno Takuya;Koeppl Dominik;Nakashima Yuto;Inenaga Shunsuke;Bannai Hideo;Takeda Masayuki;福井一輝,下平英寿
  • 通讯作者:
    福井一輝,下平英寿

Koeppl Dominik的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

相似海外基金

AF:Small: Algorithms and Limitations for Matrix Multiplication
AF:Small:矩阵乘法的算法和限制
  • 批准号:
    2330048
  • 财政年份:
    2023
  • 资助金额:
    $ 3万
  • 项目类别:
    Standard Grant
AF: Small: The complexity of matrix multiplication
AF:小:矩阵乘法的复杂度
  • 批准号:
    2203618
  • 财政年份:
    2022
  • 资助金额:
    $ 3万
  • 项目类别:
    Standard Grant
AF: Small: Group Theory and Representation Theory in Matrix Multiplication and Generalized DFTs
AF:小:矩阵乘法和广义 DFT 中的群论和表示论
  • 批准号:
    1815607
  • 财政年份:
    2018
  • 资助金额:
    $ 3万
  • 项目类别:
    Standard Grant
The search for fast matrix multiplication algorithms
寻找快速矩阵乘法算法
  • 批准号:
    510042-2017
  • 财政年份:
    2017
  • 资助金额:
    $ 3万
  • 项目类别:
    University Undergraduate Student Research Awards
AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform
AF:小:矩阵乘法、多项式分解和广义傅立叶变换算法
  • 批准号:
    1423544
  • 财政年份:
    2014
  • 资助金额:
    $ 3万
  • 项目类别:
    Standard Grant
EAGER: Numerical Accuracy of Randomized Algorithms for Matrix Multiplication and Least Squares
EAGER:矩阵乘法和最小二乘随机算法的数值精度
  • 批准号:
    1145383
  • 财政年份:
    2011
  • 资助金额:
    $ 3万
  • 项目类别:
    Standard Grant
Memory-hierarchy optimal matrix multiplication-programs
内存层次优化矩阵乘法程序
  • 批准号:
    35224341
  • 财政年份:
    2007
  • 资助金额:
    $ 3万
  • 项目类别:
    Independent Junior Research Groups
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了