Research On Equivalence Reduction For Large Graphs

Given a DAG G,The equivalence reduction of G is the compresed graph generated by replacing each of the equivalent node set with one node in the set.Equivalence reduction can effectively compresse the size of graphs,which is one of the classic problems in graph theory and can be used to speed up the speed of query processing.With the development of Internet technology,the scale of the data graphs is increasing so fast,and the existing equivalence reduction algorithm can not deal effectively with the Problem.Our Research in this paper is on equivalence reduction.First of all,through research and analysis of the existing algorithm of the equivalent reduction and we find that the curre nt method is inefficient for its high time complexity O?||V|?|V|+|E|?|?and the space complexity is O?|V|²?.Secondly,the definintion of the equivalence reduction in this paper is based on the transitive reduction of DAG G,and we provide a new definintion of equivalence based neighbor nodes,and proved that neighbors are the same for two nodes in transitive reduction graph of DAG G is equivalent to two nodes have the same transitive closure in the original graph G,which reduced the cost of judging for equivalence nodes.O n this basis,we proposed the definition of set order and node order,then we provide Sort-ER algorithms for efficient solution of equivalence reduction and its time complexity is O(|E^tr|log|V|),the space complexity is O?|V|?.Again,we provide PMR tree which is a spanning tree structure of DAG G,and we proved that the equivalent nodes are brothers in PMR tree.Then we provide PMR-ER algorithm for equivalence reduction based on the PMR tree.The algorithm further reduce the times of comparing nodes and improve efficiency of equivalence reduction.PMR-ER's time complexity is O(|E^tr|logd_max),and its space complexity is O?|V|?.Finally,Our experimental results on 34 real datasets show that our method achieves faster processing time compared with the existing methods.