计算机工程

作者：吴正江, 武星晨, 连涛, 王梦松

单位：河南理工大学计算机科学与技术学院, 河南 焦作 454003

关键词：有向无环图,Block,容差关系粗糙集,最近容差关系,近似集分布式计算

基金：国家自然科学基金(61972134); 国家自然科学基金(62372156)

为了处理分布式的不完备信息系统(IIS)中的数据筛选问题, 研究人员引入了容差关系粗糙集理论。随着数据量的不断增长, 需要通过分布式计算来实现可扩展的并行化计算, 因此分布式容差关系粗糙集被提出, 其中Block Set是计算近似集的核心方法。然而, Block Set在计算时仅使用集合运算, 数据之间没有结构, 过程涉及大量重复计算, 导致计算效率不高。针对这一问题, 提出一种基于图优化的容差关系粗糙集分布式(TRDG)算法。引用已有的可靠元和争议元的概念, 以IIS中的数据为结点, 以非对称容差关系为边, 构建具有层次关系的有向无环图, 使用图结构来组织数据。为了提高Block Set在分布式环境中的计算效率, 提出使用最近容差关系代替一般非对称容差关系的策略, 用于删除冗余边, 简化图结构, 并基于可靠元到零出度争议元的路径来得到Block Set。然后, 在Spark平台上实现分布式的图优化算法和路径搜索算法, 最终完成TRDG算法的设计。实验结果表明, TRDG算法具有良好的并行加速性能, 和传统的容差关系粗糙近似集求解算法相比, TRDG能够节省计算资源, 计算速度平均提高了40倍, 可处理的数据量也增加了50倍以上。

来源：2026年第3期

《计算机工程》期刊编辑部

查看计算机工程杂志2026年第3期