Distributed Algorithm for Tolerance Relation Rough Sets Based on Graph Optimization

Researchers have introduced the theory of tolerance relation rough sets to address the data filtering problem in distributed Incomplete Information Systems (IIS). With the continuous growth in data volume, it is necessary to achieve scalable parallel computing through distributed computing. Consequently, distributed tolerance relation rough sets have emerged, among which the Block Set is the core method for computing approximate sets. However, the Block Set only uses set operations during computation, with no structure between the data, and the process involves a large number of repetitive calculations, resulting in low computational efficiency. This study proposes a Tolerance Relation rough sets Distributed (TRDG) algorithm, which is based on graph optimization, to address this issue. Using the existing concepts of reliable and disputed elements, a hierarchical directed acyclic graph is constructed with data in the IIS as nodes and asymmetric tolerance relationships as edges. The graph structure is used to organize the data. To improve the computational efficiency of the Block Set in distributed environments, the study proposes a strategy that uses the nearest tolerance relationship instead of the general asymmetric tolerance relationship to remove redundant edges, simplify the graph structure, and obtain a Block Set based on the path from reliable elements to zero-degree disputed elements. Distributed graph optimization and path search algorithms are then implemented on the Spark platform, which ultimately completes the design of the TRDG algorithm. Experimental results show that the TRDG algorithm exhibits good parallel acceleration performance. Compared to traditional general tolerance rough approximation set solving algorithms, TRDG can save computing resources, increase the average computing speed by approximately 40 times, and increase the amount of data that can be processed by more than 50 times.