The growth in compute speed has outpaced the growth in network bandwidth over the last decades. This has led to an increasing performance gap between local and distributed processing. A parallel database cluster thus has to maximize the locality of query processing. A common technique to this end is to co-partition relations to avoid expensive data shuffling across the network. However, this is limited to one attribute per relation and is expensive to maintain in the face of updates. Other attributes often exhibit a fuzzy co-location due to correlations with the distribution key but current approaches do not leverage this. In this paper, we introduce locality-sensitive data shuffling, which can dramatically reduce the amount of network communication for distributed operators such as join and aggregation. We present four novel techniques: (i) optimal partition assignment exploits locality to reduce the network phase duration; (ii) communication scheduling avoids bandwidth underutilization due to cross traffic; (iii) adaptive radix partitioning retains locality during data repartitioning and handles value skew gracefully; and (iv) selective broadcast reduces network communication in the presence of extreme value skew or large numbers of duplicates. We present comprehensive experimental results, which show that our techniques can improve performance by up to factor of 5 for fuzzy co-location and a factor of 3 for inputs with value skew.

Shipments of smartphones and tablets with wimpy CPUs are outpacing brawny PC and server shipments by an ever-increasing margin. While high performance database systems have traditionally been optimized for brawny systems, wimpy systems have received only little attention; leading to poor performance and energy inefficiency on such systems.

eScience and big data analytics applications are facing the challenge of efficiently evaluating complex queries over vast amounts of structured text data archived in network storage solutions. To analyze such data in traditional disk-based database systems, it needs to be bulk loaded, an operation whose performance largely depends on the wire speed of the data source and the speed of the data sink, i.e., the disk. As the speed of network adapters and disks has stagnated in the past, loading has become a major bottleneck. The delays it is causing are now ubiquitous as text formats are a preferred storage format for reasons of portability. But the game has changed: Ever increasing main memory capacities have fostered the development of in-memory database systems and very fast network infrastructures are on the verge of becoming economical. While hardware limitations for fast loading have disappeared, current approaches for main memory databases fail to saturate the now available wire speeds of tens of Gbit/s. With Instant Loading, we contribute a novel CSV loading approach that allows scalable bulk loading at wire speed. This is achieved by optimizing all phases of loading for modern super-scalar multi-core CPUs. Large main memory capacities and Instant Loading thereby facilitate a very efficient data staging processing model consisting of instantaneous load-work-unload cycles across data archives on a single node. Once data is loaded, updates and queries are efficiently processed with the flexibility, security, and high performance of relational main memory databases.

MapReduce has emerged as a popular tool for distributed and scalable processing of massive data sets and is being used increasingly in e-science applications. Unfortunately, the performance of MapReduce systems strongly depends on an even data distribution while scientific data sets are often highly skewed. The resulting load imbalance, which raises the processing time, is even amplified by high runtime complexity of the reducer tasks. An adaptive load balancing strategy is required for appropriate skew handling. In this paper, we address the problem of estimating the cost of the tasks that are distributed to the reducers based on a given cost model. An accurate cost estimation is the basis for adaptive load balancing algorithms and requires to gather statistics from the mappers. This is challenging: (a) Since the statistics from all mappers must be integrated, the mapper statistics must be small. (b) Although each mapper sees only a small fraction of the data, the integrated statistics must capture the global data distribution. (c) The mappers terminate after sending the statistics to the controller, and no second round is possible. Our solution to these challenges consists of two components. First, a monitoring component executed on every mapper captures the local data distribution and identifies its most relevant subset for cost estimation. Second, an integration component aggregates these subsets approximating the global data distribution.

Peer-to-Peer (P2P) technology can be utilized to combine remote resources and build distributed, high performance database systems, called data grids, which help to handle the rapidly increasing volumes of data produced by disciplines like astrophysics, biology, or geology. One major challenge of data grids are skewed query patterns which cause load imbalances and heavily diminish performance and availability. To avoid hot spots, sophisticated load balancing techniques are required. We present a dynamic replication strategy which prevents hot spots by dynamically replicating the hot data on different locations. The main questions of such a strategy are when to copy which data to what receivers and when to delete the copies. To answer these questions we propose a low-overhead, decentralized method which is able to deliver a highly accurate estimate of the global load and the single peer loads to all clients. We use that information in an optimization problem to determine the data to be replicated and the optimal replica receivers. A simulated performance evaluation based on a real-world scenario demonstrates the effectiveness of the approach.

Collaborative research in various scientific disciplines requires sup-port for scalable data management enabling the efficient correlation of globally distributed data sources. Motivated by the expected data rates of upcoming projects and a growing number of users, com-munities explore new data management techniques for achieving high throughput. Community-driven data grids deliver such high-throughput data distribution for scientific federations by partition-ing data according to application-specific data and query character-istics. Query hot spots are an important and challenging problem in this environment. Existing approaches to load-balancing from Peer-to-Peer (P2P) data management and sensor networks do not directly meet the requirements of a data-intensive e-science envi-ronment. In this paper, our contributions are partitioning schemes based on multi-dimensional index structures enabling communities to trade off data load balancing and handling query hot spots via splitting and replication. We evaluate the partitioning schemes with two typical kinds of data sets from the astrophysics domain and workloads extracted from Sloan Digital Sky Survey (SDSS) query traces and perform throughput measurements in real and simulated networks. The experiments demonstrate the improved workload distribution capabilities and give promising directions for the de-velopment of future community grids. 1.

E-science communities face huge data management challenges due to large existing data sets and expected data rates from forthcoming projects. Community-driven data grids provide a scalable, high-throughput oriented data management solution for scientific federations by employing domain-specific partitioning schemes and parallelism. In this paper, we present how community-driven data grids can adapt their query coordination strategies in the face of different typical submission scenarios. We explore the impact of submitting queries uniformly or having submission hot spots. By an extensive evaluation of five strategies on simulated and distributed setups, we show that some coordination strategies are preferable to others, regardless of submission skew. Based on our results, we can improve the usability and scalability of community-driven data grids for data-intensive applications.

In federated Data Grids, individual institutions share their data sets within a community to enable collaborative data analysis. Data access needs to be provided in a scalable fashion since in most e-science communities, data sets do not only grow exponentially but also experience an increasing popularity. If data autonomy is retained, each individual institution has to ensure efficient access to its data. Analyzing application-specific data properties (such as data skew) or query characteristics (query patterns) and distributing data within Data Grids accordingly, allows for improved throughput for data-intensive applications and enables better load-balancing between shared resources. We propose a framework for investigating application-specific index structures for creating suitable partitioning schemes. We evaluate two variants of the well-known Quadtree data structure as well as the Zones approach, an index structure from the astrophysics domain, according to several criteria. Our framework improves data access within federated Data Grids and can be combined with well-established Grid methods as well as with more flexible P2P technologies.

The field of e-science currently faces many challenges. Among the most important ones are the analysis of huge volumes of scientific data and the connection of various sciences and communities, thus enabling scientists to share scientific interests, data, and research results. These issues can be addressed by processing large data volumes on-thefly in the form of data streams and by combining multiple data sources and making the results available in a network. In this paper, we demonstrate how e-science can benefit from research in computer science in the field of data stream management. In particular, we are concerned with processing multiple data streams in grid-based peer-to-peer (P2P) networks. We introduce spatial matching, which is a current issue in astrophysics, as a real-life e-science scenario to show how a data stream management system (DSMS) can help in efficiently performing associated tasks. We describe our new way of solving the spatial matching problem and present some evaluation results. In the course of the evaluation, our DSMS StarGlobe proves to be a valuable computing platform for astrophysical applications.

Modern document management systems administer an increasing amount of data. Unfortunately traditional database technology cannot satisfy the resulting performance requirements. We report on how parallel database technology can contribute to make large and scalable document management systems work. Our discussion clearly shows that simply substituting a sequential database system for a parallel one does not necessarily lead to scalability and high performance. In contrast, detailed knowledge of the application and document management system is necessary to decide on the optimal architecture of the parallel database system, its query optimization and parallelization strategies, as well as on its data fragmentation scheme and load balancing properties. All discussions are exemplified referring to an existing document management system developed at our university that is currently migrated from a sequential database system to a parallel one.

This paper presents an on-line algorithm for the construction of position trees, i.e., an algorithm which constructs the position tree for a given string while reading the string from left to right. In addition, an on-line correction algorithm is presented which—upon a change in the string—can be used to construct the new position tree. Moreover, special attention is paid to computers with small memory. compactification of the trees and transport costs between main and secondary storage are discussed.

In this paper a new method to increase parallelism in database systems is described. Use is made of the fact that for recovery reasons, we often have two values for one object in the database—the new one and the old one. Introduced and discussed in detail is a certain scheme by which readers and writers may work simultaneously on the same object. It is proved that transactions executed according to this scheme have the correct effect; i.e., consistency is preserved. Several variations of the basic scheme which are suitable depending on the degree of parallelism required, are described.