一类基于极图理论的局部修复编码的性质及构造

• 作者: 徐光平 朱永振
• 来源期刊: 天津理工大学学报
• 学科: 工学
• 关键词: 局部修复码 MDS码 极值二分图 Zarankiewicz问题
• 年，卷（期）: 2019,（3）
• 页码范围: 38-42,47
• 页数: 6页
• 分类号: TP316.4
• 字数: 3782字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-095X.2019.03.007

摘要

由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐光平	天津理工大学计算机科学与工程学院	16	37	4.0	5.0
2	朱永振	天津理工大学计算机科学与工程学院	1	0	0.0	0.0