Search

The big data software stack based on Apache Spark and Hadoop has become mission critical in many enterprises. Performance of Spark and Hadoop jobs depends on a large number of configuration settings. The manual tuning procedure is expensive and brittle. There have been efforts to develop online and off-line automatic tuning approaches to make the big data stack more autonomic, but many researchers noted that it is important to tune only when truly necessary because many parameter searches can reduce rather than enhance performance. Autonomic systems need to be able to accurately detect important changes in workload characteristics, predict future workload characteristics, and use this information to pro-actively optimise resource allocation and frequency of parameter searches. This paper presents the first study focusing on workload change detection, change classification and workload forecasting in big data workloads. We demonstrate 99% accuracy for workload change detection, 90% accuracy for workload and workload transition classification, and up to 96% accuracy for future workload type prediction on Spark and Hadoop job flows simulated using popular big data benchmarks. Our method does not rely on past workload history for workload type prediction.

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 scalable Cloud based Real-time OLAP system based on a new distributed index structure for OLAP, the distributed PDCR tree. CR-OLAP utilizes a scalable cloud infrastructure consisting of multiple commodity servers (processors). That is, with increasing database size, CR-OLAP dynamically increases the number of processors 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, for an Amazon EC2 cloud instance with 16 processors, a data warehouse with 160 million tuples, and a TPC-DS OLAP query stream where each query aggregates between 60% and 95% of the database, CR-OLAP achieved a query latency of below 0.3 s which can be considered a real time response. Collaboration with the IBM on alleviating performance bottlenecks for OLAP queries.OLAP queries may aggregate large portions of the database, creating bottlenecks.We study the use of parallel computing on scalable clouds to accelerate queries.Our system, CR-OLAP, is based on a new scalable distributed index structure.CR-OLAP uses dynamic cloud elasticity to improve performance.

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.

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 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).

Protein-protein interactions (PPIs) play a critical role in many cellular functions. A number of experimental techniques have been applied to discover PPIs; however, these techniques are expensive in terms of time, money, and expertise. There are also large discrepancies between the PPI data collected by the same or different techniques in the same organism. We therefore turn to computational techniques for the prediction of PPIs. Computational techniques have been applied to the collection, indexing, validation, analysis, and extrapolation of PPI data. This chapter will focus on computational prediction of PPI, reviewing a number of techniques including PIPE, developed in our own laboratory. For comparison, the conventional large-scale approaches to predict PPIs are also briefly discussed. The chapter concludes with a discussion of the limitations of both experimental and computational methods of determining PPIs.

Protein-protein interactions (PPIs) play a critical role in many cellular functions. A number of experimental techniques have been applied to discover PPIs; however, these techniques are expensive in terms of time, money, and expertise. There are also large discrepancies between the PPI data collected by the same or different techniques in the same organism. We therefore turn to computational techniques for the prediction of PPIs. Computational techniques have been applied to the collection, indexing, validation, analysis, and extrapolation of PPI data. This chapter will focus on computational prediction of PPI, reviewing a number of techniques including PIPE, developed in our own laboratory. For comparison, the conventional large-scale approaches to predict PPIs are also briefly discussed. The chapter concludes with a discussion of the limitations of both experimental and computational methods of determining PPIs.

The main problem for the design of dictionary machines on coarse grained hypercube multiprocessors, in comparison to the widely studied dictionary problem for fine grained hypercube multiprocessors, is that due to unequal distribution of the inserted and deleted records, the sizes of the sets stored at the individual processors may vary considerably. This problem, which is usually referred to as the load balancing problem , may lead to considerable degradation of the dictionary machine's performance. In this note we show that the load balancing problem for coarse grained hypercube dictionary machines can be solved with provable bounds on the sizes of the data sets, and with only little computational overhead.

Given a rectangle R (with its edges parallel to the coordinate axes) containing a set S = { s 1 ,…, s n } of n points in the Euclidean plane, consider the problem of finding the largest area subrectangle r in R with sides parallel to the coordinate axes that contains no point of S . We present optimal parallel algorithms for solving this problem on one- and two-dimensional arrays of processors.

In this paper, we study parallel branch and bound on fine grained hypercube multiprocessors. Each processor in a fine grained system has only a very small amount of memory available. Therefore, current parallel branch and bound methods for coarse grained systems (⩽ 1000 nodes) cannot be applied, since all these methods assume that every processor stores the path from the node it is currently processing back to the node where the process was created (the back-up path). Furthermore, the much larger number of processors available in a fine grained system makes it imperative that global information (e.g. the current best solution) is continuously available at every processor; otherwise the amount of unnecessary search would become intolerable. We describe an efficient branch-and-bound algorithm for fine grained hypercube multiprocessors. Our method uses a global scheme where all processors collectively store all back-up paths such that each processor needs to store only a constant amount of information. At each iteration of the algorithm, all current nodes may decide whether they need to create new children, be pruned, or remain unchanged. We describe an algorithm that, based on these decisions, updates the current back-up paths and distributes global information in O(log m) steps, where m is the current number of nodes. This method also includes dynamic allocation of search processes to processors and provides optimal load balancing. Even if very drastic changes in the set of current nodes occur, our load balancing mechanism does not suffer any slow down.

In this paper we study the parallel implementation of a traditional frame based knowledge representation system for a general purpose massively parallel hypercube architecture (such as the Connection Machine CM-2). We show that, using a widely available parallel system (instead of a special purpose architecture), it is possible to provide multiple users with efficient shared access to a large scale knowledge-base. Parallel algorithms are presented for answering multiple inference, assert and retract queries on both single and multiple inheritance hierarchies. In addition to theoretical time complexity analysis, empirical results obtained from extensive testing of a prototype implementation are presented.

In this paper we consider a new form of connectivity in binary images, called k -width connectivity. Two pixels a and b of value “1” are in the same k -width component if and only if there exists a path of width k such that a is one of the k start pixels and b is one of the k end pixels of this path. We present characterizations of the k -width components and show how to determine the k -width components of an n × n image in O(n) and O (log 2 n ) time on a mesh of processors and hypercube, respectively, when the image is stored with one pixel per processor. Our methods use a reduction of the k -width-connectivity problem to the 1-width-connectivity problem. A distributed, space-efficient encoding of the k -width components of small size allows us to represent the solution using O (1) registers per processor. Our hypercube algorithm also implies an algorithm for the shuffle-exchange network.

In this paper we discuss what kind of information can be obtained from WordNet and what kind of information should be added to WordNet in order to make it better suitable for the support of the Color-X method. We will present an extension of WordNet (called WordNet++) which contains a number of special types of relationships that are not available in WordNet. Additionally, WordNet++ is instantiated with knowledge about some particular domain.

Image processin9 is one of the major fields of application for parallel processing. Some of the first multiprocessors were mainly built for processing images (e.g., the MPP for analyzing LANDSAT satellite data) because for such applications data volumes are often so large that the use of standard sequential machines becomes impracticable. In addition to standard image processing operations such as noise removal, edge detection, filtering, etc., researchers have recently also started to study other "high-level" geometric operations which are well known in computational 9eometry. This special issue of Algorithmica is devoted to parallel algorithms for computational-geometry problems on digitized pictures. The motivation for studying such operations is that in practice geometric data for computationalgeometry applications is often given in the form of an image; hence, parallel algorithms which can be applied directly to the image may be more efficient than applying "standard" parallel computational-geometry methods which require that the image is first converted into, e.g., a set of polygonal chains. For example, consider the standard path-plannin9 problem in robotics: given a set of simple polygons in the plane representing the obstacles and a polygon representing the robot, find the shortest path for the robot to move from point A to point B without colliding with any obstacle. In practice, the robot might be moving in a factory hall; instead of first creating a polygonal description of the obstacles and the robot, it may be more efficient to use as input an image obtained from a camera mounted to the ceiling of the factory. Using an image from a camera might also be more practical for dynamic environments where the locations and shapes of the obstacles are changing. Since the factory, and thus the image of the obstacles, could be very large and the robot's path has to be determined in real-time, a parallel method for solving the path-planning problem directly on the image is desirable. 2 When solving computational-geometry problems for images in parallel, researchers have several different types of parallel machines available. The papers selected for this special issue consider four very commonly used ones: the parallel

In this paper, we present an OLAP framework for moving object data. We introduce a new operator GROUP_TRAJECTORIES for group-by operations on moving object data and present two implementation alternatives for computing groups of moving objects for group-by aggregation: group by overlap and group by intersection. We also present an interactive OLAP environment for resolution drill-down/roll-up on sets of trajectories and parameter browsing. We evaluate the performance of our GROUP_TRAJECTORIES operator by using generated as well as real life moving object datasets.

Recently, a growing interest in problems dealing with the movability of objects has been observed. Motion problems are manifold due to the variety of areas in which they may occur; among these areas are e.g. robotics, computer graphics, etc. One motion problem class recently being investigated is the separability problem.

In this paper, the authors study the problem of implementing standard data structures on a hypercube multiprocessor. They present a technique for efficiently executing multiple independent search processes on a class of graphs called ordered h-level graphs. They show how this technique can be utilized to implement a segment tree on a hypercube, thereby obtaining O(log{sup 2}n) time algorithms for solving the next element search problem, the trapezoidal composition problem, and the triangulation problem.

In this paper, we present a systolic algorithm for computing the configuration space of an arrangement of arbitrary obstacles in the plane for a rectilinearly convex robot. The obstacles and the robot are assumed to be represented in digitized form by a √n × √n nibary image. The algorithm is designed for a Mesh-of-Processors architecture with n processors (using the canonical representation of an image on a processor array) and has an execution time of O(√n) which is asymptotically optimal.