Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration （VLSI） design. An effective multi-level algorithm for bisecting graph...Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration （VLSI） design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant＇s heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute （ANSI） C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.展开更多
Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annea...Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.展开更多
After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algo...After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algorithm. The code-series (CS) have the holo-information nature, so that both the content and the sign of each gain-term can be determined via the coded method. The principle of this method is simple and it is suited for computer programming. The capability of the computer-aided analysis for switched current network (SIN) can be enhanced.展开更多
We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following a...We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following advantages: the frame of the algorithms is unified, the method is simple, and its implementation and revision are easy.展开更多
In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the foll...In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.展开更多
For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation （BP） algorithm. ...For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation （BP） algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms standard BP algorithm with an obvious performance improvement.展开更多
Hardware/software（HW/SW） partitioning is one of the key processes in an embedded system.It is used to determine which system components are assigned to hardware and which are processed by software.In contrast with p...Hardware/software（HW/SW） partitioning is one of the key processes in an embedded system.It is used to determine which system components are assigned to hardware and which are processed by software.In contrast with previous research that focuses on developing efficient heuristic,we focus on the pre-process of the task graph before the HW/SW partitioning in this paper,that is,enumerating all the sub-graphs that meet the requirements.Experimental results showed that the original graph can be reduced to 67% in the worst-case scenario and 58% in the best-case scenario.In conclusion,the reduced task graph saved hardware area while improving partitioning speed and accuracy.展开更多
The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decis...The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.展开更多
In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify pat...In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.展开更多
Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that...Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.展开更多
To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of ...To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of clustering algorithm has to be improved with the refinement algorithm application. The experiment result demonstrated that the multilevel graph text clustering algorithm is available. Key words text clustering - multilevel coarsen graph model - refinement algorithm - high-dimensional clustering CLC number TP301 Foundation item: Supported by the National Natural Science Foundation of China (60173051)Biography: CHEN Jian-bin(1970-), male, Associate professor, Ph. D., research direction: data mining.展开更多
The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method,...The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method, we provide an O（m） time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees.展开更多
With the globalization of NBA, all eyes on the NBA playoffs are around the world. Ones celebrate the winning of their team which they like. Especially, NBA fans keep on predicting the playoffs game results. However, p...With the globalization of NBA, all eyes on the NBA playoffs are around the world. Ones celebrate the winning of their team which they like. Especially, NBA fans keep on predicting the playoffs game results. However, prediction of winning probability of teams in NBA playoffs is challenging. In order to meet the challenges, we proposed a method using ELO algorithm for prediction and leveraging Graph Database, Neo4j, for implementation. Experiment results show that, the design and implementation of the prediction system could work to some degree.展开更多
We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, whi...We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, which we used to simulate the coupling constant hierarchy for the universe with five fundamental interactions. Moreover, we can explicitly compute the integer Laplacian block matrix associated with any tree plumbing graph. This matrix coincides up to sign with the integer linking matrix (the main topological invariant) of the graph manifold corresponding to the plumbing graph. The need for a special algorithm appeared during computations of these topological invariants of complicated graph manifolds since there emerged a set of special rational numbers (fractions) with huge numerators and denominators;for these rational numbers, the ordinary methods of expansion in continued fraction became unusable.展开更多
The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) t...The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.展开更多
Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical pow...Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. In this paper, we present an?time parallel algorithm with processors for constructing a spanning forest on proper circle graph G on EREW PRAM.展开更多
Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design...Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.展开更多
Blockchain technology,with its attributes of decentralization,immutability,and traceability,has emerged as a powerful catalyst for enhancing traditional industries in terms of optimizing business processes.However,tra...Blockchain technology,with its attributes of decentralization,immutability,and traceability,has emerged as a powerful catalyst for enhancing traditional industries in terms of optimizing business processes.However,transaction performance and scalability has become the main challenges hindering the widespread adoption of blockchain.Due to its inability to meet the demands of high-frequency trading,blockchain cannot be adopted in many scenarios.To improve the transaction capacity,researchers have proposed some on-chain scaling technologies,including lightning networks,directed acyclic graph technology,state channels,and shardingmechanisms,inwhich sharding emerges as a potential scaling technology.Nevertheless,excessive cross-shard transactions and uneven shard workloads prevent the sharding mechanism from achieving the expected aim.This paper proposes a graphbased sharding scheme for public blockchain to efficiently balance the transaction distribution.Bymitigating crossshard transactions and evening-out workloads among shards,the scheme reduces transaction confirmation latency and enhances the transaction capacity of the blockchain.Therefore,the scheme can achieve a high-frequency transaction as well as a better blockchain scalability.Experiments results show that the scheme effectively reduces the cross-shard transaction ratio to a range of 35%-56%and significantly decreases the transaction confirmation latency to 6 s in a blockchain with no more than 25 shards.展开更多
This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linea...This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.展开更多
Over the past era,subgraph mining from a large collection of graph database is a crucial problem.In addition,scalability is another big problem due to insufficient storage.There are several security challenges associa...Over the past era,subgraph mining from a large collection of graph database is a crucial problem.In addition,scalability is another big problem due to insufficient storage.There are several security challenges associated with subgraph mining in today’s on-demand system.To address this downside,our proposed work introduces a Blockchain-based Consensus algorithm for Authenticated query search in the Large-Scale Dynamic Graphs(BCCA-LSDG).The two-fold process is handled in the proposed BCCA-LSDG:graph indexing and authenticated query search(query processing).A blockchain-based reputation system is meant to maintain the trust blockchain and cloud server of the proposed architecture.To resolve the issues and provide safe big data transmission,the proposed technique also combines blockchain with a consensus algorithm architecture.Security of the big data is ensured by dividing the BC network into distinct networks,each with a restricted number of allowed entities,data kept in the cloud gate server,and data analysis in the blockchain.The consensus algorithm is crucial for maintaining the speed,performance and security of the blockchain.Then Dual Similarity based MapReduce helps in mapping and reducing the relevant subgraphs with the use of optimal feature sets.Finally,the graph index refinement process is undertaken to improve the query results.Concerning query error,fuzzy logic is used to refine the index of the graph dynamically.The proposed technique outperforms advanced methodologies in both blockchain and non-blockchain systems,and the combination of blockchain and subgraph provides a secure communication platform,according to the findings.展开更多
基金the International Cooperation Project of Ministry of Science and Technology of P. R. China (GrantNo.CB7-2-01)SEC E-Institute: Shanghai High Institutions Grid
文摘Partitioning is a fundamental problem with applications to many areas including data mining, parellel processing and Very-large-scale integration （VLSI） design. An effective multi-level algorithm for bisecting graph is proposed. During its coarsening phase, an improved matching approach based on the global information of the graph core is developed with its guidance function. During the refinement phase, the vertex gain is exploited as ant＇s heuristic information and a positive feedback method based on pheromone trails is used to find the global approximate bipartitioning. It is implemented with American National Standards Institute （ANSI） C and compared to MeTiS. The experimental evaluation shows that it performs well and produces encouraging solutions on 18 different graphs benchmarks.
基金the National Natural Science Foundation of China (60373089, 60674106, and 60533010)the National High Technology Research and Development "863" Program (2006AA01Z104)
文摘Evolutionary computation techniques have mostly been used to solve various optimization problems, and it is well known that graph isomorphism problem （GIP） is a nondeterministic polynomial problem. A simulated annealing （SA） algorithm for detecting graph isomorphism is proposed, and the proposed SA algorithm is well suited to deal with random graphs with large size. To verify the validity of the proposed SA algorithm, simulations are performed on three pairs of small graphs and four pairs of large random graphs with edge densities 0.5, 0.1, and 0.01, respectively. The simulation results show that the proposed SA algorithm can detect graph isomorphism with a high probability.
文摘After a code-table has been established by means of node association information from signal flow graph, the totally coded method (TCM) is applied merely in the domain of code operation beyond any figure-earching algorithm. The code-series (CS) have the holo-information nature, so that both the content and the sign of each gain-term can be determined via the coded method. The principle of this method is simple and it is suited for computer programming. The capability of the computer-aided analysis for switched current network (SIN) can be enhanced.
文摘We present an edge crossing minimization algorithm for hierarchical graphs based on genetic algorithms, and comparing it with some heuristic algorithms. The proposed algorithm is more efficient and has the following advantages: the frame of the algorithms is unified, the method is simple, and its implementation and revision are easy.
基金Supported by the National Natural Science Foundation of China(60133010,60073043,70071042)
文摘In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.
基金Project supported by the National Natural Science Foundation of China(Grant No.60972046)Grant from the National Defense Pre-Research Foundation of China
文摘For quantum sparse graph codes with stabilizer formalism, the unavoidable girth-four cycles in their Tanner graphs greatly degrade the iterative decoding performance with standard belief-propagation （BP） algorithm. In this paper, we present a jointly-check iterative algorithm suitable for decoding quantum sparse graph codes efficiently. Numerical simulations show that this modified method outperforms standard BP algorithm with an obvious performance improvement.
基金Supported by the National Natural Science Foundation of China (60970016,61173032)
文摘Hardware/software（HW/SW） partitioning is one of the key processes in an embedded system.It is used to determine which system components are assigned to hardware and which are processed by software.In contrast with previous research that focuses on developing efficient heuristic,we focus on the pre-process of the task graph before the HW/SW partitioning in this paper,that is,enumerating all the sub-graphs that meet the requirements.Experimental results showed that the original graph can be reduced to 67% in the worst-case scenario and 58% in the best-case scenario.In conclusion,the reduced task graph saved hardware area while improving partitioning speed and accuracy.
文摘The maximum weighted matching problem in bipartite graphs is one of the classic combinatorial optimization problems, and arises in many different applications. Ordered binary decision diagram (OBDD) or algebraic decision diagram (ADD) or variants thereof provides canonical forms to represent and manipulate Boolean functions and pseudo-Boolean functions efficiently. ADD and OBDD-based symbolic algorithms give improved results for large-scale combinatorial optimization problems by searching nodes and edges implicitly. We present novel symbolic ADD formulation and algorithm for maximum weighted matching in bipartite graphs. The symbolic algorithm implements the Hungarian algorithm in the context of ADD and OBDD formulation and manipulations. It begins by setting feasible labelings of nodes and then iterates through a sequence of phases. Each phase is divided into two stages. The first stage is building equality bipartite graphs, and the second one is finding maximum cardinality matching in equality bipartite graph. The second stage iterates through the following steps: greedily searching initial matching, building layered network, backward traversing node-disjoint augmenting paths, updating cardinality matching and building residual network. The symbolic algorithm does not require explicit enumeration of the nodes and edges, and therefore can handle many complex executions in each step. Simulation experiments indicate that symbolic algorithm is competitive with traditional algorithms.
基金Supported by the National Natural Science Foundation of China (601133010)
文摘In this paper, a new approach for visualizing multivariate categorical data is presented. The approach uses a graph to represent multivariate categorical data and draws the graph in such a way that we can identify patterns, trends and relationship within the data. A mathematical model for the graph layout problem is deduced and a spectral graph drawing algorithm for visualizing multivariate categorical data is proposed. The experiments show that the drawings by the algorithm well capture the structures of multivariate categorical data and the computing speed is fast.
基金supported by the National Science Foundation for Distinguished Young Scholars of China(Grant Nos.61003082 and 60903059)the National Natural Science Foundation of China(Grant No.60873014)the Foundation for Innovative Research Groups of the National Natural Science Foundation of China(Grant No.60921062)
文摘Many real-world networks are found to be scale-free. However, graph partition technology, as a technology capable of parallel computing, performs poorly when scale-free graphs are provided. The reason for this is that traditional partitioning algorithms are designed for random networks and regular networks, rather than for scale-free networks. Multilevel graph-partitioning algorithms are currently considered to be the state of the art and are used extensively. In this paper, we analyse the reasons why traditional multilevel graph-partitioning algorithms perform poorly and present a new multilevel graph-partitioning paradigm, top down partitioning, which derives its name from the comparison with the traditional bottom-up partitioning. A new multilevel partitioning algorithm, named betweenness-based partitioning algorithm, is also presented as an implementation of top-down partitioning paradigm. An experimental evaluation of seven different real-world scale-free networks shows that the betweenness-based partitioning algorithm significantly outperforms the existing state-of-the-art approaches.
文摘To construct a high efficient text clustering algorithm the multilevel graph model and the refinement algorithm used in the uncoarsening phase is discussed. The model is applied to text clustering. The performance of clustering algorithm has to be improved with the refinement algorithm application. The experiment result demonstrated that the multilevel graph text clustering algorithm is available. Key words text clustering - multilevel coarsen graph model - refinement algorithm - high-dimensional clustering CLC number TP301 Foundation item: Supported by the National Natural Science Foundation of China (60173051)Biography: CHEN Jian-bin(1970-), male, Associate professor, Ph. D., research direction: data mining.
基金Supported by the National Natural Science Foundation of China(Grant No.11271365)the Domestic Senior Visiting Scholar Program in Higher Occupation Colleges in Jiangsu Province(Grant No.2014FX075)
文摘The 2-step domination problem is to find a minimum vertex set D of a graph such that every vertex of the graph is either in D or at distance two from some vertex of D. In the present paper, by using a labeling method, we provide an O（m） time algorithm to solve the 2-step domination problem on block graphs, a superclass of trees.
文摘With the globalization of NBA, all eyes on the NBA playoffs are around the world. Ones celebrate the winning of their team which they like. Especially, NBA fans keep on predicting the playoffs game results. However, prediction of winning probability of teams in NBA playoffs is challenging. In order to meet the challenges, we proposed a method using ELO algorithm for prediction and leveraging Graph Database, Neo4j, for implementation. Experiment results show that, the design and implementation of the prediction system could work to some degree.
文摘We present a new algorithm for the fast expansion of rational numbers into continued fractions. This algorithm permits to compute the complete set of integer Euler numbers of the sophisticate tree graph manifolds, which we used to simulate the coupling constant hierarchy for the universe with five fundamental interactions. Moreover, we can explicitly compute the integer Laplacian block matrix associated with any tree plumbing graph. This matrix coincides up to sign with the integer linking matrix (the main topological invariant) of the graph manifold corresponding to the plumbing graph. The need for a special algorithm appeared during computations of these topological invariants of complicated graph manifolds since there emerged a set of special rational numbers (fractions) with huge numerators and denominators;for these rational numbers, the ordinary methods of expansion in continued fraction became unusable.
文摘The vertex connectivity k(G) of a graph G is the minimum number of nodes whose deletion disconnects it. Graph connectivity is one of the most fundamental problems in graph theory. In this paper, we designed an O(n2) time algorithm to solve connectivity problem on circular trapezoid graphs.
文摘Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. In this paper, we present an?time parallel algorithm with processors for constructing a spanning forest on proper circle graph G on EREW PRAM.
文摘Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.
基金supported by Shandong Provincial Key Research and Development Program of China(2021CXGC010107,2020CXGC010107)the Shandong Provincial Natural Science Foundation of China(ZR2020KF035)the New 20 Project of Higher Education of Jinan,China(202228017).
文摘Blockchain technology,with its attributes of decentralization,immutability,and traceability,has emerged as a powerful catalyst for enhancing traditional industries in terms of optimizing business processes.However,transaction performance and scalability has become the main challenges hindering the widespread adoption of blockchain.Due to its inability to meet the demands of high-frequency trading,blockchain cannot be adopted in many scenarios.To improve the transaction capacity,researchers have proposed some on-chain scaling technologies,including lightning networks,directed acyclic graph technology,state channels,and shardingmechanisms,inwhich sharding emerges as a potential scaling technology.Nevertheless,excessive cross-shard transactions and uneven shard workloads prevent the sharding mechanism from achieving the expected aim.This paper proposes a graphbased sharding scheme for public blockchain to efficiently balance the transaction distribution.Bymitigating crossshard transactions and evening-out workloads among shards,the scheme reduces transaction confirmation latency and enhances the transaction capacity of the blockchain.Therefore,the scheme can achieve a high-frequency transaction as well as a better blockchain scalability.Experiments results show that the scheme effectively reduces the cross-shard transaction ratio to a range of 35%-56%and significantly decreases the transaction confirmation latency to 6 s in a blockchain with no more than 25 shards.
文摘This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.
文摘Over the past era,subgraph mining from a large collection of graph database is a crucial problem.In addition,scalability is another big problem due to insufficient storage.There are several security challenges associated with subgraph mining in today’s on-demand system.To address this downside,our proposed work introduces a Blockchain-based Consensus algorithm for Authenticated query search in the Large-Scale Dynamic Graphs(BCCA-LSDG).The two-fold process is handled in the proposed BCCA-LSDG:graph indexing and authenticated query search(query processing).A blockchain-based reputation system is meant to maintain the trust blockchain and cloud server of the proposed architecture.To resolve the issues and provide safe big data transmission,the proposed technique also combines blockchain with a consensus algorithm architecture.Security of the big data is ensured by dividing the BC network into distinct networks,each with a restricted number of allowed entities,data kept in the cloud gate server,and data analysis in the blockchain.The consensus algorithm is crucial for maintaining the speed,performance and security of the blockchain.Then Dual Similarity based MapReduce helps in mapping and reducing the relevant subgraphs with the use of optimal feature sets.Finally,the graph index refinement process is undertaken to improve the query results.Concerning query error,fuzzy logic is used to refine the index of the graph dynamically.The proposed technique outperforms advanced methodologies in both blockchain and non-blockchain systems,and the combination of blockchain and subgraph provides a secure communication platform,according to the findings.
