-
题名一类基于极图理论的局部修复编码的性质及构造
被引量：1
- 1
-
-
作者
朱永振
徐光平
-
机构
天津理工大学计算机科学与工程学院
-
出处
《天津理工大学学报》
2019年第3期38-42,47,共6页
-
基金
国家自然科学基金(61201234)
天津市自然科学基金(17JCYBJC15600,18JCTPJC48700)
-
文摘
由于分布式存储系统大量使用廉价的磁盘构建,磁盘故障往往不可避免导致数据丢失.数据编码是一种防止数据丢失的必要容错机制.局部修复码与经典的最大距离可分(MDS)码相比,以一定的存储空间开销,能够有效提高数据修复的效率,降低网络带宽占用.为了降低该码的存储空间开销,本文研究以极图理论来描述该类编码.将存储节点与编码块抽象为二分图中的X、Y两类顶点,从而存储空间占用最小化等价于计算二分图中边数的极小值.这种求极值问题可以归结为Zarankiewicz问题.本文使用极值二分图对局部修复码进行建模与分析,并给出了相应的构造算法.
-
关键词
局部修复码
MDS码
极值二分图
zarankiewicz问题
-
Keywords
local repair code
MDS codes
extremal bipartite graph
zarankiewicz problem
-
分类号
TP316.4
[自动化与计算机技术—计算机软件与理论]
-
