Search

• Existing synchronization heuristics do not scale due to quadratic space complexity. • We propose a simple approach to avoid memory usage thanks to massive parallelism. • We use different parallelization approaches on CPUs and GPUs, in a hybrid way. • A different treatment of parallelism is useful at different phases of the algorithm. • Our algorithms can synchronize a billion-state automaton in around 4 mins. Synchronizing sequences for large-scale automata have gained popularity recently due to their practical use cases especially to have a faster and better testing process. In many applications, shorter sequences imply less overhead and faster processing time but the problem of finding the shortest synchronizing sequence is NP-hard and requires heuristic approaches to be solved. State-of-the-art heuristics manage to obtain desirable, short sequences with relatively small execution times. However, all these heuristics suffer their quadratic memory complexity and fail to scale when the input automaton gets larger. In this paper, we propose an approach exploiting GPUs and hybrid parallelism which can generate synchronizing sequences even for billion-scale automata, in a short amount of time. Overall, the algorithm can generate a synchronizing sequence for a random automaton with n = 10 8 states in 12.1 s, n = 5 × 10 8 states in 69.1 s, and billion states in 148.2 s. [ABSTRACT FROM AUTHOR]

We present a configurable, hybrid, and parallel covering array constructor, called CHiP. CHiP is parallel in that it utilizes vast amount of parallelism provided by graphics processing units (GPUs). CHiP is hybrid in that it bundles the bests of two construction approaches for computing covering arrays; a metaheuristic search-based approach for efficiently covering a large portion of the required combinations and a constraint satisfaction-based approach for effectively covering the remaining hard-to-cover-by-chance combinations. CHiP is configurable in that a trade-off between covering array sizes and construction times can be made. We have conducted a series of experiments, in which we compared the efficiency and effectiveness of CHiP to those of a number of existing constructors by using both full factorial designs and well-known benchmarks. In these experiments, we report new upper bounds on covering array sizes, demonstrating the effectiveness of CHiP, and the first results for a higher coverage strength, demonstrating the scalability of CHiP.

Influence maximization (IM) is the problem of finding a seed vertex set that maximizes the expected number of vertices influenced under a given diffusion model. Due to the NP-Hardness of finding an optimal seed set, high-quality yet expensive approximation algorithms have been frequently used. In addition, lightweight, sketch-based approaches, which do not step-by-step simulate the influence process, have been proposed in the literature to cope with the scale of today's networks. In this work, we describe a fast, error-adaptive approach that leverages Count-Distinct sketches and hash-based fused sampling to avoid step-by-step simulations and estimate the number of influenced vertices throughout a diffusion. Furthermore, for faster estimations, the sketches of a vertex for consecutive simulations are stored adjacently in memory. This allows the proposed algorithm to estimate the number of influenced vertices for multiple simulations at once. For faster processing, the proposed method automatically rebuilds the sketches after observing estimation errors above a given threshold. Our experimental results show that the proposed algorithm yields seed sets with comparable quality while being up to 3 , 337 × faster than a state-of-the-art, high-quality influence maximization algorithm. In addition, it is up to 63× faster than a sketch-based approach while producing seed sets with 2%–10% better influence scores. [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 awarenessproperty 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.

Graphs and matrices are widely used in algorithms for social network analyses. Since the number of interactions is much less than the possible number of interactions, the graphs and matrices used in the analyses are usually sparse. In this paper, we propose an efficient implementation of a sparse-matrix computation which arises in our publicly available citation recommendation service theadvisoras well as in many other recommendation systems. The recommendation algorithm uses a sparse matrix generated from the citation graph. We observed that the nonzero pattern of this matrix is highly irregular and the computation suffers from high number of cache misses. We propose techniques for storing the matrix in memory efficiently and we reduced the number of cache misses with ordering and partitioning. Experimental results show that our techniques are highly efficient in reducing the query processing time which is highly crucial for a web service.

The ability to summarize a large number of network patterns discovered from biomedical data provides valuable information for use in many applications. We show that several variants of the problem are all NP-hard, and merging network patterns is a practical solution for these applications. In this work, we propose an algorithmic framework for merging network patterns. We have developed fast algorithms under this general framework which supports several types of biomedical network data. In addition, our empirical study demonstrates that our algorithms are efficient in merging a large number of biomedical network patterns and can be configured for various knowledge discovery purposes.The ability to summarize a large number of network patterns discovered from biomedical data provides valuable information for use in many applications. We show that several variants of the problem are all NP-hard, and merging network patterns is a practical solution for these applications. In this work, we propose an algorithmic framework for merging network patterns. We have developed fast algorithms under this general framework which supports several types of biomedical network data. In addition, our empirical study demonstrates that our algorithms are efficient in merging a large number of biomedical network patterns and can be configured for various knowledge discovery purposes.

Abstract: Broadcast encryption (BE) deals with secure transmission of a message to a group of users such that only an authorized subset of users can decrypt the message. Some of the most effective BE schemes in the literature are the tree-based schemes of complete subtree (CS) and subset difference (SD). The key distribution trees in these schemes are traditionally constructed without considering user preferences. In fact these schemes can be made significantly more efficient when user profiles are taken into account. In this paper, we consider this problem and study how to construct the CS and SD trees more efficiently according to user profiles. We first analyze the relationship between the transmission cost and the user profile distribution and prove a number of key results in this aspect. Then we propose several optimization algorithms which can reduce the bandwidth requirement of the CS and SD schemes significantly. This reduction becomes even more significant when a number of free riders can be allowed in the system. [Copyright &y& Elsevier]

Abstract: Broadcast encryption (BE) deals with secure transmission of a message to a group of receivers such that only an authorized subset of receivers can decrypt the message. The transmission cost of a BE system can be reduced considerably if a limited number of free riders can be tolerated in the system. In this paper, we study the problem of how to optimally place a given number of free riders in a subset-difference (SD)-based BE system, which is currently the most efficient BE scheme in use and has also been incorporated in standards, and we propose a polynomial-time optimal placement algorithm and three more efficient heuristics for this problem. Simulation experiments show that SD-based BE schemes can benefit significantly from the proposed algorithms. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate how threshold cryptography can be conducted with the Asmuth–Bloom secret sharing scheme and present three novel function sharing schemes for RSA, ElGamal and Paillier cryptosystems. To the best of our knowledge, these are the first provably secure threshold cryptosystems realized using the Asmuth–Bloom secret sharing. Proposed schemes are comparable in performance to earlier proposals in threshold cryptography. [Copyright &y& Elsevier]

In this study, static and vibration behavior of a curved thick sandwich-structured composite composed of a honeycomb core layer and two face-sheets reinforced with carbon nanotubes is investigated. The governing equations are derived using three-dimensional elasticity equations and Hamilton's principle. The problem domain is discretized following Gauss–Lobatto sampling approach. To numerically solve the governing equations, a spectral method based on Chebyshev polynomials is used and a CPU–GPU based hybrid solver is developed. The presented approach is validated by comparing the predicted natural frequencies and deformation of the structure to those obtained from finite element analysis. The results show that in-house CPU–GPU based spectral solution approach decreases the computational duration remarkably and predicts the dynamic and static behavior of the system accurately. Since composite materials offer great flexibility in tailoring the dynamic behavior of the structure, an optimization study is also performed to benefit from the developed computationally efficient solver. In this study, the CNT orientations are selected as design variables to maximize the fundamental frequency of the structure. Based on the analyzed cases for different thickness ratios, curvature amounts, volume content, and distributions of CNTs, it is shown that the vibration behavior of the structure can be significantly tailored. [ABSTRACT FROM AUTHOR]