Robust and scalable techniques for mining patterns or subgraphs in protein protein interaction (PPI) networks can help identify functionally relevant and coherent subnetworks. Recently, researchers have focused on int...
详细信息
ISBN:
(纸本)9781943436071
Robust and scalable techniques for mining patterns or subgraphs in protein protein interaction (PPI) networks can help identify functionally relevant and coherent subnetworks. Recently, researchers have focused on integrating genes attributes with the protein-protein interaction networks for mining connected subnetworks whose genes are similar in a subset of attributes. However, most of the proposed approaches assume that these subnetworks are dense. While detecting dense and cohesive subnetworks is desirable, the density factor can prevent these algorithms from reporting highly cohesive subgraphs which are not particularly dense. In this paper, we propose a parallel algorithm for mining maximal cohesive subgraphs from node-attributed networks. Experiments on two real interaction networks and gene expression attributes demonstrate the effectiveness of the proposed algorithm. Moreover, biological enrichment analysis of the reported patterns show that the patterns are biologically relevant and enriched with known biological processes and KEGG pathways.
The plane sweep algorithm is a foundational algorithm for many geometric and spatial computations;thus, improvements in the algorithm have far reaching effects in many applications. In this paper, we examine the perfo...
详细信息
The plane sweep algorithm is a foundational algorithm for many geometric and spatial computations;thus, improvements in the algorithm have far reaching effects in many applications. In this paper, we examine the performance of the serial plane sweep algorithm, and introduce a parallelization technique for the algorithm that is suitable to multi-core computers. The parallelization technique is described in detail and shown to be correct. Finally, experiments are performed using multiple data sets on computers with varying numbers of processing cores. We show that our algorithm achieves significant speedups over the serial plane sweep algorithm using a wide range of input parameters;thus, our algorithm achieves good performance without the need to tune the input parameters for specific input cases.
Mathematical models with fractional-order differential operators are computationally expensive due to the non-local nature of these operators. In this work, we construct and investigate parallel solvers for problems d...
详细信息
This paper touches upon the computer simulation of the propagation of elastic waves in three-dimensional multilayer fractured media. The dynamic processes are described using the defining system of equations in the pa...
详细信息
This paper touches upon the computer simulation of the propagation of elastic waves in three-dimensional multilayer fractured media. The dynamic processes are described using the defining system of equations in the partial derivatives of the deformed solid mechanics. The numerical solution of this system is carried out via the grid-characteristic method on curvilinear structural grids. The fractured nature of the medium is accounted for by explicitly selecting the boundaries of individual cracks and setting special boundary conditions in them. Various models of heterogeneous deformed media with a fractured structures are considered: a homogeneous medium, a medium with horizontal boundaries, a medium with inclined boundaries, and a medium curvilinear boundaries. The wave fields detected on the surface are obtained, and their structures are analyzed. It is demonstrated that it is possible to detect the waves scattered from fractured media even in the case of nonparallel (inclined and curvilinear) boundaries of geological layers.
Full use of the parallel computation capabilities of present and expected CPUs and GPUs requires use of vector extensions. Yet many actors in data flow systems for digital signal processing have internal state (or, eq...
详细信息
Full use of the parallel computation capabilities of present and expected CPUs and GPUs requires use of vector extensions. Yet many actors in data flow systems for digital signal processing have internal state (or, equivalently, an edge that loops from the actor back to itself) that impose serial dependencies between actor invocations that make vectorizing across actor invocations impossible. Ideally, issues of inter-thread coordination required by serial data dependencies should be handled by code written by parallel programming experts that is separate from code specifying signal processing operations. The purpose of this paper is to present one approach for so doing in the case of actors that maintain state. We propose a methodology for using the parallel scan (also known as prefix sum) pattern to create algorithms for multiple simultaneous invocations of such an actor that results in vectorizable code. Two examples of applying this methodology are given: (1) infinite impulse response filters and (2) finite state machines. The correctness and performance of the resulting IIR filters and one class of FSMs are studied.
The conversion of traditional film into stereo 3D has become an important problem in the past decade. One of the main bottlenecks is a disocclusion step, which in commercial 3D conversion is usually done by teams of a...
详细信息
The conversion of traditional film into stereo 3D has become an important problem in the past decade. One of the main bottlenecks is a disocclusion step, which in commercial 3D conversion is usually done by teams of artists armed with a toolbox of inpainting algorithms. A current difficulty in this is that most available algorithms either are too slow for interactive use or provide no intuitive means for users to tweak the output. In this paper we present a new fast inpainting algorithm based on transporting along automatically detected splines, which the user may edit. Our algorithm is implemented on the GPU and fills the inpainting domain in successive shells that adapt their shape on the fly. In order to allocate GPU resources as efficiently as possible, we propose a parallel algorithm to track the inpainting interface as it evolves, ensuring that no resources are wasted on pixels that are not currently being worked on. Theoretical analyses of the time and processor complexity of our algorithm without and with tracking (as well as numerous numerical experiments) demonstrate the merits of the latter. Our transport mechanism is similar to the one used in coherence transport [F. Bornemann and T. Marz, J. Math. Imaging Vision, 28 (2007), pp. 259-278;T. Marz, SIAM J. Imaging Sci., 4 (2011), pp. 981-1000] but improves upon it by correcting a "kinking" phenomenon whereby extrapolated isophotes may bend at the boundary of the inpainting domain. Theoretical results explaining this phenomenon and its resolution are presented. Although our method ignores texture, in many cases this is not a problem due to the thin inpainting domains in 3D conversion. Experimental results show that our method can achieve a visual quality that is competitive with the state of the art while maintaining interactive speeds and providing the user with an intuitive interface to tweak the results.
This paper presents a generic approach to highly efficient image registration in two and three dimensions. Both monomodal and multimodal registration problems are considered. We focus on the important class of affine-...
详细信息
This paper presents a generic approach to highly efficient image registration in two and three dimensions. Both monomodal and multimodal registration problems are considered. We focus on the important class of affine-linear transformations in a derivative-based optimization framework. Our main contribution is an explicit formulation of the objective function gradient and Hessian approximation that allows for very efficient, parallel derivative calculation with virtually no memory requirements. The flexible parallelism of our concept allows for direct implementation on various hardware platforms. Derivative calculations are fully matrix free and operate directly on the input data, thereby reducing the auxiliary space requirements from to . The proposed approach is implemented on multicore CPU and GPU. Our GPU code outperforms a conventional matrix-based CPU implementation by more than two orders of magnitude, thus enabling usage in real-time scenarios. The computational properties of our approach are extensively evaluated, thereby demonstrating the performance gain for a variety of real-life medical applications.
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 appl...
详细信息
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 DamgArd-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.22x speedup and the multi-exponentiation technique adds 2.23x 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 300x speedup compared to the sequential implementation of the original method.
A numerical approach for solving gas dynamics on Cartesian grids is considered which employs an implicit time marching scheme with the matrix-free Lower-Upper Symmetric Gauss-Seidel (LU-SGS) method for solving discret...
详细信息
A numerical approach for solving gas dynamics on Cartesian grids is considered which employs an implicit time marching scheme with the matrix-free Lower-Upper Symmetric Gauss-Seidel (LU-SGS) method for solving discrete equations. Boundary conditions are treated with an embedded-boundary method. The method has two attractive features-(1) algorithmic uniformity of calculations and (2) structured memory accesses that well fit massively parallel architectures with GPU accelerators. We propose a novel CUDA+MPI computational algorithm scalable up to hundreds of GPUs and give in-depth analysis of its implementation (interoperability issues, libraries tuning).
Content delivery networks have been providing content delivery services for the last two decades using their own infrastructure. Now-a-days content delivery networks have the better option of using storage cloud sites...
详细信息
暂无评论