Search

Big data analytic technologies such as Hadoop and Spark run on compute clusters that are managed by resource managers such as YARN. YARN manages resources available to individual applications, thereby affecting job performance. Manual tuning of YARN tuning parameters can result in sub-optimal and brittle performance. Parameters that are optimal for one job may not be well suited to another. In this paper we present KERMIT, the first on-line automatic tuning system for YARN. KERMIT optimizes in real-time YARN memory and CPU allocations to individual YARN containers by analysing container response-time performance. Unlike previous automatic tuning methods for specific systems such as Spark or Hadoop, this is the first study that focuses on the more general case of on-line, real-time tuning of YARN container density and how this affects performance of applications running on YARN. KERMIT employs the same tuning code to automatically tune any system that uses YARN, including both Spark and Hadoop. The effectiveness of our technique was evaluated for Hadoop and Spark jobs using the Terasort, TPCx-HS, and SMB benchmarks. KERMIT was able to achieve an efficiency of more than 92% of the best possible tuning configuration (exhaustive search of the parameter space) and up to 30% faster than basic manual tuning.

Selim Akl has been a ground breaking pioneer in the field of parallel sorting algorithms. His ‘Parallel Sorting Algorithms’ book [12], published in 1985, has been a standard text for researchers and students. Here we discuss recent advances in parallel sorting methods for many-core GPUs. We demonstrate that parallel deterministic sample sort for GPUs (GPU Bucket Sort) is not only considerably faster than the best comparison-based sorting algorithm for GPUs (Thrust Merge) but also as fast as randomized sample sort for GPUs (GPU Sample Sort). However, deterministic sample sort has the advantage that bucket sizes are guaranteed and therefore its running time does not have the input data dependent fluctuations that can occur for randomized sample sort.

This paper presents VelocityOLAP (VOLAP), a distributed real-time OLAP system for high velocity data. VOLAP makes use of dimension hierarchies, is highly scalable, and exploits both multi-core and multi-processor parallelism. In contrast to other high performance OLAP systems such as SAP HANA or IBM Netezza that rely on vertical scaling or special purpose hardware, VOLAP supports cost-efficient horizontal scaling on commodity hardware or modest cloud instances. Experiments on 20 Amazon EC2 nodes with TPC-DS data show that VOLAP is capable of bulk ingesting data at over 400 thousand items per second, and processing streams of interspersed insertions and aggregate queries at a rate of approximately 50 thousand insertions and 20 thousand aggregate queries per second with a database of 1 billion items. VOLAP is designed to support applications that perform large aggregate queries, and provides similar high performance for aggregations ranging from a few items to nearly the entire database.

E10 is a new maturity locus in soybean and FT4 is the predicted/potential functional gene underlying the locus. Flowering and maturity time traits play crucial roles in economic soybean production. Early maturity is critical for north and west expansion of soybean in Canada. To date, 11 genes/loci have been identified which control time to flowering and maturity; however, the molecular bases of almost half of them are not yet clear. We have identified a new maturity locus called “E10” located at the end of chromosome Gm08. The gene symbol E10e10 has been approved by the Soybean Genetics Committee. The e10e10 genotype results in 5–10 days earlier maturity than E10E10. A set of presumed E10E10 and e10e10 genotypes was used to identify contrasting SSR and SNP haplotypes. These haplotypes, and their association with maturity, were maintained through five backcross generations. A functional genomics approach using a predicted protein–protein interaction (PPI) approach (Protein–protein Interaction Prediction Engine, PIPE) was used to investigate approximately 75 genes located in the genomic region that SSR and SNP analyses identified as the location of the E10 locus. The PPI analysis identified FT4 as the most likely candidate gene underlying the E10 locus. Sequence analysis of the two FT4 alleles identified three SNPs, in the 5′UTR, 3′UTR and fourth exon in the coding region, which result in differential mRNA structures. Allele-specific markers were developed for this locus and are available for soybean breeders to efficiently develop earlier maturing cultivars using molecular marker assisted breeding.

In this paper, we study the potential performance improvements for catastrophe (CAT) modelling systems that can be achieved through parallelisation on a cell processor [Cell Broadband Engine Architecture (Cell/BE)]. We studied and parallelised a critical section of CAT modelling, the so-called inner loop and implemented it on a Cell/BE running on a regular Playstation 3 platform. The Cell/BE is known to be a challenging environment for software development. In particular, the small internal storage available at each synergistic processing element (SPE) of the Cell/BE is a considerable challenge for CAT modelling because the CAT-modelling algorithm requires frequent accesses to large lookup tables. Our parallel solution is a combination of multiple techniques: streaming data to the SPEs and parallelising inner loop computations, building caches on the SPEs to store parts of the large CAT modelling lookup tables, vectorising the computation on the SPEs and double-buffering the file I/O. On a (Playstation 3) Cell/BE with six active SPEs and four-way vectorisation on each SPE, we were able to measure a sustained 16 × speedup for our parallel CAT-modelling code over a wide range of data sizes for real-life Japanese earthquake data.

It is well known that using random RNA/DNA sequences for SELEX experiments will generally yield low-complexity structures. Early experimental results suggest that having a structurally diverse library, which, for instance, includes high-order junctions, may prove useful in finding new functional motifs. Here, we develop two computational methods to generate sequences that exhibit higher structural complexity and can be used to increase the overall structural diversity of initial pools for in vitro selection experiments. Random Filtering selectively increases the number of five-way junctions in RNA/DNA pools, and Genetic Filtering designs RNA/DNA pools to a specified structure distribution, whether uniform or otherwise. We show that using our computationally designed DNA pool greatly improves access to highly complex sequence structures for SELEX experiments (without losing our ability to select for common one-way and two-way junction sequences).

The length-constrained heaviest path (LCHP) in a weighted tree T, where each edge is assigned a weight and a length, is the path P in T with maximum total path weight and total path length bounded by a given value B. This paper presents an O(nlogn) time LCHP algorithm which utilizes a data structure constructed from the spine decomposition of the input tree. This is an improvement over the existing algorithm by Wu et al. (1999), which runs in O(nlog^2n) time. Our method also improves on a previous O(nlogn) time algorithm by Kim (2005) for the special case of finding a longest nonnegative path in a constant degree tree in that we can handle trees of arbitrary degree within the same time bounds.

Protein-protein interaction (PPI) maps provide insight into cellular biology and have received considerable attention in the post-genomic era. While large-scale experimental approaches have generated large collections of experimentally determined PPIs, technical limitations preclude certain PPIs from detection. Recently, we demonstrated that yeast PPIs can be computationally predicted using re-occurring short polypeptide sequences between known interacting protein pairs. However, the computational requirements and low specificity made this method unsuitable for large-scale investigations. Here, we report an improved approach, which exhibits a specificity of approximately 99.95% and executes 16,000 times faster. Importantly, we report the first all-to-all sequence-based computational screen of PPIs in yeast, Saccharomyces cerevisiae in which we identify 29,589 high confidence interactions of approximately 2 x 10(7) possible pairs. Of these, 14,438 PPIs have not been previously reported and may represent novel interactions. In particular, these results reveal a richer set of membrane protein interactions, not readily amenable to experimental investigations. From the novel PPIs, a novel putative protein complex comprised largely of membrane proteins was revealed. In addition, two novel gene functions were predicted and experimentally confirmed to affect the efficiency of non-homologous end-joining, providing further support for the usefulness of the identified PPIs in biological investigations.

This article addresses the query performance issue for Relational OLAP (ROLAP) datacubes. We present RCUBE, a distributed multidimensional ROLAP indexing scheme which is practical to implement, requires only a small communication volume, and is fully adapted to distributed disks. Our solution is efficient for spatial searches in high dimensions and scalable in terms of data sizes, dimensions, and number of processors. Our method is also incrementally maintainable. Using “surrogate” group-bys, it allows for the efficient processing of arbitrary OLAP queries on partial cubes, where not all of the group-bys have been materialized. Our experiments with RCUBE show that the ROLAP advantage of better scalability, in comparison to MOLAP, can be maintained while providing a fast and flexible index for OLAP queries.

We present "Pipe 'n Prune" (PnP), a new hybrid method for iceberg-cube query computation. The novelty of our method is that it achieves a tight integration of top-down piping for data aggregation with bottom-up a priori data pruning. A particular strength of PnP is that it is efficient for all of the following scenarios: (1) Sequential iceberg-cube queries, (2) External memory iceberg-cube queries, and (3) Parallel iceberg-cube queries on shared-nothing PC clusters with multiple disks. We performed an extensive performance analysis of PnP for the above scenarios with the following main results: In the first scenario PnP performs very well for both dense and sparse data sets, providing an interesting alternative to BUC and Star-Cubing. In the second scenario PnP shows a surprisingly efficient handling of disk I/O, with an external memory running time that is less than twice the running time for full in-memory computation of the same iceberg-cube query. In the third scenario PnP scales very well, providing near linear speedup for a larger number of processors and thereby solving the scalability problem observed for the parallel iceberg-cubes proposed by Ng et al.

The subtree prune and regraft distance (d SPR ) between phylogenetic trees is important both as a general means of comparing phylogenetic tree topologies as well as a measure of lateral gene transfer (LGT). Although there has been exten- sive study on the computation of d SPR and similar metrics between rooted trees, much less is known about SPR distances for unrooted trees, which often arise in practice when the root is unresolved. We show that unrooted SPR distance compu- tation is NP-Hard and verify which techniques from related work can and cannot be applied. We then present an effi cient heuristic algorithm for this problem and benchmark it on a variety of synthetic datasets. Our algorithm computes the exact SPR distance between unrooted tree, and the heuristic element is only with respect to the algorithm's computation time. Our method is a heuristic version of a fi xed parameter tractability (FPT) approach and our experiments indicate that the running time behaves similar to FPT algorithms. For real data sets, our algorithm was able to quickly compute d SPR for the majority of trees that were part of a study of LGT in 144 prokaryotic genomes. Our analysis of its performance, especially with respect to searching and reduction rules, is applicable to computing many related distance measures. 1. Introduction trees are used to describe evolutionary relationships. DNA or protein sequences are associated with the leaves of the tree and the internal nodes correspond to speciation or gene duplication events. In order to model ancestor-descendant relationships on the tree, a direction must be associated with its edges by assigning a root. Often, insuffi cient information exists to determine the root and the tree is left unrooted. Unrooted trees still provide a notion of evolutionary relationship between organ- isms even if the direction of descent remains unknown. The phylogenetic tree representation has recently come under scrutiny with critics claiming that it is too simple to properly model microbial evolution, particularly in the presence of lateral gene trans- fer (LGT) events (Doolittle, 1999). A LGT is the transfer of genetic material between species by means other than inheritance and thus cannot be represented in a tree as it would create a cycle. The preva- lence of LGT events in microbial evolution can, however, still be studied using phylogenetic trees. Given a pair of trees describing the same sets of species, each constructed using different sets of genes, a LGT event corresponds to a displacement of a common subtree, referred to as a SPR operation. The SPR distance is the minimum number of SPR operations, denoted by d SPR , that explain the topological differences between a pair of trees. It is equivalent to the number of transfers in the most parsimonious LGT scenario (Beiko and Hamilton, 2006). In general, d SPR can be used as a measure of the topo- logical difference between two trees, e.g. for comparing the outputs of different tree construction algorithms. Tree bisection and reconnection (TBR) is a generalization of SPR that allows the pruned subtree to be rerooted before being regrafted. Computation of the TBR distance (d TBR ) was shown to be NP-hard (nondeterministic polynomial-time hard) by Allen and Steel (2001), who also provided two rules that reduce two input trees to a size that is a linear functions of d TBR without altering their distance. These rules, which reduce common chains and subtrees, also form the basis of algorithms that compute the SPR distance between rooted trees (d rSPR ) (Bordewich and Semple, 2004) as well as hybridization number (h) (Bordewich et al. 2007), see Section 3.3. Such algorithms proceed as follows. First the distance problem is shown to be equivalent to counting components of a maximum agreement forest

Parallel graph algorithm design is a very well studied topic. Many results have been presented for the PRAM model. However, these algorithms are inherently fine grained and experiments show that PRAM algorithms do often not achieve the expected speedup on real machines because of large message overheads. In this paper, we present coarse grained parallel graph algorithms with small message overheads that solve the following standard graph problems related to graph matching: finding maximum matchings in convex bipartite graphs, and finding maximum weight matchings in trees. To our knowledge, these are the first efficient parallel algorithms for these problems that are designed for standard commercial parallel machines such as off-the-shelf processor clusters.

This paper presents an improved parallel method for generating ROLAP data cubes on a shared-nothing multiprocessor based on a novel optimized data partitioning technique. Since no shared disk is required, our method can be used for highly scalable processor clusters consisting of standard PCs with local disks only, connected via a data switch. Experiments show that our improved parallel method provides optimal, linear, speedup for at least 32 processors. The approach taken, which uses a ROLAP representation of the data cube, is well suited for large data warehouses and high dimensional data, and supports the generation of both fully materialized and partially materialized data cubes.

On-line Analytical Processing (OLAP) has become one of the most powerful and prominent technologies for knowledge discovery in VLDB (Very Large Database) environments. Central to the OLAP paradigm is the data cube, a multi-dimensional hierarchy of aggregate values that provides a rich analytical model for decision support. Various sequential algorithms for the efficient generation of the data cube have appeared in the literature. However, given the size of contemporary data warehousing repositories, multi-processor solutions are crucial for the massive computational demands of current and future OLAP systems. In this paper we discuss the cgmCUBE Project, a multi-year effort to design and implement a multi-processor platform for data cube generation that targets the relational database model (ROLAP). More specifically, we discuss new algorithmic and system optimizations relating to (1) a thorough optimization of the underlying sequential cube construction method and (2) a detailed and carefully engineered cost model for improved parallel load balancing and faster sequential cube construction. These optimizations were key in allowing us to build a prototype that is able to produce data cube output at a rate of over one TeraByte per hour.

Given a set S of s points in the plane, where do we place a new point, p, in order to maximize the area of its region in the Voronoi diagram of S and p? We study the case where the Voronoi neighbors of p are in convex position, and prove that there is at most one local maximum.

In this paper, we present CGMgraph, the first integrated library of parallel graph methods for PC clusters based on Coarse Grained Multicomputer (CGM) algorithms. CGMgraph implements parallel methods for various graph problems. Our implementations of deterministic list ranking, Euler tour, connected components, spanning forest, and bipartite graph detection are, to our knowledge, the first efficient implementations for PC clusters. Our library also includes CGMlib, a library of basic CGM tools such as sorting, prefix sum, one-to-all broadcast, all-to-one gather, h-Relation, all-to-all broadcast, array balancing, and CGM partitioning. Both libraries are available for download at http://www.scs.carleton.ca/~cgm. In the experimental part of this paper, we demonstrate the performance of our methods on four different architectures: a gigabit connected high performance PC cluster, a smaller PC cluster connected via fast ethernet, a network of workstations, and a shared memory machine. Our experiments show that our library provides good parallel speedup and scalability on all four platforms. The communication overhead is, in most cases, small and does not grow significantly with an increasing number of processors. This is a very important feature of CGM algorithms which makes them very efficient in practice.

The pre-computation of data cubes is critical to improving the response time of on-line analytical processing (OLAP) systems and can be instrumental in accelerating data mining tasks in large data warehouses. In order to meet the need for improved performance created by growing data sizes, parallel solutions for generating the data cube are becoming increasingly important. The paper presents a parallel method for generating data cubes on a shared-nothing multiprocessor. Since no (expensive) shared disk is required, our method can be used on low cost Beowulf style clusters consisting of standard PCs with local disks connected via a data switch. Our approach uses a ROLAP representation of the data cube where views are stored as relational tables. This allows for tight integration with current relational database technology. We have implemented our parallel shared-nothing data cube generation method and evaluated it on a PC cluster, exploring relative speedup, local vs. global schedule trees, data skew, cardinality of dimensions, data dimensionality, and balance tradeoffs. For an input data set of 2000000 rows (72 Megabytes), our parallel data cube generation method achieves close to optimal speedup; generating a full data cube of /spl ap/227 million rows (5.6 Gigabytes) on a 16 processors cluster in under 6 minutes. For an input data set of 10,000,000 rows (360 Megabytes), our parallel method, running on a 16 processor PC cluster, created a data cube consisting of /spl ap/846 million rows (21.7 Gigabytes) in under 47 minutes.

Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper, we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded-tree search phase of FPT algorithms. We apply our methodology to the k-Vertex Cover problem which has important applications in, for example, the analysis of multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-Vertex Cover problem using C and the MPI communication library, and tested it on a 32-node Beowulf cluster. This is the first experimental examination of parallel FPT techniques. As part of our experiments, we solved larger instances of k-Vertex Cover than in any previously reported implementations. For example, our code can solve problem instances with k⩾400 in less than 1.5h.

This paper presents a general methodology for the efficient parallelization of existing data cube construction algorithms. We describe two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both partitioning strategies assign subcubes to individual processors in such a way that the loads assigned to the processors are balanced. Our methods reduce inter processor communication overhead by partitioning the load in advance instead of computing each individual group-by in parallel. Our partitioning strategies create a small number of coarse tasks. This allows for sharing of prefixes and sort orders between different group-by computations. Our methods enable code reuse by permitting the use of existing sequential (external memory) data cube algorithms for the subcube computations on each processor. This supports the transfer of optimized sequential data cube code to a parallel setting. The bottom-up partitioning strategy balances the number of single attribute external memory sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated group-by sizes. Both partitioning approaches can be implemented on any shared disk type parallel machine composed of p processors connected via an interconnection fabric and with access to a shared parallel disk array. We have implemented our parallel top-down data cube construction method in C++ with the MPI message passing library for communication and the LEDA library for the required graph algorithms. We tested our code on an eight processor cluster, using a variety of different data sets with a range of sizes, dimensions, density, and skew. Comparison tests were performed on a SunFire 6800. The tests show that our partitioning strategies generate a close to optimal load balance between processors. The actual run times observed show an optimal speedup of p.

Blockwise access to data is a central theme in the design of efficient ex- ternal memory (EM) algorithms. A second important issue, when more than one disk is present, is fully parallel disk I/O. In this paper we present a simple, deterministic simulation technique which transforms certain Bulk Synchronous Parallel (BSP) algorithms into efficient parallel EM algorithms. It optimizes blockwise data access and parallel disk I/O and, at the same time, utilizes multiple processors connected via a communication network or shared memory. We obtain new improved paral- lel EM algorithms for a large number of problems including sorting, permutation, matrix transpose, several geometric and GIS problems including three-dimensional convex hulls (two-dimensional Voronoi diagrams), and various graph problems. We show that certain parallel algorithms known for the BSP model can be used to ob- tain EM algorithms that meet well known I/O complexity lower bounds for various problems, including sorting.

In this paper we present deterministic parallel algorithms for the coarse-grained multicomputer (CGM) and bulk synchronous parallel (BSP) models for solving the following well-known graph problems: (1) list ranking, (2) Euler tour construction in a tree, (3) computing the connected components and spanning forest, (4) lowest common ancestor preprocessing, (5) tree contraction and expression tree evaluation, (6) computing an ear decomposition or open ear decomposition, and (7) 2-edge connectivity and biconnectivity (testing and component computation). The algorithms require O(log p) communication rounds with linear sequential work per round (p = no. processors, N = total input size). Each processor creates, during the entire algorithm, messages of total size O(log (p) (N/p)) . The algorithms assume that the local memory per processor (i.e., N/p ) is larger than p e , for some fixed e > 0 . Our results imply BSP algorithms with O(log p) supersteps, O(g log (p) (N/p)) communication time, and O(log (p) (N/p)) local computation time. It is important to observe that the number of communication rounds/ supersteps obtained in this paper is independent of the problem size, and grows only logarithmically with respect to p . With growing problem size, only the sizes of the messages grow but the total number of messages remains unchanged. Due to the considerable protocol overhead associated with each message transmission, this is an important property. The result for Problem (1) is a considerable improvement over those previously reported. The algorithms for Problems (2)—(7) are the first practically relevant parallel algorithms for these standard graph problems.

Background Our knowledge of global protein-protein interaction (PPI) networks in complex organisms such as humans is hindered by technical limitations of current methods. Results On the basis of short co-occurring polypeptide regions, we developed a tool called MP-PIPE capable of predicting a global human PPI network within 3 months. With a recall of 23% at a precision of 82.1%, we predicted 172,132 putative PPIs. We demonstrate the usefulness of these predictions through a range of experiments. Conclusions The speed and accuracy associated with MP-PIPE can make this a potential tool to study individual human PPI networks (from genomic sequences alone) for personalized medicine. Electronic supplementary material The online version of this article (doi:10.1186/s12859-014-0383-1) contains supplementary material, which is available to authorized users.

In this article we discuss what kind of information can be obtained from W ord N et and what kind of information should be added to W ord N et in order to make it better suitable for the support of the C olor -X method. We will present an extension of W ord N et (called W ord N et ++), which contains a number of special types of relationships that are not available in W ord N et . Additionally, W ord N et ++ is instantiated with knowledge about some particular domain. Also, we will show some example scenarios for how W ord N et ++ can be used for verification of C olor -X-models and we will show how this lexicon can be used in a special C ase -tool for supporting C olor -X.

We present a parallel algorithm for solving thenext element search problemon a set of line segments, using a BSP-like model referred to as thecoarse grained multicomputer(CGM). The algorithm requiresO(1) communication rounds (h-relations withh=O(n/p)),O((n/p)logn) local computation, andO((n/p)logp) memory per processor, assumingn/p?p. Our result implies solutions to the point location, trapezoidal decomposition, and polygon triangulation problems. A simplified version for axis-parallel segments requires onlyO(n/p) memory per processor, and we discuss an implementation of this version. As in a previous paper by Develliers and Fabri (Int. J. Comput. Geom. Appl.6(1996), 487?506), our algorithm is based on a distributed implementation of segment trees which are of sizeO(nlogn). This paper improves onop. cit.in several ways: (1) It studies the more general next element search problem which also solves, e.g., planar point location. (2) The algorithms require onlyO((n/p)logn) local computation instead ofO(logp*(n/p)logn). (3) The algorithms require onlyO((n/p)logp) local memory instead ofO((n/p)logn).

We present a randomized parallel algorithm for constructing the three-dimensional convex hull on a generic p-processor coarse-grained multicomputer with arbitrary interconnection network and n/p local memory per processor, where n/p ? p 2+? (for some arbitrarily small ? > 0). For any given set of n points in 3-space, the algorithm computes the three-dimensional convex hull, with high probability, in $O((n\log{n})/p)$ local computation time and O(1) communication phases with at most O(n/p) data sent/received by each processor. That is, with high probability, the algorithm computes the three-dimensional convex hull of an arbitrary point set in time $O((n\log n)/{p} + \Gamma_{n,p})$ , where Γ n,p denotes the time complexity of one communication phase. The assumption n/p ? p 2+? implies a coarse-grained, limited parallelism, model which is applicable to most commercially available multiprocessors. In the terminology of the BSP model, our algorithm requires, with high probability, O(1) supersteps, synchronization period $L = \Theta((n\log n)/{p})$ , computation cost $O((n\log n)/{p})$ , and communication cost O((n/p) g).

In this paper we study the problem of computing an exact, or arbitrarily close to exact, solution of an unrestricted point set stereo matching problem. Within the context of classical approaches like the Marr-Poggio algorithm, this means that we study how to solve the unrestricted basic subproblems created within such approaches, possibly yielding an improved overall performance of such methods. We present an O(n2 + 4k) time and O(n4) space algorithm for exact unrestricted stereo matching, where n represents the number of points in each set and k the number of depth levels considered. We generalize the notion of a δ-approximate solution for point set congruence to the stereo matching problem and present an O (( e δ ) k n 2 + 2k ) time and O (( e δ )n 2 ) space δ-approximate algorithm for unrestricted stereo matching (e represents measurement inaccuracies in the image). We introduce new computational geometry tools for stereo matching: the translation square arrangement, approximate translation square arrangement and approximate stereo matching tree.

We show that the wavefront approach to Voronoi diagrams (a deterministic line-sweep algorithm that does not use geometric transform) can be generalized to distance measures more general than the Euclidean metric. In fact, we provide the first worst-case optimal (O (n logn) time,O(n) space) algorithm that is valid for the full class of what has been callednice metrics in the plane. This also solves the previously open problem of providing anO (nlogn)-time plane-sweep algorithm for arbitraryL k -metrics. Nice metrics include all convex distance functions but also distance measures like the Moscow metric, and composed metrics. The algorithm is conceptually simple, but it copes with all possible deformations of the diagram.

In contrast to queries for on-line transaction processing (OLTP) systems that typically access only a small portion of a database, OLAP queries may need to aggregate large portions of a database which often leads to performance issues. In this paper we introduce CR-OLAP, a Cloud based Real-time OLAP system based on a new distributed index structure for OLAP, the distributed PDCR tree, that utilizes a cloud infrastructure consisting of (m + 1) multi-core processors. With increasing database size, CR-OLAP dynamically increases m to maintain performance. Our distributed PDCR tree data structure supports multiple dimension hierarchies and efficient query processing on the elaborate dimension hierarchies which are so central to OLAP systems. It is particularly efficient for complex OLAP queries that need to aggregate large portions of the data warehouse, such as “report the total sales in all stores located in California and New York during the months February-May of all years”. We evaluated CR-OLAP on the Amazon EC2 cloud, using the TPC-DS benchmark data set. The tests demonstrate that CR-OLAP scales well with increasing number of processors, even for complex queries. For example, on an Amazon EC2 cloud instance with eight processors, for a TPC-DS OLAP query stream on a data warehouse with 80 million tuples where every OLAP query aggregates more than 50% of the database, CR-OLAP achieved a query latency of 0.3 seconds which can be considered a real time response.

We study scalable parallel computational geometry algorithms for the coarse grained multicomputer model: p processors solving a problem on n data items, were each processor has O(n/p)≫O(1) local memory and all processors are connected via some arbitrary interconnection network (e.g. mesh, hypercube, fat tree). We present O(Tsequential/p+Ts(n, p)) time scalable parallel algorithms for several computational geometry problems. Ts(n, p) refers to the time of a global sort operation. Our results are independent of the multicomputer’s interconnection network. Their time complexities become optimal when Tsequential/p dominates Ts(n, p) or when Ts(n, p) is optimal. This is the case for several standard architectures, including meshes and hypercubes, and a wide range of ratios n/p that include many of the currently available machine configurations. Our methods also have some important practical advantages: For interprocessor communication, they use only a small fixed number of one global routing operation, global sort, and all other programming is in the sequential domain. Furthermore, our algorithms use only a small number of very large messages, which greatly reduces the overhead for the communication protocol between processors. (Note however, that our time complexities account for the lengths of messages.) Experiments show that our methods are easy to implement and give good timing results.

Geometric hashing methods provide an efficient approach to indexing from image features into a database of models. The hash functions that have typically been used involve quantization of the values, which can result in nongraceful degradation of the performance of the system in the presence of noise. Intuitively, it is desirable to replace the quantization of hash values and the resulting binning of hash entries by a method that gives increasingly less weight to a hash table entry as a hashed feature becomes more distant from the hash entry position. In this paper, we show how these intuitive notions can be translated into a well-founded Bayesian approach to object recognition and give precise formulas for the optimal weight functions that should be used in hash space. These extensions allow the geometric hashing method to be viewed as a Bayesian maximum-likelihood framework. We demonstrate the validity of the approach by performing similarity-invariant object recognition using models obtained from drawings of military aircraft and automobiles and test images from real-world grayscale images of the same aircraft and automobile types. Our experimental results represent a complete object recognition system, since the feature extraction process is automated. Our system is scalable and works rapidly and very efficiently on an 8K-processor CM - 2, and the quality of results using similarity-invariant model matching is excellent.

This paper presents a new approach to Parallel Computational Geometry by using networks of analog components (referred to as analog networks or analog circuits). Massively parallel analog circuits with large numbers of processing elements exist in hardware and have proven to be efficient architectures for important problems (e.g. constructing an associative memory). In this paper it is demonstrated how Parallel Computational Geometry problems can be solved by exploiting the features of such analog parallel architectures. Using massively parallel analog circuits requires a radically different approach to geometric problem solving because (1) time is continuous instead of the standard discretized stepwise parallel processing, and (2) geometric data is represented by analog components (e.g. voltages at certain positions of the circuit) instead of the usual digital representation We present analog parallel algorithms for the following geometrical problems: minimum weight triangularization of planar point sets...

Proteins within the cell act as part of complex networks, which allow pathways and processes to function. Therefore, understanding how proteins interact is a significant area of current research.This review aims to present an overview of key experimental techniques (yeast two-hybrid, tandem affinity purification and protein microarrays) used to discover protein-protein interactions (PPIs), as well as to briefly discuss certain computational methods for predicting protein interactions based on gene localization, phylogenetic information, 3D structural modeling or primary protein sequence data. Due to the large-scale applicability of primary sequence-based methods, the authors have chosen to focus on this strategy for our review. There is an emphasis on a recent algorithm called Protein Interaction Prediction Engine (PIPE) that can predict global PPIs. The readers will discover recent advances both in the practical determination of protein interaction and the strategies that are available to attempt to anticipate interactions without the time and costs of experimental work.Global PPI maps can help understand the biology of complex diseases and facilitate the identification of novel drug target sites. This study describes different techniques used for PPI prediction that we believe will significantly impact the development of the field in a new future. We expect to see a growing number of similar techniques capable of large-scale PPI predictions.

A goal of the post-genomics era has been to elucidate a detailed global map of protein-protein interactions (PPIs) within a cell. Here, we show that the presence of co-occurring short polypeptide sequences between interacting protein partners appears to be conserved across different organisms. We present an algorithm to automatically generate PPI prediction method parameters for various organisms and illustrate that global PPIs can be predicted from previously reported PPIs within the same or a different organism using protein primary sequences. The PPI prediction code is further accelerated through the use of parallel multi-core programming, which improves its usability for large scale or proteome-wide PPI prediction. We predict and analyze hundreds of novel human PPIs, experimentally confirm protein functions and importantly predict the first genome-wide PPI maps for S. pombe (∼9,000 PPIs) and C. elegans (∼37,500 PPIs).

We present a parallel algorithm for the construction of the hyperoctree representing a d-dimensional object from a set of n (d ? 1)-dimensional hyperoctrees, representing adjacent cross sections of this object. On a p-processor SIMD hypercube the time complexity of our algorithm is O((m/p) log p log n), where m is the maximum of input and output size.

The multisearch problem is defined as follows. Given a data structure D modeled as a graph with n constant-degree nodes, perform O(n) searches on D. Let r be the length of the longest search path associated with a search process, and assume that the paths are determined "on-line." That is, the search paths may overlap arbitrarily. In this paper, we solve the multisearch problem for certain classes of graphs in O([formula] + r ([formula]/log n)) time on a [formula] × [formula]n mesh-connected computer. For many data structures, the search path traversed when answering one search query has length r = O(log n). For these cases, our algorithm processes O(n) such queries in asymptotically optimal Θ([formula]) time. The classes of graphs we consider contain many of the important data structures that arise in practice, ranging from simple trees to Kirkpatrick hierarchical search DAGs. Multisearch is a useful abstraction that can be used to implement parallel versions of standard sequential data structures on a mesh. As example applications, we consider a variety of parallel on-line tree traversals, as well as hierarchical representations of polyhedra and its myriad of applications (line-polyhedron intersection queries, multiple tangent plane determination, intersecting convex polyhedra, and three-dimensional convex hull).

Interactions among proteins are essential to many biological functions in living cells but experimentally detected interactions represent only a small fraction of the real interaction network. Computational protein interaction prediction methods have become important to augment the experimental methods; in particular sequence based prediction methods that do not require additional data such as homologous sequences or 3D structure information which are often not available. Our Protein Interaction Prediction Engine (PIPE) method falls into this category. Park has recently compared PIPE with the other competing methods and concluded that our method "significantly outperforms the others in terms of recall-precision across both the yeast and human data". Here, we present MP-PIPE, a new massively parallel PIPE implementation for large scale, high throughput protein interaction prediction. MP-PIPE enabled us to perform the first ever complete scan of the entire human protein interaction network; a massively parallel computational experiment which took three months of full time 24/7 computation on a dedicated SUN UltraSparc T2+ based cluster with 50 nodes, 800 processor cores and 6,400 hardware supported threads. The implications for the understanding of human cell function will be significant as biologists are starting to analyze the 130,470 new protein interactions and possible new pathways in Human cells predicted by MP-PIPE.

Structural variations (SVs) in a genome are now known as a prominent and important type of genetic variation. Among all types of SVs, the identification of transposon insertion polymorphisms (TIPs) is more challenging due to the highly repetitive nature of transposon sequences. We developed a computational method, TIP‐finder, to identify TIPs through analysis of next generation personal genome data and their extremely large copy numbers. We tested the efficiency of TIP‐finder with simulated data and are able to detect about 88% of TIPs with precision of ≥91%. Using TIP‐finder to analyze the Solexa pair‐end sequence data at deep coverage for six genomes representing two trio families, we identified a total of 5569 TIPs, consisting of 4881, 456, 91, and 141 insertions from Alu, L1, SVA and HERV, respectively, representing the most comprehensive analysis of such type of genetic variation.

This chapter addresses the query performance issue for Relational OLAP (ROLAP) data cubes. The authors present RCUBE, a distributed multi-dimensional ROLAP indexing scheme which is practical to implement, requires only a small communication volume, and is fully adapted to distributed disks. Their solution is efficient for spatial searches in high dimensions and scalable in terms of data sizes, dimensions, and number of processors. Their method is also incrementally maintainable. Using “surrogate” group-bys, it allows for the efficient processing of arbitrary OLAP queries on partial cubes, where not all of the group-bys have been materialized. Experiments with RCUBE show that the ROLAP advantage of better scalability, in comparison to MOLAP, can be maintained while providing, at the same time, a fast and flexible index for OLAP queries.

In this book chapter, the authors discuss some important communication issues to obtain a highly scalable computing system. They consider the CGM (Coarse-Grained Multicomputer) model, a realistic computing model to obtain scalable parallel algorithms. The communication cost is modeled by the number of communication rounds and the objective is to design algorithms that require the minimum number of communication rounds. They discuss some important issues and make considerations of practical importance, based on our previous experience in the design and implementation of parallel algorithms. The first issue is the amount of data transmitted in a communication round. For a practical implementation to be successful they should attempt to minimize this amount, even when it is already within the limit allowed by the CGM model. The second issue concerns the trade-off between the number of communication rounds which the CGM attempts to minimize and the overall communication time taken in the communication rounds. Sometimes a larger number of communication rounds may actually reduce the total amount of data transmitted in the communications rounds. These two issues have guided us to present efficient parallel algorithms for the string similarity problem, used as an illustration.

We study the problem of finding shortest paths in time-dependent networks with edge load forecasts where the behavior of each edge is modeled as a time-dependent arrival function with FIFO property. Here, we present a new algorithm that computes for a given start node s and destination node d, the shortest paths and earliest arrival times for all possible starting times. Our algorithm runs in time O((Fd + λ)(|E| + |V| log |V|)) where Fd is the output size (number of linear pieces needed to represent the earliest arrival time function) and λ is the input size (number of linear pieces needed to represent the local earliest arrival time functions for all edges in the network). Our method improves significantly on the best previously known algorithm which requires time O(Fmax |V||E|) where Fmax ≥ Fd is the maximum number of linear pieces needed to represent the earliest arrival time function between the start node s to any node in the network. It has been conjectured that there are cases where Fmax is of super-polynomial size; however, even in such cases, Fd might still be of linear size. In such cases, our algorithm would take polynomial time to find the solution, while other methods require super-polynomial time. Both of the above methods are not useful in practice for graphs where Fd is of super-polynomial size. For such graphs, we present the first approximation method to compute for all possible starting times at s, the earliest arrival times at d within error at most e. Our algorithm runs in time O(Δ/e(|E| + |V|log|V|)) where Δ is the difference between the earliest arrival times at d for the latest and earliest starting times at s.

Systems biology has matured considerably as a discipline over the last decade, yet some of the key challenges separating current research efforts in systems biology and clinically useful results are only now becoming apparent. As these gaps are better defined, the new discipline of systems medicine is emerging as a translational extension of systems biology. How is systems medicine defined? What are relevant ontologies for systems medicine? What are the key theoretic and methodologic challenges facing computational disease modeling? How are inaccurate and incomplete data, and uncertain biologic knowledge best synthesized in useful computational models? Does network analysis provide clinically useful insight? We discuss the outstanding difficulties in translating a rapidly growing body of data into knowledge usable at the bedside. Although core-specific challenges are best met by specialized groups, it appears fundamental that such efforts should be guided by a roadmap for systems medicine drafted by a coalition of scientists from the clinical, experimental, computational, and theoretic domains.

In this paper we study the potential performance improvements for catastrophe modelling systems that can be achieved through parallelization on a Cell Processor. We studied and parallelized a critical section of catastrophe modelling, the so called "inner loop", and implemented it on a Cell Processor running on a regular Playstation 3 platform. The Cell Processor is known to be a challenging environment for software development. In particular, the small internal storage available at each SPE of the Cell Processor is a considerable challenge for catastrophe modelling because the catastrophe modelling algorithm requires frequent accesses to large lookup tables. Our parallel solution is a combination of multiple techniques: streaming data to the SPEs and parallelizing inner loop computations, building caches on the SPEs to store parts of the large catastrophe modelling lookup tables, vectorizing the computation on the SPEs, and double-buffering the file I/O. On a (Playstation 3) Cell Processor with six active SPEs and 4-way vectorization on each SPE (implying a maximum theoretical 24x speedup), we were able to measure a sustained 16x speedup for our parallel catastrophe modelling code over a wide range of data sizes for real life Japanese earthquake data.

In this paper, we present optimal parallel algorithms for optical clustering on a mesh-connected computer.Optical clustering is a clustering technique based on the principal of optical resolution, and is of particular interest in picture analysis. The algorithms we present are based on the application of parallel algorithms in computational geometry and graph theory. In particular, we show that given a setS ofN points in the Euclidean plane, the following problems can be solved in optimal\(O\left( {\sqrt N } \right)\) time on a mesh-connected computer of sizeN. 1. Determine the optical clusters ofS with respect to a given separation parameter. 2. Given an interval [a, b] representing the number of optical clusters desired in the clustering ofS, determine the range of the separation parameter that will result in such an optical clustering.