Search

We investigate efficient randomized methods for approximating the number of perfect matchings in bipartite graphs and general undirected graphs. Our approach is based on assigning probabilities to edges, randomly selecting an edge to be in a perfect matching, and discarding edges that cannot be put in a perfect matching. The probabilities are set according to the entries in the doubly stochastically scaled version of the adjacency matrix of the given graph. The experimental analysis on random and real-life graphs shows improvements in the approximation over previous and similar methods from the literature. [ABSTRACT FROM AUTHOR]

Influence maximization (IM) is the problem of finding a seed vertex set which is expected to incur the maximum influence spread on a graph. It has various applications in practice such as devising an effective and efficient approach to disseminate information, news or ad within a social network. The problem is shown to be NP-hard and approximation algorithms with provable quality guarantees exist in the literature. However, these algorithms are computationally expensive even for medium-scaled graphs. Furthermore, graph algorithms usually suffer from spatial and temporal irregularities during memory accesses, and this adds an extra cost on top of the already expensive IM kernels. In this article we leverage fused sampling, memoization, and vectorization to restructure, parallelize and boost their performance on undirected networks. The proposed approach employs a pseudo-random function and performs multiple Monte-Carlo simulations in parallel to exploit the SIMD lanes effectively and efficiently. In addition, it significantly reduces the number of edge traversals, hence the amount of data brought from the memory, which is critical for almost all memory-bound graph kernels. We apply the proposed approach to the traditional MixGreedy algorithm and propose INFuseR-MG which is more than $3000\times$ 3000 × faster than the greedy approaches and can run on large graphs that have been considered as too large in the literature. For instance, the new algorithm runs in 2.09, 0.08, 0.36 seconds on graphs Amazon, NetHEP, NetPhy with 16 threads where the sequential baseline takes 141.3, 259.1 and 1725.2 seconds, respectively. To compare INFuseR-MG with the state-of-the-art approximation algorithms, we conduct a thorough experimental analysis with various influence settings. The results on real-life, undirected networks show that on 16 threads, INFuseR-MG is $2.3\times$ 2. 3 × – $173.8\times$ 173. 8 × faster than state-of-the-art while being superior in terms of influence scores, and using a comparable amount of memory. [ABSTRACT FROM AUTHOR]

The permanent is an important characteristic of a matrix and it has been used in many applications. Unfortunately, it is a hard to compute and hard to approximate the immanant. For dense/full matrices, the fastest exact algorithm, Ryser, has O(2n-1n complexity. In this work, a parallel algorithm, SkipPer, is proposed to exploit the sparsity within the input matrix as much as possible. SkipPer restructures the matrix to reduce the overall work, skips the unnecessary steps, and employs a coarse-grain, shared-memory parallelization with dynamic scheduling. The experiments show that SkipPer increases the performance of exact permanent computation up to 140x compared to the naive version for general matrices. Furthermore, thanks to the coarse-grain parallelization, 14-15x speedup on average is obtained with β = 16 threads over sequential SkipPer. Overall, by exploiting the sparsity and parallelism, the speedup is 2000x for some of the matrices used in the experimental setting. The proposed techniques in this paper can be used to significantly improve the performance of exact permanent computation by simply replacing Ryser with SkipPer, especially when the matrix is highly sparse. [ABSTRACT FROM AUTHOR]

In multilevel secret sharing, a secret is shared among a set of hierarchically organized participants in a way that the members of the superior compartments are more powerful and can replace the participants of an inferior one to form an authorized coalition during secret reconstruction. In this work, we first show that the only existing multilevel threshold secret sharing scheme based on the Chinese Remainder Theorem (CRT) is not secure and fails to work with certain natural threshold settings on compartments. As the main contribution, we propose a secure CRT-based scheme that works for all threshold settings. In the proposed scheme, we employ a refined version of Asmuth-Bloom secret sharing with a special and generic Asmuth-Bloom sequence called the anchor sequence. [ABSTRACT FROM AUTHOR]

The well-known Birkhoff–von Neumann (BvN) decomposition expresses a doubly stochastic matrix as a convex combination of a number of permutation matrices. For a given doubly stochastic matrix, there are many BvN decompositions, and finding the one with the minimum number of permutation matrices is NP-hard. There are heuristics to obtain BvN decompositions for a given doubly stochastic matrix. A family of heuristics is based on the original proof of Birkhoff and proceeds step by step by subtracting a scalar multiple of a permutation matrix at each step from the current matrix, starting from the given matrix. At every step, the subtracted matrix contains nonzeros at the positions of some nonzero entries of the current matrix and annihilates at least one entry, while keeping the current matrix nonnegative. Our first result, which supports a claim of Brualdi (1982) [3] , shows that this family of heuristics can miss optimal decompositions. We also investigate the performance of two heuristics from this family theoretically. [ABSTRACT FROM AUTHOR]

Testing is the most expensive and time consuming phase in the development of complex systems. Model–based testing is an approach that can be used to automate the generation of high quality test suites, which is the most challenging part of testing. Formal models, such as finite state machines or automata, have been used as specifications from which the test suites can be automatically generated. The tests are applied after the system is synchronized to a particular state, which can be accomplished by using a synchronizing word. Computing a shortest synchronizing word is of interest for practical purposes, e.g. for a shorter testing time. However, computing a shortest synchronizing word is an NP–hard problem. Therefore, heuristics are used to compute short synchronizing words. Greedy and Cycle are the fastest synchronizing heuristics currently known. In this paper, without sacrificing the quality of the synchronizing words, we improve the time performance of Greedy and Cycle , by restructuring the algorithms and applying some optimizations. Our experimental results show that depending on the automata size, Cycle and Greedy can be made 25 × and 95 × faster, respectively. The suggested improvements become more effective as the size of the automaton increases. [ABSTRACT FROM AUTHOR]

We propose two heuristics for the bipartite matching problem that are amenable to shared-memory parallelization. The first heuristic is very intriguing from a parallelization perspective. It has no significant algorithmic synchronization overhead and no conflict resolution is needed across threads. We show that this heuristic has an approximation ratio of around 0.632 under some common conditions. The second heuristic is designed to obtain a larger matching by employing the well-known Karp–Sipser heuristic on a judiciously chosen subgraph of the original graph. We show that the Karp–Sipser heuristic always finds a maximum cardinality matching in the chosen subgraph. Although the Karp–Sipser heuristic is hard to parallelize for general graphs, we exploit the structure of the selected subgraphs to propose a specialized implementation which demonstrates very good scalability. We prove that this second heuristic has an approximation guarantee of around 0.866 under the same conditions as in the first algorithm. We discuss parallel implementations of the proposed heuristics on a multicore architecture. Experimental results, for demonstrating speed-ups and verifying the theoretical results in practice, are provided. [ABSTRACT FROM AUTHOR]

We investigate hypergraph partitioning-based methods for efficient parallelization of communicating tasks. A good partitioning method should divide the load among the processors as evenly as possible and minimize the inter-processor communication overhead. The total communication volume is the most popular communication overhead metric which is reduced by the existing state-of-the-art hypergraph partitioners. However, other metrics such as the total number of messages, the maximum amount of data transferred by a processor, or a combination of them are equally, if not more, important. Existing hypergraph-based solutions use a two phase approach to minimize such metrics where in each phase, they minimize a different metric, sometimes at the expense of others. We propose a one-phase approach where all the communication cost metrics can be effectively minimized in a multi-objective setting and reductions can be achieved for all metrics together. For an accurate modeling of the maximum volume and the number of messages sent and received by a processor, we propose the use of directed hypergraphs. The directions on hyperedges necessitate revisiting the standard partitioning heuristics. We do so and propose a multi-objective, multi-level hypergraph partitioner called UMPa. The partitioner takes various prioritized communication metrics into account, and optimizes all of them together in the same phase. Compared to the state-of-the-art methods which only minimize the total communication volume, we show on a large number of problem instances that UMPa produces better partitions in terms of several communication metrics. [ABSTRACT FROM AUTHOR]

The elimination tree model for sparse unsymmetric matrices and an algorithm for constructing it have been recently proposed by Eisenstat and Liu [SIAM J. Matrix Anal. Appl., 26 (2005), pp. 686-705] and [SIAM J. Matrix Anal. Appl., 29 (2008), pp. 1363-1381]. The construction algorithm has a worst-case time complexity of Θ(mn) for an n X n unsymmetric matrix having m off-diagonal nonzeros. We propose another algorithm that has a worst-case time complexity of ...(mlogn). We compare the two algorithms experimentally and show that both algorithms are efficient in general. The algorithm of Eisenstat and Liu is faster in many practical cases, yet there are instances in which there is a significant difference between the running time of the two algorithms in favor of the one proposed here. [ABSTRACT FROM AUTHOR]

We consider the following task assignment problem. Communicating tasks are to be assigned to heterogeneous processors interconnected with a heterogeneous network. The objective is to minimize the total sum of the execution and communication costs. The problem is NP-hard. We present an exact algorithm based on the well-known A* search. We report simulation results over a wide range of parameters where the largest solved instance contains about three hundred tasks to be assigned to eight processors. [ABSTRACT FROM AUTHOR]

Abstract: We consider the problem of scheduling an application on a computing system consisting of heterogeneous processors and data repositories. The application consists of a large number of file-sharing otherwise independent tasks. The files initially reside on the repositories. The processors and the repositories are connected through a heterogeneous interconnection network. Our aim is to assign the tasks to the processors, to schedule the file transfers from the repositories, and to schedule the executions of tasks on each processor in such a way that the turnaround time is minimized. We propose a heuristic composed of three phases: initial task assignment, task assignment refinement, and execution ordering. We experimentally compare the proposed heuristics with three well-known heuristics on a large number of problem instances. The proposed heuristic runs considerably faster than the existing heuristics and obtains 10–14% better turnaround times than the best of the three existing heuristics. [Copyright &y& Elsevier]

The scheduling of independent but file-sharing tasks on heterogeneous master-slave platforms has recently found important applications in Grid environments. The scheduling heuristics recently proposed for this problem are all constructive in nature and based on a common greedy criterion which depends on the momentary completion time values of the tasks. We show that this greedy decision criterion has shortcomings in exploiting the file-sharing interaction among tasks since completion time values are inadequate to extract the global view of this interaction. We propose a three-phase scheduling approach which involves initial task assignment, refinement, and execution ordering phases. For the refinement phase, we model the target application as a hypergraph and, with an elegant hypergraph-partitioning-like formulation, we propose using iterative-improvement-based heuristics for refining the task assignments according to two novel objective functions. Unlike the turnaround time, which is the actual schedule cost, the smoothness of proposed objective functions enables the use of iterative-improvement-based heuristics successfully since their effectiveness and efficiency depend on the smoothness of the objective function. Experimental results on a wide range of synthetically generated heterogeneous master-slave frameworks show that the proposed three-phase scheduling approach performs much better than the greedy constructive approach. [ABSTRACT FROM AUTHOR]

Graphs are ubiquitous, and they can model unique characteristics and complex relations of real-life systems. Although using machine learning (ML) on graphs is promising, their raw representation is not suitable for ML algorithms. Graph embedding represents each node of a graph as a $d$ d -dimensional vector which is more suitable for ML tasks. However, the embedding process is expensive, and CPU-based tools do not scale to real-world graphs. In this work, we present GOSH, a GPU-based tool for embedding large-scale graphs with minimum hardware constraints. GOSH employs a novel graph coarsening algorithm to enhance the impact of updates and minimize the work for embedding. It also incorporates a decomposition schema that enables any arbitrarily large graph to be embedded with a single GPU. As a result, GOSH sets a new state-of-the-art in link prediction both in accuracy and speed, and delivers high-quality embeddings for node classification at a fraction of the time compared to the state-of-the-art. For instance, it can embed a graph with over 65 million vertices and 1.8 billion edges in less than 30 minutes on a single GPU. [ABSTRACT FROM AUTHOR]

An important concept in finite state machine based testing is synchronization which is used to initialize an implementation to a particular state. Usually, synchronizing sequences are used for this purpose and the length of the sequence used is important since it determines the cost of the initialization process. Unfortunately, the shortest synchronization sequence problem is NP-Hard. Instead, heuristics are used to generate short sequences. However, the cubic complexity of even the fastest heuristic algorithms can be a problem in practice. In order to scale the performance of the heuristics for generating short synchronizing sequences, we propose algorithmic improvements together with a parallel implementation of the cheapest heuristics existing in the literature. To identify the bottlenecks of these heuristics, we experimented on random and slowly synchronizing automata. The identified bottlenecks in the algorithms are improved by using algorithmic modifications. We also implement the techniques on multicore CPUs and Graphics Processing Units (GPUs) to take benefit of the modern parallel computation architectures. The sequential implementation of the heuristic algorithms are compared to our parallel implementations by using a test suite consisting of 1200 automata. The speedup values obtained depend on the size and the nature of the automaton. In our experiments, we observe speedup values as high as 340x by using a 16-core CPU parallelization, and 496x by using a GPU. Furthermore, the proposed methods scale well and the speedup values increase as the size of the automata increases. • We propose algorithmic improvements together with an efficient parallelization approach for synchronizing sequence heuristics. • We experimented on random and slowly synchronizing automata. • We implement the proposed techniques on multicore CPUs and Graphics Processing Units (GPUs) to take benefit of the modern parallel architectures. • With the proposed techniques, we observe speedup values as high as 340x by using a 16-core CPU parallelization, and 496x by using a GPU. • The proposed methods scale well and the speedup values increase as the size of the automata increases. [ABSTRACT FROM AUTHOR]

Abstract The etiology of addiction has not yet been fully elucidated. The ratio between the length of the second and fourth fingers (2D:4D ratio) has been linked with prenatal androgen concentrations, but also with addictive behvaiors. Aim: The present study aimed to evaluate the differences of 2D:4D ratio of individuals with cannabis and heroin addiction by examining them together with the control group. A total of sixty two male patients (33 opiate use disorder and 29 cannabis use disorder) with substance use disorder and the twenty-nine healthy controls were included in the present investigation. We obtained the lengths of 2D and 4D of the subjects by using sensitive calipers and calculated the 2D:4D. Heroin-addicted patients had lower 2D:4D ratio in in the right hand (significant difference between control group) (p < 0.001), there was no significant difference found between heroin-cannabis (p = 0.242) and control-cannabis 2D:4D ratios (p < 0.06). In the left hand, it was significant between the heroin-control groups (p < 0.037) and the cannabis-control groups (p < 0.023), while it was not significant between the heroin-cannabis groups (p = 1). In conclusion, we suggest that heroin-and cannabis addicted patients seem to have a lower ratio of 2D:4D compared to healthy control subjects. Our findings can be considered promising as to whether prenatal hormonal factors are important in the etiopathogenesis of addiction. [ABSTRACT FROM AUTHOR]

Lipmaa's Computational Private Information Retrieval (CPIR) protocol is probably the most bandwidth efficient method in the literature, although its computational complexity is a limiting factor for practical applications as it is based on expensive public key operations. Utilizing binary decision diagrams (Bdd) and the Damgård–Jurik cryptosystem, Lipmaa's CPIR performs three modular exponentiation operations per internal node in Bdd. In this paper, we present a new CPIR protocol, which reduces the number of exponentiation operations to 1 per first-level internal nodes and 2 per other internal nodes of the Bdd. For 1024-bit exponents (i.e. 80-bit security level) and 32 768 items, when compared with the fastest parallel implementation in the literature on four cores, reducing the number of exponentiations yields a 1.22× speedup and the multiexponentiation technique adds 2.23× more on top of that. Overall, when combined, reducing the number of exponentiations, multi-exponentiation, parallelization on four cores and the hybrid approach can provide more than 300× speedup compared to the sequential implementation of the original method. [ABSTRACT FROM AUTHOR]

Networks are commonly used to model traffic patterns, social interactions, or web pages. The vertices in a network do not possess the same characteristics: some vertices are naturally more connected and some vertices can be more important. Closeness centrality (CC) is a global metric that quantifies how important is a given vertex in the network. When the network is dynamic and keeps changing, the relative importance of the vertices also changes. The best known algorithm to compute the CC scores makes it impractical to recompute them from scratch after each modification. In this paper, we propose S treamer , a distributed memory framework for incrementally maintaining the closeness centrality scores of a network upon changes. It leverages pipelined, replicated parallelism, and SpMM-based BFSs, and it takes NUMA effects into account. It makes maintaining the closeness centrality values of real-life networks with millions of interactions significantly faster and obtains almost linear speedups on a 64 nodes 8 threads/node cluster. [ABSTRACT FROM AUTHOR]

Centrality metrics such as betweenness and closeness have been used to identify important nodes in a network. However, it takes days to months on a high-end workstation to compute the centrality of today’s networks. The main reasons are the size and the irregular structure of these networks. While today’s computing units excel at processing dense and regular data, their performance is questionable when the data is sparse. In this work, we show how centrality computations can be regularized to reach higher performance. For betweenness centrality, we deviate from the traditional fine-grain approach by allowing a GPU to execute multiple BFSs at the same time. Furthermore, we exploit hardware and software vectorization to compute closeness centrality values on CPUs, GPUs and Intel Xeon Phi. Experiments show that only by reengineering the algorithms and without using additional hardware, the proposed techniques can speed up the centrality computations significantly: an improvement of a factor 5.9 on CPU architectures, 70.4 on GPU architectures and 21.0 on Intel Xeon Phi. [ABSTRACT FROM AUTHOR]

Literature search is one of the most important steps of academic research. With more than 100,000 papers published each year just in computer science, performing a complete literature search becomes a Herculean task. Some of the existing approaches and tools for literature search cannot compete with the characteristics of today’s literature, and they suffer from ambiguity and homonymy. Techniques based on citation information are more robust to the mentioned issues. Thus, we recently built a Web service called the advisor, which provides personalized recommendations to researchers based on their papers of interest. Since most recommendation methods may return redundant results, diversifying the results of the search process is necessary to increase the amount of information that one can reach via an automated search. This article targets the problem of result diversification in citation-based bibliographic search, assuming that the citation graph itself is the only information available and no categories or intents are known. The contribution of this work is threefold. We survey various random walk--based diversification methods and enhance them with the direction awareness property to allow users to reach either old, foundational (possibly well-cited and well-known) research papers or recent (most likely less-known) ones. Next, we propose a set of novel algorithms based on vertex selection and query refinement. A set of experiments with various evaluation criteria shows that the proposed γ-RLM algorithm performs better than the existing approaches and is suitable for real-time bibliographic search in practice. [ABSTRACT FROM AUTHOR]

Literature search is one of the most important steps of academic research. With more than 100,000 papers published each year just in computer science, performing a complete literature search becomes a Herculean task. Some of the existing approaches and tools for literature search cannot compete with the characteristics of today’s literature, and they suffer from ambiguity and homonymy. Techniques based on citation information are more robust to the mentioned issues. Thus, we recently built a Web service called the advisor, which provides personalized recommendations to researchers based on their papers of interest. Since most recommendation methods may return redundant results, diversifying the results of the search process is necessary to increase the amount of information that one can reach via an automated search. This article targets the problem of result diversification in citation-based bibliographic search, assuming that the citation graph itself is the only information available and no categories or intents are known. The contribution of this work is threefold. We survey various random walk--based diversification methods and enhance them with the direction awareness property to allow users to reach either old, foundational (possibly well-cited and well-known) research papers or recent (most likely less-known) ones. Next, we propose a set of novel algorithms based on vertex selection and query refinement. A set of experiments with various evaluation criteria shows that the proposed γ-RLM algorithm performs better than the existing approaches and is suitable for real-time bibliographic search in practice. [ABSTRACT FROM AUTHOR]

Abstract: The problem of task assignment in heterogeneous computing systems has been studied for many years with many variations. We consider the version in which communicating tasks are to be assigned to heterogeneous processors with identical communication links to minimize the sum of the total execution and communication costs. Our contributions are three fold: a task clustering method which takes the execution times of the tasks into account; two metrics to determine the order in which tasks are assigned to the processors; a refinement heuristic which improves a given assignment. We use these three methods to obtain a family of task assignment algorithms including multilevel ones that apply clustering and refinement heuristics repeatedly. We have implemented eight existing algorithms to test the proposed methods. Our refinement algorithm improves the solutions of the existing algorithms by up to 15% and the proposed algorithms obtain better solutions than these refined solutions. [Copyright &y& Elsevier]

We investigate the problem of partitioning the vertices of a directed acyclic graph into a given number of parts. The objective function is to minimize the number or the total weight of the edges having end points in different parts, which is also known as the edge cut. The standard load balancing constraint of having an equitable partition of the vertices among the parts should be met. Furthermore, the partition is required to be acyclic; i.e., the interpart edges between the vertices from different parts should preserve an acyclic dependency structure among the parts. In this work, we adopt the multilevel approach with coarsening, initial partitioning, and refinement phases for acyclic partitioning of directed acyclic graphs. We focus on two-way partitioning (sometimes called bisection), as this scheme can be used in a recursive way for multiway partitioning. To ensure the acyclicity of the partition at all times, we propose novel and efficient coarsening and refinement heuristics. The quality of the computed acyclic partitions is assessed by computing the edge cut. We also propose effective ways to use the standard undirected graph partitioning methods in our multilevel scheme. We perform a large set of experiments on a dataset consisting of (i) graphs coming from an application and (ii) some others corresponding to matrices from a public collection. We report significant improvements compared to the current state of the art. [ABSTRACT FROM AUTHOR]

Viruses of influenza A subtype H7 can be highly pathogenic and periodically infect humans. For example, there have been numerous outbreaks of H7 in the Americas and Europe since 1996. More recently, a reassortant H7N9 has emerged among humans and birds during 2013-2014 in China, Taiwan and Hong Kong. This H7N9 genome consists of genetic segments that assort with H7 and H9 viruses previously circulating in chickens and wild birds in China and ducks in Korea. Epidemic risk modellers have used agricultural, climatic and demographic data to predict that the virus will spread to northern Vietnam via poultry. To shed light on the traffic of H7 viruses in general, we examine genetic segments of influenza that have assorted with many strains of H7 viruses dating back to 1902. We focus on use cases from the United States, Italy and China. We apply a novel metric, betweenness, an associated phylogenetic visualization technique, transmission networks, and compare these with another technique, route mapping. In contrast to traditional views, our results illustrate that segments that assort with H7 viruses are spread frequently between the Americas and Eurasia. In summary, genetic segments that historically assort with H7 influenza viruses have been spread from China to: Australia, Czech Republic, Denmark, Egypt, Germany, Hong Kong, Italy, Japan, Mongolia, the Netherlands, New Zealand, Pakistan, South Africa, South Korea, Spain, Sweden, the UK, the US, and Vietnam. [ABSTRACT FROM AUTHOR]

For automata, synchronization, the problem of bringing an automaton to a particular state regardless of its initial state, is important. It has several applications in practice and is related to a fifty-year-old conjecture on the length of the shortest synchronizing word. Although using shorter words increases the effectiveness in practice, finding a shortest one (which is not necessarily unique) is NP-hard. For this reason, there exist various heuristics in the literature. However, high-quality heuristics such as SynchroP producing relatively shorter sequences are very expensive and can take hours when the automaton has tens of thousands of states. The SynchroP heuristic has been frequently used as a benchmark to evaluate the performance of the new heuristics. In this work, we first improve the runtime of SynchroP and its variants by using algorithmic techniques. We then focus on adapting SynchroP for many-core architectures, and overall, we obtain more than 1000 × speedup on GPUs compared to naive sequential implementation that has been frequently used as a benchmark to evaluate new heuristics in the literature. We also propose two SynchroP variants and evaluate their performance. [ABSTRACT FROM AUTHOR]