Search

The need for speeding up data analytics increases inevitably due to the need for extracting valuable information from social media, data generated by smart devices with sensors, patterns of people's communications over the web, items viewed and bought by global-scale customers, cloud applications, etc., all of which take part in the "Big Data." Such kind of interaction data is very well represented as sparse graphs to enable the graph analytics, which requires efficient underlying kernels. The breadth-first search (BFS)-based traversal is a commonly used kernel in graph algorithms such as the betweenness centrality algorithm for centrality analysis. In this work, we focus on parallel BFS operations and propose hypergraph-based combinatorial models that aim at reducing cache misses and hence exploiting data locality during the parallel BFS operations. Our models are based on finding new vertex visit orders so that locality in accessing the data associated with vertices is exploited. Experiments on graphs arising in a wide range of applications show that our proposed models achieve on average 9% performance improvement in the CPU-based Ligra data analytics framework. [ABSTRACT FROM AUTHOR]

We consider the classic stochastic multiarmed bandit problem with a constraint that limits the total cost incurred by switching between actions to be no larger than a given switching budget. For this problem, we prove matching upper and lower bounds on the optimal (i.e., minimax) regret and provide efficient rate-optimal algorithms. Surprisingly, the optimal regret of this problem exhibits a nonconventional growth rate in terms of the time horizon and the number of arms. Consequently, we discover surprising "phase transitions" regarding how the optimal regret rate changes with respect to the switching budget: when the number of arms is fixed, there are equal-length phases, in which the optimal regret rate remains (almost) the same within each phase and exhibits abrupt changes between phases; when the number of arms grows with the time horizon, such abrupt changes become subtler and may disappear, but a generalized notion of phase transitions involving certain new measurements still exists. The results enable us to fully characterize the trade-off between the regret rate and the incurred switching cost in the stochastic multiarmed bandit problem, contributing new insights to this fundamental problem. Under the general switching cost structure, the results reveal interesting connections between bandit problems and graph traversal problems, such as the shortest Hamiltonian path problem. This paper was accepted by J. George Shanthikumar, data science. Supplemental Material: The online appendix and data are available at https://doi.org/10.1287/mnsc.2023.4755. [ABSTRACT FROM AUTHOR]

We identify the graph data structure, frontiers, operators, an iterative loop structure, and convergence conditions as essential components of graph analytics systems based on the native-graph approach. Using these essential components, we propose an abstraction that captures all the significant programming models within graph analytics, such as bulk-synchronous, asynchronous, shared-memory, message-passing, and push vs. pull traversals. Finally, we demonstrate the power of our abstraction with an elegant modern C++ implementation of single-source shortest path and its required components.

Today, as PHP application technology is becoming increasingly mature, the functions of modern multi-layer web applications are becoming more and more complete, and the complexity is also gradually increasing. While providing developers with various business functions and interfaces, multi-tier Web applications also successfully cover the details of application development. This type of web application adopts a unified entrance, many object-oriented codes are used, and features such as encapsulation, inheritance, and polymorphism bring challenges to vulnerability mining from the perspective of static analysis. A large amount of object-oriented code makes it impossible for a simple function name-matching method to build a complete call graph (CG), resulting in the inability to perform a comprehensive interprocedural analysis. At the same time, the encapsulation feature of the class makes the data hidden in the object attribute, and the vulnerability path cannot be obtained through the general data-flow analysis. In response to the above issues, we propose a vulnerability detection method that supports vulnerability detection for multi-layer web applications based on MVC (Model-View-Control) architecture. First, we improve the construction of the call graph and Code Property Graph (CPG). Then, based on the enhanced Code Property Graph, we propose a technique to support vulnerability detection for multi-layer web applications. Based on this approach, we implemented a prototype of VulPathsFinder, a security analysis tool extended from the PHP security analyzer Joern-PHP. Then, we select ten MVC based and ten non-MVC-based applications to form a test dataset and validate the effectiveness of VulPathsFinder based on this dataset. Experimental results show that, compared with currently available tools, VulPathsFinder can handle framework applications more effectively, build a complete code property map, and detect vulnerabilities in framework applications that existing tools cannot detect. [ABSTRACT FROM AUTHOR]

As the basis of many algorithms,the breadth-first search(BFS) algorithm for big graph data has attracted more and more interests industrially and academically.Among the researches on BFS for the big graph,the solid state disk(SSD) is utilized to improve algorithm performance.In the graph traversal,the storage devices are required to continuously and repeatedly load data to fulfill the demand of graph traversal.However,many operations of data wipe caused by continuously and repeatedly loading data severely degrade the lifetime of SSD.For this reason,the lifetime of SSD can be effectively extended by reducing the data for write operations.Firstly,combined with the characteristics of graph structure,the data reuse model is constructed for describing the levels of data reuse in graph traversal.Then,a heuristic priority access algorithm based on vertex degree is proposed.By judging the independence of vertexes,the proposed algorithm selects graph vertexes that are priority accessed for improving the probability of data reusing,increasing hit ratio,and reducing the wear of flash memory.This method is available to any BFS algorithms and datasets without modifying BFS algorithm and big graph data.In the end,simulation results demonstrate that the proposed model and algorithm are effective.By applying the proposed algorithm on three common BFS algorithms:BFS-4K,B40C,and Gunrock,it can effectively reduce the operations of data written in graph traversal and improve the lifetime of SSD 12%,15%,22%,respectively.

Companies and research institutes are acquiring monopolized technologies through patents to survive in a rapidly changing market. The applicant is guaranteed by law the exclusive right to the technology for a certain period. A prior art search is an essential task for this purpose. Therefore, the need for a successful prior art search is increasing. Previous studies have disadvantages because relevant fields are limited, requiring an in-depth understanding of specific technologies. This paper proposes a method to overcome these limitations using patent text and citation information. The proposed method searches for prior art using a citation network based on the shortest path derived from a breadth-first search. We examined based on experiments whether the proposed method could be applied to the industry. Based on the results, the proposed algorithm can efficiently search for prior art. Furthermore, it was possible to construct a counterstrategy based on the characteristics of the applicant. The code will be made available at github.com/lee-ju/k_step_PIC.

Floorplan generation has drawn widespread interest in the community. Recent learning-based methods for generating realistic floorplans have made significant progress while a complex heuristic post-processing is still necessary to obtain desired results. In this paper, we propose a novel wall-oriented method, called WallPlan, for automatically and efficiently generating plausible floorplans from various design constraints. We pioneer the representation of the floorplan as a wall graph with room labels and consider the floorplan generation as a graph generation. Given the boundary as input, we first initialize the boundary with windows predicted by WinNet. Then a graph generation network GraphNet and semantics prediction network LabelNet are coupled to generate the wall graph progressively by imitating graph traversal. WallPlan can be applied for practical architectural designs, especially the wall-based constraints. We conduct ablation experiments, qualitative evaluations, quantitative comparisons, and perceptual studies to evaluate our method's feasibility, efficacy, and versatility. Intensive experiments demonstrate our method requires no post-processing, producing higher quality floorplans than state-of-the-art techniques. [ABSTRACT FROM AUTHOR]

A key property of Linked Data is the representation and publication of data as interconnected labelled graphs where different resources linked to each other form a network of meaningful information. Searching these important relationships between resources – within single or distributed graphs – can be reduced to a pathfinding or navigation problem, i.e., looking for chains of intermediate nodes. SPARQL1.1, the current standard query language for RDF-based Linked Data defines a construct – called Property Paths (PPs) – to navigate between entities within a single graph. Since Linked Data technologies are naturally aimed at decentralised scenarios, there are many cases where centralising this data is not feasible or even not possible for querying purposes. To address these problems, we propose a SPARQL PP-based graph processing approach – dubbed DpcLD – where users can execute SPARQL PP queries and find paths distributed across multiple, connected graphs exposed as SPARQL endpoints. To execute the distributed path queries we implemented an index-free, cache-based query engine that communicates with a shared algorithm running on each remote endpoint, and computes the distributed paths. In this paper, we highlight the way in which this approach exploits and aggregates partial paths, within a distributed environment, to produce complete results. We perform extensive experiments to demonstrate the performance of our approach on two datasets: One representing 10 million triples from the DBPedia SPARQL benchmark, and another full benchmark dataset corresponding to 124 million triples. We also perform a scalability test of our approach using real-world genomics datasets distributed across multiple endpoints. We compare our distributed approach with other distributed and centralized pathfinding approaches, showing that it outperforms other distributed approaches by orders of magnitude, and provides a good trade-off for cases when the data cannot be centralised. [ABSTRACT FROM AUTHOR]

In recent years, graph computing has played an increasingly important role in many fields. The connected component algorithm is an important basic algorithm for graph computing, which can be applied to multiple scenarios such as reachability query. This paper is oriented to the large-scale graph traversal GraphSOO standard test, and optimizes the connected component algorithm and data structure. The main innovations are as follows: (1) A shortcutting-vector algorithm is proposed for the union-find set, and the degree of coordination between the algorithm and the data structure is tested. (2) The multi-threaded iterative rotation algorithm is used to achieve the parallel acceleration of the algorithm. (3) The advantages and disadvantages of different implementation methods are compared from multiple dimensions. Based on the optimization method, the performance is evaluated and analyzed. When scale = 25 (including 225 vertices), the speedup ratio of the shortcutting-vector algorithm to the rank-merging algorithm based on two-dimensional vectors and linked lists is 1. 38 times and 1. 40 times, respectively. The speedup ratios of BFS and DFS are 4. 76 times and 4. 70 times respectively, and the space occupation is 4. 1%〜4. 6% of the two algorithms. In addition, the speedup ratio of parallel to serial is 1. 57 times. [ABSTRACT FROM AUTHOR]

Coarse-grained reconfigurable architecture (CGRA) mapping involves three main steps: placement, routing, and timing. The mapping is an NP-complete problem, and a common strategy is to decouple this process into its independent steps. This work focuses on the placement step, and its aim is to propose a technique that is both reasonably fast and leads to high-performance solutions. Furthermore, a near-optimal placement simplifies the following routing and timing steps. Exact solutions cannot find placements in a reasonable execution time as input designs increase in size. Heuristic solutions includemeta-heuristics, such as Simulated Annealing (SA) and fast and straightforward greedy heuristics based on graph traversal. However, as these approaches are probabilistic and have a large design space, it is not easy to provide both run-time efficiency and good solution quality.We propose a graph traversal heuristic that provides the best of both: high-quality placements similar to SA and the execution time of graph traversal approaches. Our placement introduces novel ideas based on "you only traverse twice" (YOTT) approach that performs a two-step graph traversal. The first traversal generates annotated data to guide the second step, which greedily performs the placement, node per node, aided by the annotated data and target architecture constraints. We introduce three new concepts to implement this technique: I/O and reconvergence annotation, degree matching, and look-ahead placement. Our analysis of this approach explores the placement execution time/quality trade-offs.We point out insights on how to analyze graph properties during dataflow mapping. Our results show that YOTT is 60.6 x, 9.7 x, and 2.3 x faster than a high-quality SA, bounding box SA VPR, and multi-single traversal placements, respectively. Furthermore, YOTT reduces the average wire length and the maximal FIFO size (additional timing requirement on CGRAs) to avoid delay mismatches in fully pipelined architectures. [ABSTRACT FROM AUTHOR]

Coarse grain reconfigurable architectures (CGRAs) are an emerging hybrid computational architecture that has the parallel customization benefits of low-level logic devices, such as FPGAs and ASICs, while the relative coarseness of these architectures makes CGRAs easier to design for, which is more similar to the traditional processor. In the process of mapping designs to CGRAs, flexible, fast, and adaptive placement and routing (P&R) is fundamental in order to implement efficient run-time reconfigurable frameworks. It is well-known that P&R is an NP-complete problem, and thus, solutions rely on heuristics to achieve quality results with acceptable execution times. CGRA P&R has different constraints compared to traditional VLSI P&R, e.g., path latency balancing and modulo scheduling of loops. In this work, we propose a graph-based P&R approach that uses graph traversals to map designs to CGRAs. Additionally, we parallelize our approach with a graph-based greedy heuristic that executes on a GPU. We compare our proposed P&R approach with the CGRA-ME framework, which implements simulated annealing and integer linear programming placement algorithms. Our results show that this new approach can generate optimal mappings and improve the execution run-time up to several orders of magnitude. Furthermore, considering spatial mapping at the millisecond scale, our GPU approach is one order of magnitude faster compared to the state-of-the-art tool VPR. [ABSTRACT FROM AUTHOR]

With a huge amount of information being stored as structured data, there is an increasing need for retrieving exact answers to questions from tables. Answering natural language questions on structured data usually involves semantic parsing of query to a machine understandable format which is then used to retrieve information from the database. Training semantic parsers for domain specific tasks is a tedious job and does not guarantee accurate results. In this paper, we used conversational analytics tool to create the user interface and to get the required entities and intents from the query thus avoiding the traditional semantic parsing approach. We then make use of Knowledge Graph for querying in structured data domain. Knowledge graphs can be easily leveraged for question answering systems, to use them as the database. We extract appropriate answers for different types of queries which have been illustrated in the Results section.

Finding the shortest paths from a single source to all other vertices is a fundamental method used in a variety of higher-level graph algorithms. We present three parallel friendly and work-efficient methods to solve this Single-Source Shortest Paths (SSSP) problem: Workfront Sweep, Near-Far and Bucketing. These methods choose different approaches to balance the tradeoff between saving work and organizational overhead. In practice, all of these methods do much less work than traditional Bellman-Ford methods, while adding only a modest amount of extra work over serial methods. These methods are designed to have a sufficient parallel workload to fill modern massively-parallel machines, and select reorganizational schemes that map well to these architectures. We show that in general our Near-Far method has the highest performance on modern GPUs, outperforming other parallel methods.We also explore a variety of parallel load-balanced graph traversal strategies and apply them towards our SSSP solver. Our work-saving methods always outperform a traditional GPU Bellman-Ford implementation, achieving rates up to 14x higher on low-degree graphs and 340x higher on scalefree graphs. We also see significant speedups (20–60x) when compared against a serial implementation on graphs with adequately high degree.

A key property of linked data, i.e., the web-based representation and publication of data as interconnected labeled graphs, is that it enables querying and navigating through datasets distributed across the network. SPARQL1.1, the current standard query language for RDF-based linked data, defines a construct-called property paths (PP)-to navigate between the entities of a graph. This is potentially very useful in a number of use cases, e.g., in the biomedical domain, where large datasets are available as linked data graphs. However, the use of PP in SPARQL 1.1. is possible only on a single local graph, requiring us to merge all distributed datasets into one large, centrally stored graph, therefore reducing the value of using linked data in the first place. We propose an index-based approach-called QPPDs-for answering queries for paths distributed across multiple, distributed datasets. We provide a heuristic-based source selection mechanism to select the relevant datasets (also called data sources) for a given path query, and a technique that federates queries to selected sources, and assembles (merges) the paths (i.e., partial or complete) retrieved from those remote datasets. We demonstrate our approach on a genomics use-case, where the description of biological entities (e.g., genes, diseases, and drugs) is scattered across multiple datasets. In our preliminary investigation, we evaluate the QPPDs approach with real-world path queries-on biological data that are very heterogeneous in nature-in terms of performance (overall path retrieval time) and result completeness, i.e., the number of paths retrieved.

Abstract Background R has become the de-facto reference analysis environment in Bioinformatics. Plenty of tools are available as packages that extend the R functionality, and many of them target the analysis of biological networks. Several algorithms for graphs, which are the most adopted mathematical representation of networks, are well-known examples of applications that require high-performance computing, and for which classic sequential implementations are becoming inappropriate. In this context, parallel approaches targeting GPU architectures are becoming pervasive to deal with the execution time constraints. Although R packages for parallel execution on GPUs are already available, none of them provides graph algorithms. Results This work presents cuRnet, a R package that provides a parallel implementation for GPUs of the breath-first search (BFS), the single-source shortest paths (SSSP), and the strongly connected components (SCC) algorithms. The package allows offloading computing intensive applications to GPU devices for massively parallel computation and to speed up the runtime up to one order of magnitude with respect to the standard sequential computations on CPU. We have tested cuRnet on a benchmark of large protein interaction networks and for the interpretation of high-throughput omics data thought network analysis. Conclusions cuRnet is a R package to speed up graph traversal and analysis through parallel computation on GPUs. We show the efficiency of cuRnet applied both to biological network analysis, which requires basic graph algorithms, and to complex existing procedures built upon such algorithms.

Summary: Media‐based modulation (MBM) plays a crucial role in enhancing the spectral efficiency and energy efficiency of massive MIMO (mMIMO) systems for 5G and beyond wireless communications. In MBM, multiple parasitic elements, also termed as radio frequency (RF) mirrors, are placed near the transmit antennas for generating different channel fade realizations. These realizations are obtained by ON/OFF switching of RF mirrors. One of those channel fade realizations is selected (using a part of the incoming information bits) for transmitting a part of the information bits utilizing a symbol chosen from the conventional constellation set (using another part of the incoming information bits). Transmission of a symbol through one of the available channel realizations constitutes a sparse transmit vector for each user in MBM‐mMIMO. The sparse nature of transmitted symbols from multiple users and inter‐user interference makes the symbol detection in uplink MBM‐mMIMO challenging. Therefore, in this article, the problem of symbol detection in MBM‐mMIMO is analyzed from a graph‐theoretical point of view, and a graph‐traversal aided low‐complexity symbol detection algorithm is proposed inspired by socio‐cognitive learning of swarm optimization. Also, the convergence characteristic of the proposed technique is investigated theoretically. Further, an analytical expression of upper bound on bit error rate performance is derived and corroborated through simulations. Viability and robustness of the proposed technique are also justified through simulations over state‐of‐art detection techniques, under both perfect and imperfect channel state information scenarios. [ABSTRACT FROM AUTHOR]

Carpoolng is a sysytem which the passenger can share the vehicale nad by this means the traffic also duces due to red ucing the no of vehicle on the the roa the government government organization has started the implementatio of carpooling system. To implement this system various Approaches has beendeveloped but becomes essentials that the Selection of optimal distance for pickingthe ger for improvi passenger for improving the recital of the system so in the research work, we use graph traversal technique to find the effective path and it is testedto find the opiimal solution The experimentl results of the proposed metdodology our approac showng approa more efficient than the existing approach. [ABSTRACT FROM AUTHOR]

In various wireless networking settings, node locations determine a network's topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required Θ (log n) state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and, when the algorithm has knowledge of the incoming port (the preceding node on the route), the first stateless local geometric routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions). We also show that Ω (log n) state bits are necessary in planar subdivisions in which faces may have three or more reflex vertices. [ABSTRACT FROM AUTHOR]

In view of the problem of the slowness of the community diffusion and not suitable for large-scale network, the paper proposed a local community detection algorithm based on breadth first traversal. The algorithm found out the node with lowest degree in the network, and used this node as a starting point to divide the nodes into community nodes and boundary nodes to form the initial community detection by influence function. Then it used fitness function to get the final cover. The experimental results show that the algorithm tested in a real network can effectively dig out community structure in the network and have faster speed. [ABSTRACT FROM AUTHOR]

Increasing threat of password leakage from compromised password hashes demands a resource consuming password-hashing algorithm to prevent the precomputation of the password hashes. A class of password-hashing schemes (PHS) provides such a defense by making the design Memory hard. This ensures that any reduction in the memory consumed by the algorithm leads to an exponential increase in its runtime. The security offered by a memory-hard PHS design is measured in terms of its time-memory trade-off (TMTO) defense. Another important measure for a good PHS is its efficiency in utilizing all the available memory as quickly as possible, and fast running time when more than the required memory is available. In this work, we present a simple technique to analyze TMTO for a password-hashing scheme which can be represented as a directed acyclic graph (DAG). The nodes of the DAG correspond to the storage required by the algorithm and the edges correspond to the flow of the execution. Our proposed technique provides expected runtimes at varied levels of available storage utilizing the DAG representation of the algorithm. We show the effectiveness of our proposed technique by applying it on three designs from the "Password Hashing Competition" (PHC)—Argon2-Version 1.2.1 (the PHC winner), Catena-Version 3.2 and Rig-Version 2. Our analysis shows that Argon2i is not providing expected memory hardness which is also highlighted in a recent work by Corrigan-Gibbs et al. We analyze these PHS for performance under various settings of time and memory complexities. Our experimental results show (i) simple DAGs for PHS are efficient but not memory hard, (ii) complex DAGs for PHS are memory hard but less efficient, and (iii) combination of two simple graphs in the representation of a DAG for PHS achieves both memory hardness and efficiency. [ABSTRACT FROM AUTHOR]

Background: R has become the de-facto reference analysis environment in Bioinformatics. Plenty of tools are available as packages that extend the R functionality, and many of them target the analysis of biological networks. Several algorithms for graphs, which are the most adopted mathematical representation of networks, are well-known examples of applications that require high-performance computing, and for which classic sequential implementations are becoming inappropriate. In this context, parallel approaches targeting GPU architectures are becoming pervasive to deal with the execution time constraints. Although R packages for parallel execution on GPUs are already available, none of them provides graph algorithms. Results: This work presents cuRnet, a R package that provides a parallel implementation for GPUs of the breath-first search (BFS), the single-source shortest paths (SSSP), and the strongly connected components (SCC) algorithms. The package allows offloading computing intensive applications to GPU devices for massively parallel computation and to speed up the runtime up to one order of magnitude with respect to the standard sequential computations on CPU. We have tested cuRnet on a benchmark of large protein interaction networks and for the interpretation of high-throughput omics data thought network analysis. Conclusions: cuRnet is a R package to speed up graph traversal and analysis through parallel computation on GPUs. We show the efficiency of cuRnet applied both to biological network analysis, which requires basic graph algorithms, and to complex existing procedures built upon such algorithms. [ABSTRACT FROM AUTHOR]