Search

Shortest path searching is very important in some special cases such as medical emergencies, fire brigade, etc. An optimal path may be defined on a number of factors such as least distance/time or traffic density in stochastic road networks. Hence, there is no proper definition of an optimal path within the underlying constraints. One approach taken as an answer to this question is to find a path with the minimum expected travel time. For this, the approach taken is to construct a map of a city/town. This map is created using graphs where the nodes and edges represent the landmarks/locations and roads respectively. Traversal of the graph denotes traversal among the city/town. There are multiple graph traversal algorithms such as Best First Search, Bellman-Ford, and Dijkstra; but an optimal algorithm that finds the shortest path with the least time complexity should be chosen and implemented. Hence the A* algorithm is ideal. The benefit of using the A* algorithm is that it provides the optimum path while adhering to the underlying constraints. While A* algorithm is an optimum path-finding algorithm, it works ideally when the graph created has accurate measurements. Scaling is also not an issue as space complexity increases with the size of the graph. A small part of The city of Bengaluru is taken as the map consisting of 83 locations in which 24 locations consist of the possible destinations and an ambulance is considered as the vehicle of traversal to eliminate underlying constraints such as traffic density and variable speed.

The skewed degree distribution of real-world graphs is the main source of poor locality in traversing all edges of the graph, known as Sparse Matrix-Vector (SpMV) Multiplication. Conventional graph traversal methods, such as push and pull, traverse all vertices in the same manner, and we show applying a uniform traversal direction for all edges leads to sub-optimal memory locality, hence poor efficiency. This paper argues that different vertices in power-law graphs have different locality characteristics and the traversal method should be adapted to these characteristics.To solve this problem, we propose to inspect the number of destination and source vertices in selecting a cache-compatible traversal direction for each type of vertex. We introduce in-Hub Temporal Locality (iHTL), a structure-aware SpMV that combines push and pull in one graph traversal, but for different vertex types. iHTL exploits temporal locality by traversing incoming edges to in-hubs in push direction, while processing other edges in pull direction.The evaluation shows iHTL is 1.5-2.4 times faster than pull and 4.8-9.5 times faster than push in state-of-the-art graph processing frameworks such as GraphGrind, GraphIt and Galois. More importantly, iHTL is 1.3-1.5 times faster than pull traversal of state-of-the-art locality optimizing reordering algorithms such as SlashBurn, GOrder, and Rabbit-Order. https://blogs.qub.ac.uk/GraphProcessing/exploiting-in-hub-temporal-locality-in-spmv-based-graph-processing/

Complete Event Trend (CET) detection over large-scale event streams is important and challenging in various applications such as financial services, real-time business analysis, and supply chain management. A potential large number of partial intermediate results during complex event matching can raise prohibitively high memory cost for the processing system. The state-of-the-art scheme leverages compact graph encoding, which represents the common sub-sequences of different complex events using a common sub-graph to achieve space efficiency for storing the intermediate results. However, we show that such a design raises unacceptable computation cost for the graph traversal needed whenever a new event comes. To address this problem, in this paper, we propose a novel attribute-based indexing (ABI) graph model to represent the relationship between events. By classifying the predicates and constructing the graph based on both the comparators in the predicates and the attribute values of the events, we achieve parallel event stream processing and efficient graph construction. Our design significantly reduces the total computation cost of graph construction from O(n2) to O(nlog(m)), where n is the number of events and m is the number of the attribute vertices. We further design several efficient traversal-based algorithms to extract CETs from the graph. We implement our design and conduct comprehensive experiments to evaluate the performance of this design. The results show that our design wins a couple of orders of magnitude back from state-of-the-art schemes.

Graph analytics are widely used in real-world applications, and GPUs are major accelerators for such applications. However, as graph sizes become significantly larger than the capacity of GPU memory, the performance can degrade significantly due to the heavy overhead required in moving a large amount of graph data between CPU main memory and GPU memory. Some existing approaches have tried to exploit data locality and addressed the issues of memory oversubscription on GPUs. However, these approaches have yet to take advantage of the data reuse cross iterations because of the data sizes in most large-graph analytics. In our studies, we have found that in most graph applications the graph traversals exhibit a roughly sequential scan over the graph data with an extremely large memory footprint. Based on the observation, we propose a novel framework, called Ascetic, to exploit temporal locality with very long reuse distances. In Ascetic, the GPU memory is divided into a Static Region and an On-demand Region. The static region can exploit data reuse across iterations. The on-demand region is designed to load the data requested in the iteration of the graph traversal while not found in the static region. We have implemented a prototype of the Ascetic framework and conducted a series of experiments on performance evaluation. The experimental results show that Ascetic can significantly reduce the data transfer overhead, and allow more overlapped execution between GPU and CPU, which leads to an average of 2.0x speedup over a state-of-the-art approach.

Summary Influential node identification plays a significant role in understanding network structure and functions. Here we propose a general method for detecting influential nodes in a graph-traversal framework. We evaluate the influence of each node by constructing a breadth-first search (BFS) tree in which the target node is the root node. From the BFS tree, we generate a curve in which the x axis is the level number and the y axis is the cumulative scores of all nodes visited so far. We use the area under the curve value as the final influence score of the target node. Experimental results on various networks across different domains demonstrate that our method can be significantly superior to widely used centrality measures on the task of influential node detection., Graphical abstract, Highlights • We propose an influential node detection method, TARank, in a graph-traversal framework • We evaluate the influence of each node by constructing a breadth-first search tree • TARank is capable of enhancing existing centrality measures • TARank can yield new, yet effective, centrality measures as well, The bigger picture The discovery of influential nodes is a fundamental research issue in network science. To quantify the influence of each node in a network, various methods have been presented in the literature. To the best of our knowledge, no previous research efforts address the influential node identification problem from a graph-traversal perspective. To fulfill this void, we propose the TARank method that integrates the information collected from the breadth-first search tree to identify influential nodes. The formulation under the graph-traversal framework opens the door to a fundamentally new type of method of influential node identification. In the future, more effective recognition methods can be expected to be constructed based on this general framework. Since empirical studies have validated the effectiveness of TARank, it would be plausible to employ this method in different applications to reveal new findings., To identify influential nodes, many methods have been proposed during the past decades. However, no single method can always achieve the best performance across different networks, and it is still necessary to develop new methods based on some principles that remain unexplored. Here we present a novel method, TARank, which tackles the influential node identification issue from a graph-traversal perspective. TARank is a general framework that can both unify some existing methods and create many new variants.

A k nearest neighbors (kNN) query finds k closest points-of-interest (POIs) from an agent's location. In this paper, we study a natural extension of the kNN query for multiple agents, namely, the Aggregate k Nearest Neighbors (AkNN) query. An AkNN query retrieves k POIs with the smallest aggregate distances where the aggregate distance of a POI is obtained by aggregating its distances from the multiple agents (e.g., sum of its distances from each agent). We propose a novel data structure COLT (Compacted Object-Landmark Tree) which enables efficient hierarchical graph traversal and utilize it to efficiently answer AkNN queries. Our experiments on real-world and synthetic data sets show that our techniques outperform existing approaches by more than an order of magnitude in almost all settings.

The public transportation graph facilitates efficient trip planning considering various passenger requests such as distance, waiting time, travel time, self-transportation, and number of transfers. This paper proposes an approach to normalize the edge weight in the public transportation graph and presents examples of graph traversal-based solutions to solve trip planning problems in public transportation. The proposed solutions are implemented and tested on the synthetic data to show the improvements and apply the algorithms.

Cache efficiency is an important factor in the performance of graph processing due to the irregular memory access patterns caused by the sparse nature of graphs. To increase the cache hit rate, prior studies proposed a variety of preprocessing approaches based on the reordering, which permutes the vertexes’ labels to improve the locality of graph structures. However, the locality enhancement of existing reordering approaches does not bring much performance benefit in depth-first traversal, which is widely adopted in a majority of graph processing applications. Furthermore, the state-of-the-art reordering approach suffers from an obvious overhead on preprocessing which will greatly limit the application of their approach. In this paper, we propose SeqDFS, a depth-first graph traversal method that optimizes the cache efficiency by adjusting the order of vertexes visited and can be further extended to dynamic scenarios. We conduct extensive experiments on 16 real-world datasets and 3 representative depth-first graph applications, of which the results show that our proposal achieves a significant speed-up on both directed and undirected graphs.

The indexing and retrieval of multimedia content is generally implemented by employing feature graphs. These graphs typically contain a significant number of nodes and edges to reflect the level of detail in feature detection. A higher level of detail increases the effectiveness of the results, but also leads to more complex graph structures. However, graph traversal-based algorithms for similarity are quite inefficient and computationally expensive, especially for large data structures. To deliver fast and effective retrieval especially for large multimedia collections and multimedia big data, an efficient similarity algorithm for large graphs in particular is desirable. Hence, in this paper, we define a graph projection into a 2D space (Graph Code) and the corresponding algorithms for indexing and retrieval. We show that calculations in this space can be performed more efficiently than graph traversals due to the simpler processing model and the high level of parallelization. As a consequence, we demonstrate experimentally that the effectiveness of retrieval also increases substantially, as the Graph Code facilitates more levels of detail in feature fusion. These levels of detail also support an increased trust prediction, particularly for fused social media content. In our mathematical model, we define a metric triple for the Graph Code, which also enhances the ranked result representations. Thus, Graph Codes provide a significant increase in efficiency and effectiveness, especially for multimedia indexing and retrieval, and can be applied to images, videos, text and social media information.

Wireless rechargeable sensor network includes three parts: data center DC, sensor and mobile charger MC. The work of sensor requires battery to provide energy. Based on this, this paper focuses on how to design a reasonable charging circuit for a single mobile charger starting from the data center, and the minimum capacity of the battery to ensure the normal operation of each sensor, and thus expand to multiple mobile chargers. In the case of a mobile charger, in order to minimize the energy consumption of the mobile charger on the road, the driving distance of the mobile charger should be minimized. The paper use the earth's radius and longitude and latitude of each sensor can calculate the distance between each sensor, thus the problem can be converted to a given weighted network diagram to find starting from the data center will all vertices in the network graph traversal only again back to the data center makes the problem of shortest distance, the simulation using the simulated annealing algorithm, thus it is concluded that the optimum route scheme. And then normal operation of the system need to make sure that the process of finish a lap mobile charger after the sensor has not less than the minimum battery capacity as the constraint condition, the multi-objective problem to single objective problem, the simplified calculation is further transformed into linear programming problems, setting up reasonable charging rate r, movement speed v, battery capacity low f, sensor is obtained by solving our minimum battery capacity.

GPU's massive computing power offers unprecedented opportunities to enable large graph analysis. Existing studies proposed various preprocessing approaches that convert the input graphs into dedicated structures for GPU-based optimizations. However, these dedicated approaches incur significant preprocessing costs as well as weak programmability to build general graph applications. In this paper, we introduce SAGE, a self-adaptive graph traversal on GPUs, which is free from preprocessing and operates on ubiquitous graph representations directly. We propose Tiled Partitioning and Resident Tile Stealing to fully exploit the computing power of GPUs in a runtime and self-adaptive manner. We also propose Sampling-based Reordering to further optimize the memory efficiency of SAGE through a lightweight and effective node reordering technique on the fly. Extensive experiments demonstrate that SAGE can achieve superior graph traversal performance over existing approaches under different architectural scenarios, i.e., single-GPU, out-of-core, and multi-GPU.

Shortest path finding is the building block of various applications in road networks and the index-based algorithms, especially hub labeling, can boost the query performance dramatically. However, the traffic condition keeps changing in real life, making the pre-computed index unable to answer the query correctly. In this work, we adopt the state-of-the-art tree decomposition-based hub labeling as the underlying index, and design efficient algorithms to incrementally maintain the index. Specifically, we first analyze the structural stability of the index in dynamic road networks which enables us to concentrate on label value maintenance. We then introduce the minimum weight property and minimum distance property to guarantee the index correctness without graph traversal. Moreover, we propose the star-centric paradigm for tracing index change and design various pruning techniques to further accelerate the index maintenance. Finally, we extend our algorithms to batch mode for shared computation, extend to structural maintenance for full types of update, and generalize to all kinds of TDHL. Our experimental results validate the superiority of our proposals over existing solutions on both index maintenance and query processing.

Is it possible to predict the execution time of a spatially distributed hydrological model by only examining the mesh? This article investigates this question by using a benchmark mesh with the Penn State Integrated Hydrologic Model (PIHM). The benchmark mesh triangles are reordered using ten different graph search algorithms that treat each mesh triangle as a graph root to select the remaining triangles in the watershed domain. PIHM then executed these graph-reordered meshes to create performance datasets to find which graph search algorithm and triangle root combinations improved PIHM's execution time. The performance datasets were used to train and classify seven different machine learning (ML) models to predict the fastest execution times. Analyzing these ML results facilitated a strategy for end users of the HydroTerre expert system to choose meshes that improve execution times for their hydrological science research with PIHM.

The Hungarian algorithm solves the linear assignment problem in polynomial time. A GPU/CUDA implementation of this algorithm is proposed. GPUs are massive parallel machines. In this implementation, the alternating path search phase of the algorithm is distributed by several blocks in a way to minimize global device synchronization. This phase is very important and has a big contribution to the execution time. Other advanced features also implemented are: parallel graph traversal; the parallel detection of multiple alternating paths in a single iteration; a simplified and fast matrix compression that stores the zeros of the slack matrix, resulting in very fast graph traversal; highly optimized reductions for the initial slack matrix calculation and update. This results in a fast implementation for moderate size problems.

Graphs are widely used to model data in many application domains. Thanks to the wide spread use of GPS-enabled devices, many applications assign spatial attributes to graph vertexes (e.g., geographic knowledge bases, geo-tagged social media). Graph database systems such as Neo4j and Titan are commonly used to manage and query graph data. Even though an off-the-shelf graph database system allows users to define spatial location semantics on vertexes and edges, existing graph query processors are not natively optimized for spatial predicates. The paper proposes GeoExpand—a query operator that adds spatial data awareness to a graph database management system. GeoExpand allows efficient execution of graph queries that involve spatial predicates. The proposed operator makes use of spatial bitmap entries stored as properties in the graph. GeoExpand leverages such bitmap entries to possibly terminate the graph traversal process early and hence reduces the query latency. Since the spatial bitmap entries are represented using a light-weight data structure, they do not add a lot of storage or maintenance overhead. That makes GeoExpand a practical solution. Experiments based on implementation inside the core kernel of Neo4j prove that the GeoExpand operator exhibits up to two orders of magnitude better query response time than the classic Expand operator used in Neo4j.

In various domains, e.g. robotics or autonomous driving, automated path planning for conflict-free movements of the participating vehicles, i.e. robots, cars or other mobile units is an essential task on the navigation level. Especially in crowded scenarios in which many vehicles share a common operation area together with other static or dynamic obstacles, finding a set of conflict-free paths for all vehicles is a challenging navigation task that is crucial for fully autonomous vehicles. In this work we propose a decentralized path planning algorithm for such scenarios which focuses on the cooperative negotiation of conflict-free paths. The path planning on navigation level is realized with an innovative graph search algorithm based on A* that incorporates dynamic obstacles (e.g. manually operated vehicles and other autonomous mobile units) and enables the autonomous vehicles to change speed. Furthermore, the framework suggests a decentralized approach, in which each vehicle performs its own path planning locally. Communication between the mobile units allows them to cooperatively negotiate conflict-free paths for all autonomous vehicles participating in the framework. The resulting iterative process of calculating new paths and negotiating a feasible solution set for all vehicles is designed to yield a deterministic solution within a finite number of iterations. We furthermore provide promising simulation results for this framework with test scenarios involving many autonomous vehicles and challenging obstacle formations.

One of the effective methods to reduce the risk of load shedding and its subsequent blackout is to evaluate the risk of cascading outages and detection of key links in a power system. This risk assessment is getting more complicated considering the plans for integration of high wind energy. Therefore, in this study, a new sequential time approach has been proposed to evaluate risk of cascading outages considering the high penetration of correlated wind farms. The cascading processes are investigated using the extended OPA model using the graph traversal algorithm. Therefore, the problem of non-convergence situations caused by the island formation is resolved. To deal with the future wind farms integration, a correlation is defined between them by a proposed method based on the Copula theory. The numerical results confirm that in evaluation of risk, the limited scenarios cannot always be reliable. The extended OPA model is then compared with a simple OPA to confirm the importance of islanding detection in the cascade simulation. Different aspects of cascading outages, i.e. fractional load shedding, cascade propagation level and number of line interruptions have been investigated. Finally, the impact of wind penetration and correlation of wind farms on results have been presented.

Multi-robots are used in hospital for the delivery service. To increase the delivery efficiency, an appropriate multi-robots path planning algorithm is required. This study explains a mixed path planning algorithm for multi-robots in structured hospital environment which combines the ‘corridor path planning’ and ‘room path planning’, ‘corridor path planning’ uses graph search algorithm to plan the path in corridor for multiple hospital robots, and it uses the strongly connected digraph to describe corridor environment, so it could simplify the multi-robots path planning problem. While the ‘room path planning’ uses the artificial potential field method to plan the path in room for multiple hospital robots, it makes the hospital robot move flexibly in the room, so the robot could avoid the obstacle and other robots more flexibly. The algorithm is tested by simulation, and the result shows that mixed path planning algorithm makes the robot move fast in the corridor environment and move flexibly in the room environment.

Task scheduling is the key to the full utilization of heterogeneous cloud capabilities for parallel processing of big graphs. Most graph processing systems adopt single-granularity scheduling mechanisms without considering the heterogeneity of the cloud, leading to poor performance. To alleviate it by learning from the excellent directed acyclic graph (DAG)-based scheduling techniques accumulated in traditional parallel computing, we first present a streaming DAG-construction heuristic. It transforms a big graph along with graph traversal algorithms to be carried out into a DAG. We then propose a three-phase heterogeneous-aware cluster-scheduling algorithm to schedule the DAG into a heterogeneous cloud for parallel processing. In the first phase, we design a parallel linear clustering algorithm to cluster the DAG into a series of linear clusters with different granularities. In the second phase, we design a heterogeneous-aware load balancing algorithm to map these clusters to different computational nodes of the cloud. In the last phase, we design a task ordering algorithm to assigns these clusters as-early-as-possible start times. The experimental results show that our scheme can generate high-quality schedules and improve the efficiency and performance of parallel processing of big graphs in the heterogeneous cloud.

Directed hypergraphs are an extension of directed graphs in which edges connect a set of source nodes to a set of target nodes. Unlike graphs, they can capture complex relations in network structures that go beyond the union of pairwise associations. They are widely applied in a variety of different domains, such as finding pathways in chemical reaction networks or minimising propositional Horn formulas. Calculating optimal paths in hypergraphs in the general case is an NP-hard problem, which can be solved in polynomial time only when utility functions hold specific properties. We present in this paper an approach to search for optimal hypergraph paths in the general case based on ant colony optimisation. Ant colony optimisation is an evolutionary meta-heuristic that is particularly suitable to combinatorial problems, such as optimal graph traversal. We present an experimental evaluation using artificially-generated hypergraphs and discuss innovative applications of the proposed approach in the domains of industrial engineering and chemical informatics.

Multi-relation graphs intuitively capture the heterogeneous correlations among real-world entities by allowing multiple types of relationships to be represented as entity-connecting edges, i.e., two entities could be correlated with more than one type of relationship. This is important in various applications such as social network analysis, ecology, and bio-informatics. Existing studies on these graphs usually consider an edge label constraint perspective, where each edge contains only one label and each edge is considered independently. For example, there are lines of research focusing on reachability between two vertices under a set of edge label constraints, or finding paths whose consecutive edge labels satisfy a user-specified logical expression. This is too restricted in real graphs, and in this work, we define a generic correlation constraint on multi-relation graphs from the perspective of vertex correlations, where a correlation can be defined recursively. Specifically, we formalize and investigate the shortest path problem over large multi-relation graphs in the presence of both necessity and denial constraints, which have various real applications. We show that it is nontrivial to apply conventional graph traversal algorithms (e.g., BFS or DFS) to address the challenge. To effectively reduce the search space, we propose a Hybrid Relation Encoding method, a.k.a. HyRE, to encode both topological and relation information in a compact way. We conduct extensive experiments over large real-world graphs to validate the effectiveness and efficiency of the proposed solution.

Coverage of an area is required for a large variety of robotics and manufacturing applications, such as environment monitoring, home cleaning, search and rescue operations, machining, delivery, additive manufacturing and even for 3D terrain reconstruction. In this work, we present highly flexible algorithms that can be used for coverage and graph traversal. Although our methods take advantage of variable-sized Voronoi cells, by which regular, irregular and complex geometries can be easily composed, it is not limited to Voronoi diagrams and can be applied for any connected graph. After the construction of the Voronoi diagram, an Eulerian graph is generated. Then, three algorithms are elaborated for the traversal of it. Two of those algorithms traverse the graph continuously, leading to Eulerian cycles. On the other hand, one algorithm requires switching positions from time to time, which we call fast travel. Additionally, we describe the phenomenon of traversing the same edge twice in a row, i.e., u turn, and draw a conclusion to emphasize the importance of this specific problem.

Given a directed acyclic graph (DAG), a k-hop reachability query u → ?k is used to answer whether there exists a path from u to v with length ≤ k. Answering k-hop reachability queries is a fundamental graph operation and has been extensively studied during the past years. Considering that existing approaches still suffer from inefficiency in practice when processing large graphs, we propose a novel labeling scheme, namely HT, to accelerate k-hop reachability queries answering. HTuses a constrained 2hop distance label to maintain the length of shortest paths between a set of hop nodes and other nodes, and for the remaining reachability information, HT uses a novel topological level to accelerate graph traversal. Further, we propose to enhance HT by two optimization techniques. The experimental results show that compared with the state-of-the-art approaches, HT works best for most graphs when answering k-hop reachability queries with small index size and reasonable index construction time.

Detecting strongly connected components (SCC) is a practical graph analytics algorithm widely used in many application domains. To accelerate SCC detection, parallel algorithms have been proposed and implemented on GPUs. However, existing GPU implementations show unstable performance for various graphs, especially for real-world graphs, as these implementations do not have a clear understanding of the graph properties. In this paper, we analyze that graphs in SCC detection usually exhibit (1) skewed component sizes (the static property) and (2) dynamically changed graph structure (the dynamic property). To deal with these irregular graph properties, we propose a hybrid method that divides the algorithm into two phases and exploits different levels of parallelism for different-sized components. We also customize the graph traversal strategies for each phase to handle the dynamically changed graph structure. Our method is carefully implemented to take advantage of the GPU hardware. Evaluation with diverse synthetic and real-world graphs shows that our method substantially improves existing GPU implementations, both performance-wise and applicability-wise. It also achieves an average speedup of 5.6 × and 1.5 × over the sequential and OpenMP implementations on the CPU respectively.

Relabeling algorithms aim to improve the poor memory locality of graph processing by changing the order of vertices. This paper analyses the functionality of three state-of-the-art relabeling algorithms: SlashBurn, GOrder, and Rabbit-Order for real-world graphs. Find a comprehensive version of this paper in: https://blogs.qub.ac.uk/graphprocessing/locality-analysis-of-graph-reordering-algorithms/ .

The purpose of this article is to conduct research on graphics processing (GP) methods based on DL in the context of big data (BD). First, this article studies the characteristics of current BD and investigates related applications. Then based on DL, this article proposes a method of processing graphics content. This method uses three different DL network structures to extract graphic features. In this paper, the OpenMP parallel model is used to optimize the graph search algorithm in parallel on the CPU platform, and the algorithm is optimized in parallel by using the principle of program locality, reducing synchronization overhead and load balancing. Thirdly, in view of the irregularity of the memory access of the graph search algorithm, the FPGA algorithm hardware accelerator is customized using BD technology. Finally, it introduces the development tools of DL algorithm hardware acceleration, and compares them with traditional processing methods. Comparative experiments show that the image processing method based on DL proposed in this paper has an average recognition rate of about 10% higher than traditional processing methods, and has better results, providing an important reference for the development of image processing.

Technological advancements and the changing needs drive the process workflow, meeting the need-of-the-hour requirements, and calibrating system components. While the perception evolves, the fundamental principles stay put and wrap around generational disparities. In a changing scenario of the physical market to an e-commerce site, the recommendation systems have had substantial roles. The present systems customarily use the item or user profiles for recommendations. The existing recommendation systems rely heavily on data and learning algorithms. An improved recommendation system given by considering the query’s semantics rather than using only historical data of numerous worldwide queries can create a paradigm shift in the technologies involved in computer recommendations. Bag of science attempts to take on this challenge. The model dwells on inferring a query’s meaning in all contexts to create an order in which the words relate. By constructing a word definition graph, the methodology explores the possibility of enhancing the recommendation systems to improve the e-commerce platforms’ business. The paper presents the model’s architecture with its chief components, including a parser and scraper, graph generator, graph traversal, and results. The model presents the traversal results and analysis of the constructed e-commerce graphs using hops as the threshold metric. The paper also presents the model’s abstract data type to make it applicable and extend to other domain contexts that involve query engines and need recommendations.

Graph database (GDB) is one of the best approaches for enabling efficient management of relationships in the graph. It retains the shape of the graph to retrieve the required nodes through their interconnections. GDBs have an attractive characteristic called index-free adjacency, enabling users to traverse one edge at a fixed computing cost for vast and complex graph data. However, it is quite likely that GDBs cannot avoid reaching already-scanned nodes from different start nodes by repeatedly traversing edges that have a specific relationship type. This is because GDBs cannot consider the node degrees of each node in a graph. Consequently, when a GDB reaches a hub, the number of nodes that need to be arrived at by traversing different edges increases depending on the hub’s adjacent nodes. Therefore, an inefficient process increases the cost of extracting a sub-graph in conventional GDBs. Accordingly, in this paper, we propose an efficient approach to repeatedly traversing edges belonging to a specific relationship type by distinguishing between hub s and other nodes. In particular, our approach manages repetition path s from each hub in addition to a list of the adjacent node in a conventional GDB; this GDB aims to enable us to manage a real-world network effectively.

In this survey we have compared five different path finding algorithms, namely, Dijkastra’s algorithm, A* Search, Greedy Best First Search, Breadth First Search and Depth First Search on the basis of the following criteria: Complexity: It refers to the rate at which the execution time grows with respect to the input size. Reliability: It refers to whether the algorithm is able to guarantee the shortest path. Weighted/unweighted: Some algorithms are not suited for weighted graphs and thus have a major limitation. Their respective advantages and disadvantages have also been discussed.

© 2021, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.A* (A-star) is a computer algorithm that is widely used in pathfinding and graph traversal to effectively compute optimal solutions. The algorithm uses the best first search and finds the lowest cost path from a given start node to a target node. It follows a path of the lowest known heuristic cost, keeping a sorted priority queue of alternate path segments along the way. It is more accurate than greedy best-first search algorithm because it takes into account already moved nodes. Each iteration calculates the cost from the starting node and adds the heuristic cost to the target node. The cost of paths can be given based on truth, indeterminate and false membership functions. In the graph, cost path and heuristic cost paths can be expressed with fuzzy numbers. The contribution of this study to the existing literature comes from the usage of A* algorithm to find the shortest path of a graph with arcs expressed in single valued neutrosophic numbers. A numerical example is given to show the usefulness of proposed approach.

Rock crushing task for excavators has harsh working environments. With the development of vision sensors and intelligent algorithms, it is possible to achieve autonomous intelligent mining for unmanned excavators. This paper presents an autonomous path planning system for mining robots based on stereo vision. For semantic obstacles such as excavators and loaders in the quarry environment, a recognition network for construction vehicles is trained. The positions and sizes of the construction vehicles are determined by stereo vision. To avoid the rollover hazard that may occur, a gradient map is derived from the elevation map. The traffic cost considering the energy consumption is adopted to build a graph, where the Dijkstra graph search algorithm is used to obtain the path with the lowest cost. Finally, ROS and Gazebo are utilized to simulate and verify the autonomous path planning system. The results show that the proposed system based on stereo vision can complete the autonomous intelligent navigation task in the quarry environment.

Differentiable neural computers extend artificial neural networks with an explicit memory without interference, thus enabling the model to perform classic computation tasks such as graph traversal. However, such models are difficult to train, requiring long training times and large datasets. In this work, we achieve some of the computational capabilities of differentiable neural computers with a model that can be trained very efficiently, namely an echo state network with an explicit memory without interference. This extension enables echo state networks to recognize all regular languages, including those that contractive echo state networks provably can not recognize. Further, we demonstrate experimentally that our model performs comparably to its fully-trained deep version on several typical benchmark tasks for differentiable neural computers., In print at the special issue 'New Frontiers in Extremely Efficient Reservoir Computing' of IEEE TNNLS

Video is a very expressive medium, able to capture a wide variety of information in different ways. While there have been many advances in the recent past, which enable the annotation of semantic concepts as well as individual objects within video, their larger context has so far not extensively been used for the purpose of retrieval. In this paper, we introduce the first iteration of VideoGraph, a knowledge graph-based video retrieval system. VideoGraph combines information extracted from multiple video modalities with external knowledge bases to produce a semantically enriched representation of the content in a video collection, which can then be retrieved using graph traversal. For the 2021 Video Browser Showdown, we show the first proof-of-concept of such a graph-based video retrieval approach.

The standard approach to bundle routing in delay-tolerant networks with predictable contacts uses a graph traversal algorithm to search for paths where the graph’s nodes represent the presumed and non-expired contact opportunities and the edges the waiting time for the next contact to occur. However, unforeseen systemic issues may introduce random contact holdups, i.e., the start time of certain contacts may be delayed, which may lead to lower performance than anticipated. An analysis of random contact holdups and their impact on the probabilistic optimal routing of bundles over parallel, non-overlapping substrate paths are provided. The study brings new insight into the consequences of unforeseen divergences between the planned contacts and their realization, which may help to improve the design of future DTN protocols.

Many real-world applications need to know the distances between some or all pairs of vertices in a large graph, but the existing distributed single-source shortest path (SSSP) solution can not efficiently handle the problem of such multi-source computation. While, distributed multi-source shortest path (MSSP) has not attracted enough attention. This paper thereby proposes a distributed multi-source shortest path algorithm by scheduling source vertices in different batches and sharing graph traversal operations in the same batch for efficiency (B-MSSP), which effectively solves the performance bottleneck of MSSP on big graphs. To correctly run multi source vertices in the same batch, a message cluster mechanism is designed to effectively manage the communication. A further analysis reveals that the overall performance of B-MSSP is affected by the batch size. Thus, an adaptive cost-benefit model is proposed to quickly and easily select a proper batch size for better performance. Extensive experiments over lots of real graphs validate the efficiency and effectiveness of our proposals.

Recommender systems hoard appropriate suggestions guided by the interactions and previous choices of the users. In a world of the ever-growing amount of data, we are overpopulated with undesired information, which is making it difficult to operate or choose. Hence, we require a recommender system that is enough capable to deduce desired suggestions which can be valuable for the users. Thus, they are rising in popularity and becoming part and parcel of day-to-day activities in our general life. Here, in this paper, we implement the recommender system, which is conceptualized on a hybrid filtering algorithm that helps in dealing with limitations of both content and collaborative filtering reinforced with artificial bee colony optimization along with k- nearest neighbor for better performance. For this purpose, we used MovieLens dataset, which contains information regarding users, movies, and ratings given by the users. Here, we gathered a pre-filled user project scoring matrix and have compared multiple models of recommender systems for their precision and recall factor. We are using a recommender system based on graph database which uses graph traversal and pathfinding algorithms to establish relations and hence is more robust and faster in implementation. The thickness of the edges connecting movie nodes and the indegree of a movie node specifies the recommendation limit of the movie. The experiment results on MovieLens dataset establishes scope for future scalable models and delivers competent outcomes brought in comparison with traditional systems. Preliminary results show improvement of 9% in precision and 3% improvement in recall over traditional systems.

Knowledge graphs which often integrate heterogeneous data can be exploited for serendipitous knowledge discovery using appropriate integration paradigms. We posit that a semi-structured querying model which blends the benefits of structured and unstructured querying could offer a sweetspot. However, there is a need for effective algorithmic techniques for such query processing.In this paper, we propose a class of constrained subgraph connection structure discovery queries whose specification is only partially structured. Graph theoretically, these amount subgraph homeomorphism problems that tolerate flexibility in graph structure matching. Central to achieving the goals of performance and scale of query evaluation is the use of a path algebraic framework rather than a graph theoretic framework. The path algebraic framework is coupled with some efficient data encoding, representation and indexing. Together, these allow more effective querying than using the traditional graph traversal style algorithms, demonstrated by a comparative evaluation.

In recent decades, visual programming tools have focused on scientific workflow tasks. However, the current focus has shifted to machine learning tasks, which are most often amenable to unification. The existing solutions in this area demonstrate many alternatives with the possibility of using models from various machine learning packages. The proposed solution is based on the concept of minimal graphical notation, where all typical operations on data and machine learning models are possible. Another distinguishing feature of the proposed solution is the explicit separation of data and models, making the proposed notation clearer for perception. In the proposed engine, computational graph traversal does not have a rigorous sequence. The call of the sequence of calculations depends on the specific model that the user currently needs.

Finding biosynthetic pathways is essential for metabolic engineering of organisms to produce chemicals, biodegradation prediction of pollutants and drugs, and for the elucidation of bioproduction pathways of secondary metabolites. A key step in biosynthetic pathway design is the extraction of novel metabolic pathways from big networks that integrate known biological, as well as novel, predicted biotransformations. However, especially with the integration of big data, the efficient analysis and navigation of metabolic networks remains a challenge. Here, we propose the construction of searchable graph representations of metabolic networks. Éach reaction is decomposed into pairs of reactants and products, and each pair is assigned a weight, which is calculated from the number of conserved atoms between the reactant and the product molecule. We test our method on a biochemical network that spans 6,546 known enzymatic reactions to show how our approach elegantly extracts biologically relevant metabolic pathways from biochemical networks, and how the proposed network structure enables the application of efficient graph search algorithms that improve navigation and pathway identification in big metabolic networks. The weighted reactant-product pairs of an example network and the corresponding graph search algorithm are available online. The proposed method extracts metabolic pathways fast and reliably from big biochemical networks, which is inherently important for all applications involving the engineering of metabolic networks.

PURPOSE The objective of this study was to formalize and automate quality assurance (QA) in radiation oncology. Quality assurance in radiation oncology entails a multistep verification of complex, personalized radiation plans to treat cancer involving an interdisciplinary team and high technology, multivendor software and hardware systems. We addressed the pretreatment physics chart review (TPCR) using methods from graph theory and constraint programming to study the effect of dependencies between variables and automatically identify logical inconsistencies and how they propagate. MATERIALS AND METHODS We used a modular approach to decompose the TPCR process into tractable units comprising subprocesses, modules and variables. Modules represented the main software entities comprised in the radiation treatment planning workflow and subprocesses grouped the checks to be performed by functionality. Module-associated variables served as inputs to the subprocesses. Relationships between variables were modeled by means of a directed graph. The detection of errors, in the form of inconsistencies, was formalized as a constraint satisfaction problem whereby checks were encoded as logical formulae. The sequence in which subprocesses were visited was described in an activity diagram. RESULTS The comprehensive model for the TPCR process comprised 5 modules, 19 subprocesses and 346 variables, 225 of which were distinct. Modules included "Treatment Planning System" and "Record and Verify System." Subprocesses included "Dose Prescription," "Documents," "CT Integrity," "Anatomical Contours," "Beam Configuration," "Dose Calculation," "3D Dose Distribution Quality," and "Treatment Approval." Variable inconsistencies, and their source and propagation were determined by checking for constraint violation and through graph traversal. Impact scores, obtained through graph traversal, combined with severity scores associated with an inconsistency, allowed risk assessment. CONCLUSIONS Directed graphs combined with constraint programming hold promise for formalizing complex QA processes in radiation oncology, performing risk assessment and automating the TPCR process. Though complex, the process is tractable.

Path planning is an essential task in autonomous mobile robotics that demands to navigate following a minimum-cost path, which involves partitioning the landscape in nodes and the use of combinatorial optimization methods to find the optimal sequence of nodes to follow. Traditional algorithms such as the A* and Dijkstra are computationally efficient in landscapes with a reduced number of nodes. Most of the practical applications require to use a significantly large number of nodes up to the point that the problem might be computationally explosive. This work contributes to state-of-the-art with two heuristics for the A* algorithm that allows finding the optimal path in landscapes with a large number of nodes. The heuristics used the Euclidean and Manhattan distance in the estimation function. We present a comparative analysis of our proposal against the Dijkstra’s and A* algorithms. All the experiments were achieved using a simulation-platform specially designed for testing important algorithm features, such as the grid size, benchmark problems, the design of custom-made test sceneries, and others. Relevant results are drawn to continue working in this line.