Association rules encode common patterns and structures identified in datasets. They can be derived by association rule mining (ARM) algorithms. The association rules are human-readable and allow comprehensible predictions, unlike many other types of prediction algorithms. Classical ARM algorithms, like Apriori or FP-growth, cannot process interval or ratio scaled data (quantitative variables) which limits their applicability. We address this restriction in classical ARM algorithms, making it possible to process quantitative variables on the right side of a rule. Our approach is based on applying the Kullback–Leibler divergence (KLD) to identify a rule which holistically considers complete data distributions instead of using only summary statistics. We demonstrate the new approach by using, among others, the example of predicting the length of stay of intensive care patients. The length of stay describes the number of days a patient spends in the intensive care unit. In addition, we further demonstrate our approach by predicting the credit score of bank customers and the contract duration of customers of a fictional telco company based on two publically available datasets. This paper shows a new approach for predicting quantitative variables in ARM. We demonstrate the new approach using the FP-growth algorithm.

Remote sensing-based Earth Observation plays an important role in assessing environmental changes throughout our planet. As an image-heavy domain, the evaluation of the data strongly focuses on statistical and pixel-based spatial analysis methods. However, considering the complexity of our Earth system, there are some environmental structures and dependencies that are not possible to accurately describe with these traditional image analysis approaches. One example for such a limitation is the representation of (spatial) networks and their characteristics. In this study, we thus propose a computer vision approach that enables the representation of semantic information gained from images as graphs. As an example, we investigate digital terrain models of Arctic permafrost landscapes with its very characteristic polygonal patterned ground. These regular patterns, which are clearly visible in high-resolution image and elevation data, are formed by subsurface ice bodies that are very vulnerable to rising temperatures in a warming Arctic. Observing these networks’ topologies and metrics in space and time with graph analysis thus allows insights into the landscape’s complex geomorphology, hydrology, and ecology and therefore helps to quantify how they interact with climate change. We show that results extracted with this analytical and highly automated approach are in line with those gathered from other manual studies or from manual validation. Thus, with this approach, we introduce a method that, for the first time, enables upscaling of such terrain and network analysis to potentially pan-Arctic scales where collecting in-situ field data is strongly limited.

Set similarity join (SSJ) is a well studied problem with many algorithms proposed to speed up its performance. However, its scalability and performance are rarely discussed in modern multicore environments. Existing algorithms assume a single-threaded execution that leaves the abundant parallelism provided by modern machines unused, or use distributed setups that may not yield efficient runtimes and speedups that are proportional to the amount of hardware resources (e.g., CPU cores). In this paper, we focus on a widely-used family of SSJ algorithms that are based on the filter-and-verification paradigm, and study the potential of speeding them up in the context of multicore machines. We adapt state-of-the-art SSJ algorithms including PPJoin and AllPairs. Our experiments using 12 real-world datasets highlight important findings: (1) Using the exact number of hardware-provided hyperthreads leads to optimal runtimes for most experiments, (2) hand-crafted data structures do not always lead to better performance, and (3) PPJoin’s position filter is more effective in the multithreaded case compared to the single-threaded execution.

Hybrid Hash Join (HHJ) has proven to be one of the most efficient and widely-used join algorithms. While HHJ's performance depends largely on accurate statistics and information about the input relations, it may not always be practical or possible for a system to have such information available. HHJ's design depends on many details to perform well. This paper is an experimental and analytical study of the trade-offs in designing a robust and dynamic HHJ operator. We revisit the design and optimization techniques suggested by previous studies through extensive experiments, comparing them with other algorithms designed by us or used in related studies. We explore the impact of the number of partitions on HHJ's performance and propose a new lower bound for the number of partitions. We design and evaluate different partition insertion techniques to maximize memory utilization with the least CPU cost. Additionally, we consider a comprehensive set of algorithms for dynamically selecting a partition to spill and compare the results against previously published studies. We then present and evaluate two alternative growth policies for spilled partitions. These algorithms have been implemented in the context of Apache AsterixDB and evaluated under different scenarios such as variable record sizes, different distributions of join attributes, and different storage types, including HDD, SSD, and Amazon Elastic Block Store (Amazon EBS).

Over the last 20 years, the progress of information technology has allowed many companies to generate, integrate, store, and analyze data of unprecedented size and complexity. In many cases, this data is personal data and how it can be used is therefore subject to laws that depend on the specific countries and application domains. For example, the General Data Protection Regulation (GDPR) introduced in the European Union imposes strict rules on how personal data can be processed. Analyzing personal data can create tremendous value, but at the same time companies must ensure that they remain legally compliant. Unfortunately, existing systems offer only limited or no support at all for processing personal data in a privacy-aware manner. Approaches that have emerged from the academic and industrial research environments need to be integrated into large systems (like enterprise systems) in a manageable and scalable way. In many IT environments, it is also desirable and necessary to combine and to integrate personal data with other (non-personal) data in a seamless fashion. In this paper, we present the first steps that SAP has taken to provide its database management system SAP HANA with privacy-enhanced processing capabilities, referred to in the following as SAP HANA Data Anonymization. Various goals on both the conceptual and technical levels were followed with the aim of providing SAP customers today with an integrated processing environment for personal and non-personal data.

Set similarity joins, which compute pairs of similar sets, constitute an important operator primitive in a variety of applications, including applications that must process large amounts of data. To handle these data volumes, several distributed set similarity join algorithms have been proposed. Unfortunately, little is known about the relative performance, strengths and weaknesses of these techniques. Previous comparisons are limited to a small subset of relevant algorithms, and the large differences in the various test setups make it hard to draw overall conclusions. In this paper we survey ten recent, distributed set similarity join algorithms, all based on the MapReduce paradigm. We empirically compare the algorithms in a uniform test environment on twelve datasets that expose different characteristics and represent a broad range of applications. Our experiments yield a surprising result: All algorithms in our test fail to scale for at least one dataset and are sensitive to long sets, frequent set elements, low similarity thresholds, or a combination thereof. Interestingly, some algorithms even fail to handle the small datasets that can easily be processed in a non-distributed setting. Our analytic investigation of the algorithms pinpoints the reasons for the poor performance and targeted experiments confirm our analytic findings. Based on our investigation, we suggest directions for future research in the area.

Progressive optimization introduces robustness for database workloads against wrong estimates, skewed data, correlated attributes, or outdated statistics. Previous work focuses on cardinality estimates and rely on expensive counting methods as well as complex learning algorithms. In this paper, we utilize performance counters to drive progressive optimization during query execution. The main advantages are that performance counters introduce virtually no costs on modern CPUs and their usage enables a non-invasive monitoring. We present fine-grained cost models to detect differences between estimates and actual costs which enables us to kick-start reoptimization. Based on our cost models, we implement an optimization approach that estimates the individual selectivities of a multi-selection query efficiently. Furthermore, we are able to learn properties like sortedness, skew, or correlation during run-time. In our evaluation we show, that the overhead of our approach is negligible, while performance improvements are convincing. Using progressive optimization, we improve runtime up to a factor of three compared to average run-times and up to a factor of 4,5 compared to worst case run-times. As a result, we avoid costly operator execution orders and; thus, making query execution highly robust.

In this paper, we accelerate the processing of tree-based in-dex structures by using SIMD instructions. We adapt the B+-Tree and prefix B-Tree (trie) by changing the search al-gorithm on inner nodes from binary search to k-ary search. The k-ary search enables the use of SIMD instructions, which are commonly available on most modern processors today. The main challenge for using SIMD instructions on CPUs is their inherent requirement for consecutive memory loads. The data for one SIMD load instruction must be located in consecutive memory locations and cannot be scattered over the entire memory. The original layout of tree-based index structures does not satisfy this constraint and must be adapted to enable SIMD usage. Thus, we introduce two tree adaptations that satisfy the specific constraints of SIMD instructions. We present two di↵erent algorithms for trans-forming the original tree layout into a SIMD-friendly layout. Additionally, we introduce two SIMD-friendly search algo-rithms designed for the new layout. Our adapted B+-Tree speeds up search processes by a fac-tor of up to eight for small data types compared to the origi-nal B+-Tree using binary search. Furthermore, our adapted prefix B-Tree enables a high search performance even for larger data types. We report a constant 14 fold speedup and an 8 fold reduction in memory consumption compared to the original B+-Tree. 1.

Data flows are a popular abstraction to define dataintensive processing tasks. In order to support a wide range of use cases, many data processing systems feature MapReduce-style user-defined functions (UDFs). In contrast to UDFs as known from relational DBMS, MapReduce-style UDFs have less strict templates. These templates do not alone provide all the information needed to decide whether they can be reordered with relational operators and other UDFs. However, it is well-known that reordering operators such as filters, joins, and aggregations can yield runtime improvements by orders of magnitude. We demonstrate an optimizer for data flows that is able to reorder operators with MapReduce-style UDFs written in an imperative language. Our approach leverages static code analysis to extract information from UDFs which is used to reason about the reorderbility of UDF operators. This information is sufficient to enumerate a large fraction of the search space covered by conventional RDBMS optimizers including filter and aggregation push-down, bushy join orders, and choice of physical execution strategies based on interesting properties. We demonstrate our optimizer and a job submission client that allows users to peek step-by-step into each phase of the optimization process: the static code analysis of UDFs, the enumeration of reordered candidate data flows, the generation of physical execution plans, and their parallel execution. For the demonstration, we provide a selection of relational and nonrelational data flow programs which highlight the salient features of our approach.

Workflow concepts are well suited for scenarios where many distributed entities work collaboratively together to achieve a common goal. Today, workflows are mostly used as computerized model for business processes executed in instances in commercial Workflow Management Systems. However, there are many other application domains where computer-supported cooperative work can be captured and organized by workflows. In this paper, we investigate the task of scheduling workflows in self-organizing wireless networks for disaster scenarios. Most research work in the field of workflow scheduling has been driven by temporal and causality constraints. We present an adaptive scheduling algorithm that finds a suitable execution sequence for workflow activities by additionally considering resource allocation constraints and dynamic topology changes. Our approach utilizes a multi-stage distribution algorithm which we extend with techniques to cope with network dynamics.

Complex queries often contain common or similar subexpressions, either within a single query or among multiple queries submitted as a batch. If so, query execution time can be improved by evaluating a common subexpression once and reusing the result in multiple places. However, current query optimizers do not recognize and exploit similar subexpressions, even within the same query. We present an efficient, scalable, and principled solution to this long-standing optimization problem. We introduce a light-weight and effective mechanism to detect potential sharing opportunities among expressions. Candidate covering subexpressions are constructed and optimization is resumed to determine which, if any, such subexpressions to include in the final query plan. The chosen subexpression(s) are computed only once and the results are reused to answer other parts of queries. Our solution automatically applies to optimization of query batches, nested queries, and maintenance of multiple materialized views. It is the first comprehensive solution covering all aspects of the problem: detection, construction, and cost-based optimization. Experiments on Microsoft SQL Server show significant performance improvements with minimal overhead.

We study the novel problem of efficiently computing the update distance for a pair of relational databases. In analogy to the edit distance of strings, we define the update distance of two databases as the minimal number of set-oriented insert, delete and modification operations necessary to transform one database into the other. We show how this distance can be computed by traversing a search space of database instances connected by update operations. This insight leads to a family of algorithms that compute the update distance or approximations of it. In our experiments we observed that a simple heuristic performs surprisingly well in most considered cases.Our motivation for studying distance measures for databases stems from the field of scientific databases. There, replicas of a single database are often maintained at different sites, which typically leads to (accidental or planned) divergence of their content. To re-create a consistent view, these differences must be resolved. Such an effort requires an understanding of the process that produced them. We found that minimal update sequences of set-oriented update operations are a proper and concise representation of systematic errors, thus giving valuable clues to domain experts responsible for conflict resolution.

Traditional approaches to query processing aim at rewriting a given query into another more efficient one that uses less time and/or resources during the execution. There by, the rewritten query must be equivalent to the initial one, i.e., it must provide the same result. However, rewriting queries in equivalent ways do not always satisfy the user's needs, in particular when the user does not receive any answer at all. In this paper, we propose a new approach for query processing which allows to rewrite a query into another one which is not necessary equivalent but can provide more meaningful result satisfying the user's intention. For this purpose, we illustrate how semantic knowledge inform of ontologies could be effectively used. We develop a set of rewriting rules which rely on semantic information extracted form the ontology associated with the database. In addition, we discuss features of the necessary mappings between the ontology and its underlying database.

The characteristics of XML documents require new ways of storing and querying such documents. Queries on both textual content and structural aspects must be supported efficiently. For this reason, we examined existing work on both document storage approaches and models for querying documents to derive requirements that are essential for the storage of XML documents. As a result of our study, we designed the Access Support Tree and TextArray (AST/TA) data structure. The important idea of the AST/TA data structure is the separation of the (logical) structure of a document from its "visible" text content. The latter is represented as a single contiguous string. At the same time the AST/TA data structure provides a tight integration to guarantee consistent changes. We introduce the AST/TA data structure formally by, its abstraction, namely the AST/TA model and compare requirements of our AST/TA approach with those found in the current literature. Finally, we describe the advantage of the AST/TA model based on the AST/TA design principles.

Over the last decade the need to implement functions into a DBMS that are application-specific has increased. For this reason today most object-relational DBMS (ORDBMS) provide features that allow the user to include application-specific functions into the DBMS for their execution within database queries. This paper reports on an implementation effort to include spatial operations into an ORDBMS as a basis to support geographic information systems (GIS). Based on the technique of multi-step query processing using z-values we show how to transform "straight forward" queries into more sophisticated ones that use the existing ORDBMS as is. That is, existing index methods and existing optimization techniques are sufficient to execute the rewritten queries efficiently. For this purpose we introduce several user-defined functions and types that provide the necessary basis for an efficient implementation. To validate our implementation we used a subset of queries as defined in the SEQUOIA2000 benchmark. Our measurements show that the performance improvements between the original queries and the rewritten ones are dramatic.

A variety of heterogenous data sources is available in the field of molecular biology. The authors focus lies on the biological sequence data, i.e. data maintained in collections like EMBL or SWISS-PROT. They propose a relational model based on an entity-relationship approach for this discourse world. This is the foundation of a flexible architecture useful for a variety of purposes, e.g. for sequence comparison. They present their first application system within this architecture, the sequence analysis tool NNSAT. The description of this system is accompanied by a short review of the data model and a section on the problem of sequence comparison in which they propose a small modification of the Needleman and Wunsch (1970) alignment method.

Today's DBMSs are unable to support the increasing demands of the various applications that would like to use a DBMS. Each kind of application poses new requirements for the DBMS. The Starburst project at IBM's Almaden Research Center aims to extend relational DBMS technology to bridge this gap between applications and the DBMS. While providing a full function relational system to enable sharing across applications, Starburst will also allow (sophisticated) programmers to add many kinds of extensions to the base system's capabilities, including language extensions (e.g., new datatypes and operations), data management extensions (e.g., new access and storage methods) and internal processing extensions (e.g., new join methods and new query transformations). To support these features, the database query language processor must be very powerful and highly extensible. Starburst's language processor features a powerful query language, rule-based optimization and query rewrite, and an execution system based on an extended relational algebra. In this paper, we describe the design of Starburst's query language processor and discuss the ways in which the language processor can be extended to achieve Starburst's goals.

This paper investigates the problem of translating set-oriented query specifications into iterative programs. The translation uses techniques of functional programming and program transformation. We present two algorithms that generate iterative programs from algebra-based query specifications. The first algorithm translates query specifications into recursive programs. Those are simplified by sets of transformation rules before the algorithm generates the final iterative form. The second algorithm uses a two-level translation that generates iterative programs faster than the first algorithm. On the first level a small set of transformation rules performs structural simplification before the functional combination on the second level yields the final iterative form.

The query optimizer is an important system component of a relational database management system (DBMS). It is the responsibility of this component to translate the user-submitted query - usually written in a non-procedural language - into an efficient query evaluation plan (QEP) which is then executed against the database. The research literature describes a wide variety of optimization strategies for different query languages and implementation environments. However, very little is known about how to design and structure the query optimization component to implement these strategies.

Over the last decade many techniques for optimizing relational queries have been developed. However, the problem of translating these set-oriented query specifications into other forms for efficient execution has received little attention.