一类基于极图理论的局部修复编码的性质及构造 |
| |
引用本文: | 朱永振,徐光平.一类基于极图理论的局部修复编码的性质及构造[J].天津理工大学学报,2019(3). |
| |
作者姓名: | 朱永振 徐光平 |
| |
作者单位: | 天津理工大学计算机科学与工程学院 |
| |
摘 要: | 由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.
|
关 键 词: | 局部修复码 MDS码 极值二分图 Zarankiewicz问题 |
Based extremal graph applied to optimization of local repair |
| |
Abstract: | |
| |
Keywords: | |
本文献已被 CNKI 等数据库收录! |
|