This paper presents VelocityOLAP (VOLAP), a distributed real-time OLAP system for high-velocity data. VOLAP makes use of dimension hierarchies, is highly scalable, exploits both multi-core and multi-processor parallelism, and can guarantee serializable execution of insert and query operations. 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 600 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.

research-article Share on Quantifying Eventual Consistency For Aggregate Queries Authors: Neil Burke Dalhousie University Dalhousie UniversityView Profile , Frank Dehne School of Computer Science, Carleton University School of Computer Science, Carleton UniversityView Profile , Andrew Rau-Chaplin Dalhousie University Dalhousie UniversityView Profile , David Robillard School of Computer Science, Carleton University School of Computer Science, Carleton UniversityView Profile Authors Info & Claims IDEAS '17: Proceedings of the 21st International Database Engineering & Applications SymposiumJuly 2017 Pages 274–282https://doi.org/10.1145/3105831.3105836Published:12 July 2017Publication History 0citation43DownloadsMetricsTotal Citations0Total Downloads43Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

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.

Fast aggregation of data with many dimensions is a key component of many applications. The R-tree is the traditional data structure for indexing multi-dimensional data, but even the best R-tree variants suffer from performance degradation as the number of dimensions increases. The DC-tree addressed this issue by replacing Minimum Bounding Rectangle (MBR) keys with Minimum Describing Subsets (MDSs), which are less susceptible to overlap. This technique dramatically improves query performance with many dimensions, but at the cost of reduced insertion performance. Like most R-tree variants, this insertion overhead comes from expensive geometric comparisons while selecting the best child for insertion, or splitting over-full nodes. DC-trees, including the parallel PDC-tree, suffer even more from this overhead since MDSs are typically much more expensive to compare and manipulate than MBRs. This paper introduces the Hilbert PDC-tree, a parallel index structure for many-dimensional data that supports high-velocity data ingestion. This is achieved by avoiding geometric comparisons during insertion by instead inserting records based on the Hilbert index of their keys. This approach is similar to that of the Hilbert R-tree, but with special considerations for efficiently supporting many hierarchical dimensions. Additionally, a new node splitting algorithm significantly reduces overlap and improves query performance. Experiments show that the Hilbert PDC-tree scales well to a high number of dimensions, while supporting a much higher rate of ingestion and better query performance than the PDC-tree.

Summary In the reinsurance market, the risks natural catastrophes pose to portfolios of properties must be quantified, so that they can be priced, and insurance offered. The analysis of such risks at a portfolio level requires a simulation of up to 800 000 trials with an average of 1000 catastrophic events per trial. This is sufficient to capture risk for a global multi‐peril reinsurance portfolio covering a range of perils including earthquake, hurricane, tornado, hail, severe thunderstorm, wind storm, storm surge and riverine flooding, and wildfire. Such simulations are both computation and data intensive, making the application of high‐performance computing techniques desirable. In this paper, we explore the design and implementation of portfolio risk analysis on both multi‐core and many‐core computing platforms. Given a portfolio of property catastrophe insurance treaties, key risk measures, such as probable maximum loss, are computed by taking both primary and secondary uncertainties into account. Primary uncertainty is associated with whether or not an event occurs in a simulated year, while secondary uncertainty captures the uncertainty in the level of loss due to the use of simplified physical models and limitations in the available data. A combination of fast lookup structures, multi‐threading and careful hand tuning of numerical operations is required to achieve good performance. Experimental results are reported for multi‐core processors and systems using NVIDIA graphics processing unit and Intel Phi many‐core accelerators. Copyright © 2015 John Wiley & Sons, Ltd.

Summary This paper addresses how the benefits of cloud‐based infrastructure can be harnessed for analytical workloads. Often, the software handling analytical workloads is not developed by a professional programmer but on an ad hoc basis by analysts in high‐level programming environments such as R or MATLAB. The goal of this research is to allow Analysts to take an analytical job that executes on their personal workstations and with minimum effort execute it on cloud infrastructure and manage both the resources and the data required by the job. If this can be facilitated gracefully, then the Analyst benefits from on‐demand resources, low maintenance cost and scalability of computing resources, all of which are offered by the cloud. In this paper, a Platform for Parallel R‐based Analytics on the Cloud (P2RAC) that is placed between an Analyst and a cloud infrastructure is proposed and implemented. P2RAC offers a set of command‐line tools for managing the resources, such as instances and clusters, the data and the execution of the software on the Amazon Elastic Computing Cloud infrastructure. Experimental studies are pursued using two parallel problems and the results obtained confirm the feasibility of employing P2RAC for solving large‐scale analytical problems on the cloud.Copyright © 2013 John Wiley & Sons, Ltd.

Measuring document relatedness using unsupervised co-occurrence based word relatedness methods is a processing-time and memory consuming task. This paper introduces the application of compact data structures for efficient computation of word relatedness based on corpus statistics. The data structure is used to efficiently lookup: (1) the corpus statistics for the Common Word Relatedness Approach, (2) the pairwise word relatedness for the Algorithm Specific Word Relatedness Approach. These two approaches significantly accelerate the processing time of word relatedness methods and reduce the space cost of storing co-occurrence statistics in memory, making text mining tasks like classification and clustering based on word relatedness practical.

The purpose of this paper is to evaluate the performance of Vector Evaluated Differential Evolution (VEDE) and Vector Evaluated Particle Swarm Optimization (VEPSO) in solving a real world financial optimization problem. The algorithms have been applied to the Reinsurance Contract Problem, which is a challenging problem in computational finance, and their performance has been evaluated in terms of metrics including the average number of solutions, the average hypervolume and the coverage. Results have shown that both algorithms can reach good solutions, however VEPSO tends to perform better.

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.

Modern insurance and reinsurance companies use stochastic simulation techniques for portfolio risk analysis. Their risk portfolios may consist of thousands of reinsurance contracts covering millions of individually insured locations. To quantify risk and to help ensure capital adequacy, each portfolio must be evaluated in up to a million simulation trials, each capturing a different possible sequence of catastrophic events (e.g., earthquakes, hurricanes, etc.) over the course of a contractual year. We present a flexible framework for portfolio risk analysis that can answer a rich variety of catastrophic risk queries. Rather than aggregating simulation data in order to produce a small set of high-level risk metrics efficiently (as done in production risk management systems), our focus is on queries on unaggregated or partially aggregated data. The goal is to allow analysts to obtain answers to a wide variety of unanticipated but natural ad hoc queries, which can help actuaries or underwriters to better understand the multiple dimensions (e.g., spatial correlation, seasonality, peril features, construction features, financial terms, etc.) that can impact portfolio risk and thus company solvency. We implemented a prototype system, called QuPARA, using Apache's Hadoop implementation of the MapReduce paradigm. This allows the user to utilize large parallel compute servers in order to answer ad hoc queries efficiently even on very large data sets typically encountered in practice. We describe the design and implementation of QuPARA and present experimental results that demonstrate its feasibility.

Stochastic simulation techniques employed for the analysis of portfolios of insurance/reinsurance risk, often referred to as `Aggregate Risk Analysis', can benefit from exploiting state-of-the-art high-performance computing platforms. In this paper, parallel methods to speed-up aggregate risk analysis for supporting real-time pricing are explored. An algorithm for analysing aggregate risk is proposed and implemented for multi-core CPUs and for many-core GPUs. Experimental studies indicate that GPUs offer a feasible alternative solution over traditional high-performance computing systems. A simulation of 1,000,000 trials with 1,000 catastrophic events per trial on a typical exposure set and contract structure is performed in less than 5 seconds on a multiple GPU platform. The key result is that the multiple GPU implementation can be used in real-time pricing scenarios as it is approximately 77x times faster than the sequential counterpart implemented on a CPU.

The purpose of this paper is to present a PSO algorithm mixed with a new hybrid local search algorithm named LHS, enhancing the exploration and exploitation capabilities of the canonical PSO. The hybrid PSO, named PSOLHS, is examined against six known multimodal functions and compared with both canonical PSO and LHS. Furthermore, a comparison between evolutionary strategies (ES) and MPSO-LS is going to show how our approach outperforms these other techniques in almost all benchmark functions. All comparisons are based on a statistical t-test for supporting our results.

Space-filling curves, particularly Hilbert curves, have proven to be a powerful paradigm for maintaining spatial groupings of multi-dimensional data in a variety of application areas including database systems,data structures and distributed information systems. One significant limitation in the standard definition of Hilbert curves is the requirement that the grid size (i.e. the cardinality) in each dimension be the same. In the real world, not all dimensions are of equal size and the work-around of padding all dimensions to the size of the largest dimension wastes memory and disk space, while increasing the time spent manipulating and communicating these "inflated" values. In this paper we define a new compact Hilbert index which, maintains all the advantages of the standard Hilbert curve and permits dimension cardinalities of varying sizes. This index can be used in any application that would have previously relied on Hilbert curves but, in the case of unequal side lengths, provides a more memory efficient representation. This is particularly important in distributed applications (parallel, P2P and grid), in which not only is memory space saved but communication volume reduced

Over the past ten to fifteen years, data warehouse platformshave grown enormously, both in terms of their importance and their sheer size. Traditionally, such systems have been based upon a dimensional model known as the Star Schema that consists of a central fact table and a series of related dimension tables. Given the enormous size of the fact table, virtually all current systems augment the primary fact table with a small number of focused summary tables. Previous research has addressed the issue of the selection or identification of the most cost-effective summaries. However, the problem of efficiently computing a given view subset has received far less attention. In this paper, we present a suite of greedy algorithms for the construction of these view subsets. Experimental results demonstrate cost savings of between 20% and 70% relative to the naive alternatives, depending upon the degree of materialization required.

In this paper we propose a new query processing method for the OLAP enabled grid, which blends sophisticated cache extraction techniques and data grid scheduling to efficiently satisfy OLAP queries in a distributed fashion. The heart of our approach is our query fragment aggregation and recombination (FAR) strategy that partitions OLAP queries into subqueries which can be effectively answered by retrieving and aggregating multiple fragments of cached data from nearby grid sources, or as a last resort, more remote backend data warehouses. We have implemented and experimentally evaluated our query processing method and found that our strategy reduces query time between 50% and 60% for practical user cache sizes and network parameters.

We present the cgmOLAP server, the first fully functional parallel OLAP system able to build data cubes at a rate of more than 1 Terabyte per hour. cgmOLAP incorporates a variety of novel approaches for the parallel computation of full cubes, partial cubes, and iceberg cubes as well as new parallel cube indexing schemes. The cgmOLAP system consists of an application interface, a parallel query engine, a parallel cube materialization engine, meta data and cost model repositories, and shared server components that provide uniform management of I/O, memory, communications, and disk resources.

Online Analytical Processing is a powerful framework for the analysis of organizational data. OLAP is often supported by a logical structure known as a data cube, a multidimensional data model that offers an intuitive array-based perspective of the underlying data. Supporting efficient indexing facilities for multi-dimensional cube queries is an issue of some complexity. In practice, the difficulty of the indexing problem is exacerbated by the existence of attribute hierarchies that sub-divide attributes into aggregation layers of varying granularity. In this paper, we present a hierarchy and caching framework that supports the efficient and transparent manipulation of attribute hierarchies within a parallel ROLAP environment. Experimental results verify that, when compared to the non-hierarchical case, very little overhead is required to handle streams of arbitrary hierarchical 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 very efficient for all of the following scenarios: (1) Sequential iceberg-cube queries. (2) External memory iceberg-cube queries. (3) Parallel iceberg-cube queries on shared-nothing PC clusters with multiple disks.

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, e.g., in 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 PC cluster. This is the first experimental examination of parallel FPT techniques. We have tested our parallel k-VERTEX COVER method on protein sequences obtained from the National Center for Biotechnology Information. 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 /spl ges/ 400 in less than 1.5 hours. Since our parallel FPT algorithm requires only very little communication between processors, we expect our method to also perform well on Grids.

This paper addresses the query performance issue for Relational OLAP (ROLAP) datacubes. We present 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. 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 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.

Abstract This paper describes efficient coarse‐grained parallel algorithms and implementations for a suite of interval graph problems. Included are algorithms requiring only a constant number of communication rounds for connected components, maximum weighted clique, and breadth‐first‐search and depth‐first‐search trees, as well as $O(log p)$ communication rounds algorithms for optimization problems such as minimum interval covering, maximum independent set and minimum dominating set, where $p$ is the number of processors in the parallel system. This implies that the number of communication rounds is independent of the problem size. Implementations of these algorithms are evaluated on parallel clusters, using both Fast Ethernet and Myrinet interconnection networks, and on a CRAY T3E parallel multicomputer, with extensive experimental results being presented and analyzed. Copyright © 2002 John Wiley & Sons, Ltd.

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 .

Describes the parallel, cluster-based implementation of an algorithm for the computation of a database operator known as the datacube. Though a number of efficient sequential algorithms have recently been proposed for this problem, very little research effort has been expended upon cost-effective parallelization techniques. Our approach builds directly upon the existing sequential proposals and is designed to be both load-balanced and communication-efficient. We also provide experimental results that demonstrate the viability of our technique under a variety of test conditions. Ultimately, we show that parallel performance relative to the underlying sequential algorithm (speedup) is near-optimal.

Whereas most of the literature assumes that the number of processors p is a function of the problem size n, in scalable algorithms p becomes a parameter of the time complexity. This is a more realistic modelisation of real parallel machines and yields optimal algorithms, for the case that n H p, where H is a function depending on the architecture of the interconnexion network. In this paper we present scalable algorithms for a number of geometric problems, namely lower envelope of line segments, 2D-nearest neighbour, 3D-maxima, 2D-weighted dominance counting area of the union of rectangles, 2D-convex hull. The main idea of these algorithms is to decompose the problem in p subproblems of size 0(F(n;p) + f(p)), with f(p) 2 F(n;p) , which can be solved independently using optimal sequential algorithms. For each problem we present a spatial decomposition scheme based on some geometric observations. The decomposition schemes have in common that they can be computed by globally sorting the entire data set at most twice. The data redundancy of f(p) duplicates of data elements per processor does not increase the asymptotic time complexity and ranges for the algorithms presented in this paper, from p to p2. The algorithms do not depend on a specific architecture,they are easy to implement and in practice efficient as experiments show.