China
Africa
Explore chapters and articles related to this topic
Big Graph Analytics: Techniques, Tools, Challenges, and Applications
Published in Mohiuddin Ahmed, Al-Sakib Khan Pathan, Data Analytics, 2018
Dhananjay Kumar Singh, Pijush Kanti Dutta Pramanik, Prasenjit Choudhury
A graph is basically a collection of nodes where each node might point to the other nodes. The graphs can be directed like one-way streets or can be undirected like two-way streets in the city. Suppose we want to go through this graph, and specifically suppose we want to do something, like figure out if there is a path from one node to another. There are two common ways of doing this: Breadth-first search (BFS): The BFS is a level-by-level graph traversal algorithm that performs searching on unweighted, undirected graph from the given start vertex and assigns the distance to each vertex.Depth-first search (DFS): The DFS is typically a recursive graph traversal algorithm that explores as deeply as possible using one neighbor before backtracking to other neighbors. DFS does not go through all the edges. The vertices and edges, which depth first search has visited, form a tree (graph spanning tree).
Considerations on the Use of Custom Accelerators for Big Data Analytics
Published in Kuan-Ching Li, Hai Jiang, Albert Y. Zomaya, Big Data Management and Processing, 2017
Vito Giovanni Castellana, Antonino Tumeo, Marco Minutoli, Marco Lattuada, Fabrizio Ferrandi
Prominent examples of designs to accelerate graph traversal and, in general, irregular kernels are the Breadth First Search (BFS) personalities for the Convey HC [42], and the Convey MX systems. The Convey MX, in particular, couples a multithreaded custom processor on the reconfigurable logic with an OpenMP programming environment (CHOMP—Convey Hybrid OpenMP) [43]. Betkaoui et al. [44] discuss reconfigurable hardware methodologies for efficient parallel processing of large-scale graph exploration. These, however, either are custom accelerators for a specific kernel, or employ general-purpose designs on the FPGA. Our approach exploits an HLS approach. In Reference 45, Halstead et al. discuss how to extend the ROCCC framework to support irregular applications, introducing multithreading to tolerate long memory access latencies. However, they do not address atomic memory operations and focus on the simple case study of pointer chasing.
Graph Algorithms I
Published in R. Balakrishnan, Sriraman Sridharan, Discrete Mathematics, 2019
R. Balakrishnan, Sriraman Sridharan
We are interested in traversing a multigraph in a systematic manner, that is, “visiting” the vertices and edges of a multigraph. The vertices are normally variables of type “struct” in the language C or the type “record” in Pascal. These vertices contain information and we are interested in reaching the information stored in the vertices to perform some kind of operation. For example, we may want to update the information in each vertex or simply write the contents of a particular field of each vertex. We shall study two important graph traversal methods: The depth-first searchdepth-first search and breadth-first searchbreadth-first search.
BTLA-LSDG: Blockchain-Based Triune Layered Architecture for Authenticated Subgraph Query Search in Large-Scale Dynamic Graphs
Published in IETE Journal of Research, 2023
G. Sharmila, M. K. Kavitha Devi
A two-level index was proposed [43] which considers the frequent structure mapping and label value aggregation. The main pitfall of this paper is frequent structure mapping index is generated and stored into D for each graph , which has high computational overhead when the index is updated. In the inserting edges and vertice operations, it traverses from the newly inserted vertices or edges. It minimizes the computational cost of the graph traversal, but the index is imbalanced. A fast top-k graph search via representative matrices was presented in [44]. A hierarchical representative matrix index is a space-consuming operation for the large size of datasets. In addition, subtree patterns increase for large query graphs in that case 0-hop and 1-hop result in the false answer set and also consume large storage space. To construct the feature vector similarity between the graph and query, a huge time is needed.
Artificial neural network model for arrival time computation in gate level circuits
Published in Automatika, 2019
In the delay library extracted, three delay values, i.e. minimum, typical and maximum values are given. These values are then modelled as normal distributions with a mean and standard deviation at each gate. They are appended to the nodes of the timing graph. The graph is traversed level by level using graph traversal algorithms such as the breadth-first search (BFS) and simultaneously performing statistical operations such as the statistical maximum and convolution integral on each edge and fan-out of the gates of the timing graph. Circuit levelization is generally performed to ensure that the components in the circuit are arranged in an orderly fashion. It is like one component precedes a second component. Hence the evaluation can be carried out in an orderly fashion. In the proposed work levelization is used to perform faster simulations.
Spatial simulation using abstraction of virtual geographic environments
Published in International Journal of Digital Earth, 2018
Informed topologic graph: The resulting unified map now contains all the semantic information of the input layers, along with the elevation information. This map can be used as an Informed topologic graph (ITG), where each node corresponds to the map's triangles, and each arc corresponds to the adjacency relations between these triangles. Then, common graph algorithms can be applied to this topological graph, and graph traversal algorithms in particular. One of these algorithms retrieves the node, and therefore the triangle, corresponding to given coordinates. Once this node is obtained, it is possible to extract the data corresponding to the position, such as the elevation from the 2.5D triangle, and the semantics from its additional attributes. Several other algorithms can be applied, such as path planning or graph abstraction, but they are out of the scope of this paper and will not be detailed here.