多维稀疏矩阵行储存压缩研究

数据库数据库

Created At : 2022-01-15 21:46

Views 👀 :

PATRICIA 字典树压缩储存
扩展压缩行储存CRS/列储存CCS方法

PATRICIA 字典树压缩储存

扩展压缩行储存CRS/列储存CCS方法

概述

在CRS方法的基础上，将维度从二维的行和列扩展到k-维空间(k>2),进而提出了扩展CRS的方法xCRS/xCCS，考虑到CRS和CCS高度的相似性，因此我们只讨论CRS方法。

为了在多维空间使用CRS方法，我们需要选取一种映射，将k维数组转换到CRS方法中的行和列的形式，具体的操作是将原本的k-维空间映射到一个行(为第j个维度构成集合的势)的二维形式；在这种映射的作用下，原多维空间的每一个行元素能够转化为一个独一无二的键值（key），这个键值则又是通过行偏移量（row offsets）和维度的索引值共同决定的；对于行偏移量，它使用个索引值，比如来表示；而对于行中的每一个元素使用，进一步地可以使用的形式计算；因此通过这种维度映射，对于每一个行元素都能计算出一个独一无二的键值。

实现存储形式

根据上面的内容，我们可以得出XCRS对多维数据中的非零元素的储存方式的储存方式：对于数据Value本身和它们在原有的多维矩阵中对应的维度的索引被储存在两个一维数组：和 $中$ ；除此之外，还需要再使用一个一维数组来储存中每个行的起始位置，如果xCRS中的行没有有效的元素，那么这个一行的起始位置就被标记为缺省值“- 1”。需要注意的是xCRS中的每一个行在中都有一个条目，其位置对应着这个行的行偏移值（row offset）。
这里给出xCRS存储的一种案例：

对于表中的第一个非零元素，其位置对应着多维数组中的（0，0，0）位置的数据 20.5 ,因此其cind为0。
对于第二个非零元素，其位置对应着多维数组中的（0，0，1），因为其在K轴上维度上的索引为1，其cind为1；对于17.0，23.6，14.9 类似，其cind分别为 2，3，3。
对于rptr行的每一个偏移值，其计算方式如下：如果我们固定i=0，j=0，任取K时，我们可以得到一个行[（0，0，0）,（0，0，1）,（0，0，2）,（0，0，3）]，则其第一个元素（20.5）在val中的起始位置的偏移量offset是0,因此该位置的rptr为0；同理，固定i=0，j=1，任取K时，提出出的行[（0，1，0）,（0，1，1）,（0，1，2）,（0，1，3）]，中没有任何的非零元素，因对应位置的rptr为-1，对offset为2的位置（i=0，j=2，任取K）其原理类似，因为offset为0对应的行有两个非零元素，而此行至少有一个非零元素，因此其开始值即为rptr亦为 2，对于剩下的值计算类似。

如何从压缩后的状态还原

对于xCRS类似，还是按着上面一节举的例子，如果要在CRS压缩后的结构中查询原矩阵的 $（，，）$ 位置的数据，需要先计算改位置对应的行索引，即为：3X+Y，然后在中查询对应的行开始位置，即 $rptr[3X+Y] $如果该处的值为$ -1 $的话，说明该行全部都是空的，返回空值即可；如果不为说明该行有非零数值，再根据$ cind $中存储的数据，查询该坐标中轴对应的位置，即同时满足$ cind[k]=Z $的值，之后就可以根据$ rptr[3X+Y] $获取该行开始的位置，则$ rptr[3X+Y] $到下一个$ rptr[3*X+Y] $中非空的位置的差，即为该行非空元素的个数，然后就可以再根据$ cind[k]=Z $的条件，选出满足该条件的对应的$ offset $对应的$ val $值，即为所求位置$ （X，Y，Z）$的value；如果没有满足条件的值，说明该位置的元素为空。

举一个例子，还是再刚才的xCRS表中,加入我们要获取坐标为 $（，，）$ 处的值,首先需要根据X和Y值算出对应的行的开始坐标，即为再根据的条件算出满足解得，即为所求。

公式化映射：

对于K维组,有：从K维空间到三个一维空间的映射满足：
多维空间对应的取值等于
其中
PS：表示维度上的的集合的势。

研究一下xCRS压缩率

当多维数组的稀疏性很高时，xCRS下的压缩比会变差。这是因为存储每一行起始位置的xCRS数组rptr本身可能变得较为稀疏。

转载无需注明来源，放弃所有权利