Compute Express Link (CXL) is an interconnect that extends the traditional memory hierarchy beyond a single machine. It enables disaggregated memory architecture, where memory can be pooled and shared across multiple hosts effectively. Previous systems and approaches were limited to CXL 1.0 which is restricted to intra-host scaling of memory resources with no out of the box support for sharing across multiple hosts. We evaluate a commercially available CXL 2.0 memory switching platform for multi-host shared memory. While prior work has largely focused on emulation, FPGA-based or non-available prototypes, we investigate the real-world performance and system implications of deploying CXL as shared memory across multiple hosts on a commercially available setup. Our evaluation reveals fundamental trade-offs: Access to shared CXL memory exhibits up to 4x higher latency and significantly lower bandwidth compared to local DRAM, but enables flexible memory pooling with fair sharing across hosts. More importantly, we show that the lack of hardware cache coherence in CXL 2.0 introduces non-trivial challenges, requiring carefully chosen instruction patterns.

Accelerators allow computation to be offloaded from the CPU and improve query performance.Intel has recently introduced a dedicated Data Accelerator Complex (DAC) for its scalable Xeon processor family.Among the four accelerators, the In-Memory Analytics Accelerator (IAA) provides functionality for offloading query processing operations from the CPU.In this work, we investigate the potential of this accelerator for database queries.We propose a coreless query processing approach in which query operators such as scan, filter, but also sorting, and joins are executed on the accelerator.Our evaluation shows that offloading tasks such as filter and join operators to IAA achieves performance comparable to highthread-count CPU processing.Further speedups on compressed data enable the DBMS to free CPU resources more efficiently for other tasks.

Updates in graph DBMS lead to structural changes in the graph over time with different intermediate states. Capturing these changes and their time is one of the main purposes of temporal DBMS. Most DBMSs built their temporal features based on their non-temporal processing and storage without considering the memory hierarchy of the underlying system. This leads to slower temporal processing and poor storage utilization. In this paper, we propose a storage and processing strategy for (bi-) temporal graphs using temporal materialized views (TMV) while exploiting the memory hierarchy of a modern system. Further, we show a solution to the query containment problem for certain types of temporal graph queries. Finally, we evaluate the overhead and performance of the presented approach. The results show that using TMV reduces the runtime of temporal graph queries while using less memory.

Modern workflows for developing ML pipelines utilize ML artifact management systems (ML AMSs) such as MLflow in addition to traditional version control systems such as Git. ML AMSs collect data, model, metadata and software artifacts used and produced in pipeline development workflows. While ensuring repeatability and reproducibility, the provenance capabilities are still rudimentary, mainly due to incomplete traces, coarse granularity, and limited query capabilities. In this paper, we introduce a comprehensive PROV-compliant provenance model that captures end-to-end provenance traces of ML pipelines, their artifacts, and their relationships based on MLflow and Git activities. Moreover, we present the tool MLflow2PROV for continuously extracting provenance graphs according to our model, enabling querying, analyzing, and processing of the collected provenance information.

Distributed partitioned joins are one of the most expensive operators in distributed DBMSs where a major part of the execution is attributed to network transfer costs. Although high-speed network technologies, such as RDMA, can lower this cost, they still come with significantly higher latency than local DRAM access. The emerging CXL interconnect protocol promises to provide direct and cache-coherent access to remote memory while offering byte-addressable memory access without CPU intervention. For short-distance communication in distributed DBMSs, CXL represents an interesting alternative for low-latency requirements. In this work, we explore how CXL can be leveraged for engine-internal communication and data exchange. We discuss and apply communication strategies to distributed joins. We emulate various CXL characteristics based on optimistic and pessimistic assumptions on the real performance of upcoming CXL devices and evaluate their impact on the execution of distributed joins. Our results show that CXL has the potential to improve distributed join performance.

Processing-in-Memory (PIM) is a new computing paradigm aimed at minimizing data movement, which is a bottleneck in modern and emerging applications. PIM upgrades the otherwise passive memory subsystem to an active computation role along with the processor. PIM achieves this by moving processing cores to where the data resides, thereby reducing memory access latency, increasing overall memory bandwidth and decreasing energy consumption. In this paper, we leverage the commercially available real UPMEM PIM system to accelerate the execution of the aggregation operator, which is data-intensive and involves large amounts of data movements. We tailor the operator to PIM, propose various performance optimizations with regards to the architectural peculiarities of the UPMEM PIM system and conduct evaluations in comparison with a CPU baseline implementation. Our PIM-based aggregation outperforms the CPU baseline by up to a speedup of 2.41 x.

Debugging, evaluating, and optimizing stream processing applications is challenging due to continuous streams of input data and typically distributed and parallel execution environments. To address these issues, we present an approach for explorative debugging of stream processing pipelines that allows in-depth investigation of a pipeline's execution behavior and evolution. The time traveling debugger enables traveling back in time within the pipeline's execution history and thoroughly analyzing and retracing each fine-grained step. Any changes made to the pipeline's structure or parameters are captured based on provenance information and can be reviewed, compared, and analyzed with the provenance inspector to understand the impact of each alteration on the quality of the pipeline.

Distributed in-memory processing frameworks accelerate application runs by caching important datasets in memory. Allocating a suitable cluster configuration for caching these datasets plays a crucial role in achieving minimal cost. We present Agile-ant, a self-managing framework that identifies important datasets and scales out the cluster memory to cache them on the fly without any human interaction, without any prior knowledge of the application, the characteristics of the input data, the specification of the computing resources and their utilization by multiple-tenants. We evaluate Agile-ant on various real-world applications. Compared with our baseline, Agile-ant reduces execution cost by 78.3% on average and provides better performance than the related work.

The Processing-in-Memory (PIM) paradigm promises to accelerate data processing by pushing down computation to memory, reducing the amount of data transfer between memory and CPU, and – in this way – relieving the CPU from processing. Particularly, in in-memory databases memory access becomes a performance bottleneck. Thus, PIM seems to offer an interesting solution for database processing. In this work, we investigate how commercially available PIM technology can be leveraged to accelerate query processing by offloading (parts of) query operators to memory. Furthermore, we show how to address the problem of limited PIM storage capacity by interleaving transfer and computation and present a cost model for the data placement problem.

Stream processing takes on an important role as a hot topic of our time. More and more applications generate large amounts of heterogeneous data that need to be processed in real-time. However, the dynamic and high frequent nature of stream processing applications complicates the debugging process since the constant flow of data can not be slowed down, paused, or reverted to previous states to analyze the execution step-by-step. In this demonstration, we present StreamVizzard’s visual and interactive pipeline debugger that allows reverting the pipeline state to any arbitrary point in the past to review or repeat critical parts of the pipeline step by step. During this process, our extensive visualizer allows to explore the processed data and statistics of each operator to retrace and understand the data flow and behavior of the pipeline.

Abstract Compiling database queries into compact and efficient machine code has proven to be a great technique to improve query performance and exploit characteristics of modern hardware. Particularly for graph database queries, which often execute the exact instructions for processing, this technique can lead to an improvement. Furthermore, compilation frameworks like LLVM provide powerful optimization techniques and support different backends. However, the time for generating and optimizing machine code becomes an issue for short-running queries or queries which could produce early results quickly. In this work, we present an adaptive approach integrating graph query interpretation and compilation. While query compilation and code generation are running in the background, the query execution starts using the interpreter. When the code generation is finished, the execution switches to the compiled code. Our evaluation of the approach using short-running and complex queries show that autonomously switching execution modes helps to improve the runtime of all types of queries and additionally to hide compilation times and the additional latencies of the underlying storage.

Abstract Hybrid transactional/analytical processing (HTAP) workloads on graph data can significantly benefit from GPU accelerators. However, to exploit the full potential of GPU processing, dedicated graph representations are necessary, which mostly make in-place updates difficult. In this paper, we discuss an adaptive update handling approach in a graph database system for HTAP workloads. We discuss and evaluate strategies for propagating transactional updates from an update-friendly table storage to a GPU-optimized sparse matrix format for analytics.

Distributed in-memory processing frameworks accelerate iterative workloads by caching suitable datasets in memory rather than recomputing them in each iteration. Selecting appropriate datasets to cache as well as allocating a suitable cluster configuration for caching these datasets play a crucial role in achieving optimal performance. In practice, both are tedious, time-consuming tasks and are often neglected by end users, who are typically not aware of workload semantics, sizes of intermediate data, and cluster specification.

Abstract After the introduction of Persistent Memory in the form of Intel’s Optane DC Persistent Memory on the market in 2019, it has found its way into manifold applications and systems. As Google and other cloud infrastructure providers are starting to incorporate Persistent Memory into their portfolio, it is only logical that cloud applications have to exploit its inherent properties. Persistent Memory can serve as a DRAM substitute, but guarantees persistence at the cost of compromised read/write performance compared to standard DRAM. These properties particularly affect the performance of index structures, since they are subject to frequent updates and queries. However, adapting each and every index structure to exploit the properties of Persistent Memory is tedious. Hence, we require a general technique that hides this access gap, e.g., by using DRAM caching strategies. To exploit Persistent Memory properties for analytical index structures, we proposeselective caching. It is based on a mixture of dynamic and static caching of tree nodes in DRAM to reach near-DRAM access speeds for index structures. In this paper, we evaluate selective caching on the OLAP-optimized main-memory index structure Elf, because its memory layout allows for an easy caching. Our experiments show that if configured well, selective caching with a suitable replacement strategy can keep pace with pure DRAM storage of Elf while guaranteeing persistence. These results are also reflected when selective caching is used for parallel workloads.

Developers of Apache Spark applications can accelerate their workloads by caching suitable intermediate results in memory and reusing them rather than recomputing them all over again every time they are needed. However, as scientific workflows are becoming more complex, application developers are becoming more prone to making wrong caching decisions, which we refer to as caching anomalies , that lead to poor performance. We present and give a demonstration of Spark Caching Anomalies Detector (SparkCAD) , a developer decision support tool that visualizes the logical plan of Spark applications and detects caching anomalies.

The cost of DRAM contributes significantly to the operating costs of in-memory database management systems (IMDBMS). Persistent memory (PMEM) is an alternative type of byte-addressable memory that offers --- in addition to persistence --- higher capacities than DRAM at a lower price with the disadvantage of increased latencies and reduced bandwidth. This paper evaluates PMEM as a cheaper alternative to DRAM for storing table base data, which can make up a significant fraction of an IMDBMS' total memory footprint. Using a prototype implementation in the SAP HANA IMDBMS, we find that placing all table data in PMEM can reduce query performance in analytical benchmarks by more than a factor of two, while transactional workloads are less affected. To quantify the performance impact of placing individual data structures in PMEM, we propose a cost model based on a lightweight workload characterization. Using this model, we show how to place data pareto-optimally in the heterogeneous memory. Our evaluation demonstrates the accuracy of the model and shows that it is possible to place more than 75% of table data in PMEM while keeping performance within 10% of the DRAM baseline for two analytical benchmarks.

Persistent memory (PMem) - also known as non-volatile memory (NVM) - offers new opportunities not only for the design of data structures and system architectures but also for failure recovery in databases. However, instant recovery can mean not only to bring the system up as fast as possible but also to continue long-running queries which have been interrupted by a system failure. In this work, we discuss how PMem can be utilized to implement query recovery for analytical graph queries. Furthermore, we investigate the trade-off between the overhead of managing the query state in PMem at query runtime as well as the recovery and restart costs.

Non-volatile memory (NVM) offers lower costs per capacity and higher total capacities than DRAM. However, NVM cannot simply be used as a drop-in replacement for DRAM in database management systems due to its different performance characteristics. We thus investigate the placement of column-store data structures in a hybrid hierarchy of DRAM and NVM, with the goal of placing as much data as possible in NVM without compromising performance. After analyzing how different memory access patterns affect query runtimes when columns are placed in NVM, we propose a heuristic that leverages lightweight access counters to suggest which structures should be placed in DRAM and which in NVM. Our evaluation using TPC-H shows that more than 80% of the data touched by queries can be placed in NVM with almost no slowdown, while naively placing all data in NVM would increase runtime by 53%.

The Python programming language has become very popular among data scientists because of its easy-to-learn syntax and rich ecosystem of libraries. Especially the Pandas framework is widely used for various data processing and analytics tasks. However, due to its memory management and eager evaluation Pandas does not scale and workstations quickly come to their limits even for moderate data set sizes. With Grizzly, we introduce a framework that produces SQL queries for operations on DataFrames, moving complexity from workstations to database servers. Grizzly allows to not only access data already stored in a database, but also to combine it with external data from files. Furthermore, users can use their own user-defined functions or use Grizzly’s model join feature to easily apply machine learning models to data, both being executed inside the database server. This allows for fast and scalable data analytics operations, even with a small workstation.

Graph databases are used for different applications like analyzing large networks, representing and querying knowledge graphs, and managing master data and complex data structures. Besides graph analytics, the transactional processing of concurrent updates and queries represents a challenging data management task. In this paper, we investigate the usage of persistent memory as a very promising technology for graph processing. We present a novel architecture for transactional processing of queries and updates on a property graph model that exploits and addresses the specific characteristics of persistent memory by hybrid storage and memory management as well as a just-in-time query compilation approach. Our experimental evaluation on interactive short read and update query workloads show that PMem-based systems that are well-designed to exploit PMem characteristics outperform traditional disk-based systems significantly and have only a small overhead compared to DRAM-only systems. Moreover, the evaluation shows that JIT compilation brings performance benefits especially when an adaptive compilation approach is leveraged to hide the overhead of compilation as well as the latency of PMem.

Modern big data applications integrate data from various sources. As a result, these datasets may not satisfy perfect constraints, leading to sparse schema information and non-optimal query performance. The existing approach of PatchIndexes enable the definition of approximate constraints and improve query performance by exploiting the materialized constraint information. As real world data warehouse workloads are often not limited to read-only queries, we enhance the PatchIndex structure towards an update-conscious design in this paper. Therefore, we present a sharded bitmap as the underlying data structure which offers efficient update operations, and describe approaches to maintain approximate constraints under updates, avoiding index recomputations and full table scans. In our evaluation, we prove that PatchIndexes provide more lightweight update support than traditional materialization approaches.

Abstract Cloud data warehouse systems lower the barrier to access data analytics. These applications often lack a database administrator and integrate data from various sources, potentially leading to data not satisfying strict constraints. Automatic schema optimization in self-managing databases is difficult in these environments without prior data cleaning steps. In this paper, we focus on constraint discovery as a subtask of schema optimization. Perfect constraints might not exist in these unclean datasets due to a small set of values violating the constraints. Therefore, we introduce the concept of a generic PatchIndex structure, which handles exceptions to given constraints and enables database systems to define these approximate constraints. We apply the concept to the environment of distributed databases, providing parallel index creation approaches and optimization techniques for parallel queries using PatchIndexes. Furthermore, we describe heuristics for automatic discovery of PatchIndex candidate columns and prove the performance benefit of using PatchIndexes in our evaluation.

Persistent Memory (PM) represents a very promising, next-generation memory solution with a significant impact on database architectures. Several data structures for this new technology have already been proposed. However, primarily only complete structures are presented and evaluated. Thus, the implications of the individual ideas and PM features are concealed. Therefore, in this paper, we disassemble the structures presented so far, identify their underlying design primitives, and assign them to appropriate design goals. As a result of our comprehensive experiments on real PM hardware, we can reveal the trade-offs of the primitives for various access patterns and pinpoint their best use cases.

Re-Pair is a compression algorithm well-suited for applications that require random accesses to compressed data, but has not found widespread use in the data management community due to its prohibitively high compression times. As Re-Pair is a computationally expensive algorithm and FPGAs are becoming more and more common to accelerate such problems in data centers, we devise an FPGA system that performs Re-Pair compression. The system is implemented in OpenCL, aside from a hash table and sorting component realized in RTL for more control over the synthesized hardware. Our experiments demonstrate that an Intel Arria® 10 GX FPGA with our system compresses an order of magnitude faster than a highly-optimized CPU version of Re-Pair. We discuss further optimization opportunities and argue that our system can scale to being deployed on a more resourceful FPGA for even better performance.

Cloud infrastructures allow to dynamically adapt to workload changes by provisioning additional resources or deprovisioning resources to reduce costs. This offers also opportunities for scalable distributed data management. However, elastic scaling in databases requires to migrate or even repartition data. In this work, we present an approach implemented in Actian’s MPP solution VectorH that speeds up the elastic resizing process by minimizing partition reassignments while still achieving load balancing. Moreover, we describe a buffer matching and prefilling technique to further increase performance after the resize step. The experimental evaluation shows that our solution significantly outperforms the non-elastic way of scaling using a system restart by a factor of 2 up to 4 and reduces downtimes during resizing to less than one minute.

Abstract Apache Spark jobs are often characterized by processing huge data sets and, therefore, require runtimes in the range of minutes to hours. Thus, being able to predict the runtime of such jobs would be useful not only to know when the job will finish, but also for scheduling purposes, to estimate monetary costs for cloud deployment, or to determine an appropriate cluster configuration, such as the number of nodes. However, predicting Spark job runtimes is much more challenging than for standard database queries: cluster configuration and parameters have a significant performance impact and jobs usually contain a lot of user-defined code making it difficult to estimate cardinalities and execution costs. In this paper, we present a gray-box modeling methodology for runtime prediction of Apache Spark jobs. Our approach comprises two steps: first, a white-box model for predicting the cardinalities of the input RDDs of each operator is built based on prior knowledge about the behavior and application parameters such as applied filters data, number of iterations, etc. In the second step, a black-box model for each task constructed by monitoring runtime metrics while varying allocated resources and input RDD cardinalities is used. We further show how to use this gray-box approach not only for predicting the runtime of a given job, but also as part of a decision model for reusing intermediate cached results of Spark jobs. Our methodology is validated with experimental evaluation showing a highly accurate prediction of the actual job runtime and a performance improvement if intermediate results can be reused.

Abstract String dictionaries constitute a large portion of the memory footprint of database applications. While strong string dictionary compression algorithms exist, these come with impractical access and compression times. Therefore, lightweight algorithms such as front coding (PFC) are favored in practice. This paper endeavors to make strong string dictionary compression practical. We focus on Re-Pair Front Coding (RPFC), a grammar-based compression algorithm, since it consistently offers better compression ratios than other algorithms in the literature. To accelerate compression times, we propose block-based RPFC (BRPFC) which consists in independently compressing small blocks of the dictionary. For further accelerated compression times especially on large string dictionaries, we also propose an alternative version of BRPFC that uses sampling to speed up compression. Moreover, to accelerate access times, we devise a vectorized access method, using $$\hbox {Intel}^{\circledR }$$ Intel ® Advanced Vector Extensions 512 ( $$\hbox {Intel}^{\circledR }$$ Intel ® AVX-512). Our experimental evaluation shows that sampled BRPFC offers compression times up to 190 $$\times $$ × faster than RPFC, and random string lookups 2.3 $$\times $$ × faster than RPFC on average. These results move our modified RPFC into a practical range for use in database systems because the overhead of Re-Pair-based compression for access times can be reduced by 2 $$\times $$ × .

String dictionaries constitute a large portion of the memory foot-print of database applications. While strong string dictionary compression algorithms exist, these come with impractical access and compression times. Therefore, lightweight algorithms such as front coding are favored in practice. This paper endeavors to make strong string dictionary compression practical. We focus on Re-Pair Front Coding (RPFC), a grammar-based compression algorithm, since it consistently offers better compression ratios than other algorithms in the literature. To accelerate compression times, we propose block-based RPFC, which consists in compressing independently small blocks of the dictionary. Moreover, to accelerate access times, we devise a vectorized access method, using Intel® Advanced Vector Extensions 512 (Intel® AVX-512), that is enabled by two specific changes we propose to RPFC. Our experimental evaluation shows that our proposed techniques accelerate compression and access times by up to 24x and 2.9x, respectively. These results move our modified RPFC into a practical range for use in database systems.

Transactional database systems and data stream management systems have been thoroughly investigated over the past decades. While both systems follow completely different data processing models, the combined concept of transactional stream processing promises to be the future data processing model. So far, however, it has not been investigated how well-known concepts found in DBMS or DSMS regarding multi-user support can be transferred to this model or how they need to be redesigned. In this paper, we propose a transaction model combining streaming and stored data as well as continuous and ad-hoc queries. Based on this, we present appropriate protocols for concurrency control of such queries guaranteeing snapshot isolation as well as for consistency of transactions comprising several shared states. In our evaluation, we show that our protocols represent a resilient and scalable solution meeting all requirements for such a model.

With High-Bandwidth Memory (HBM), an additional opportunity on hardware side for performance benefits is given. The large amount of available bandwidth compared to regular DRAM allows the execution of high numbers of threads in parallel masking penalties of concurrent memory accesses. This is especially interesting considering database join algorithms optimized for multicore CPUs, even more when running on a manycore processor like a Xeon Phi Knights Landing (KNL). The drawback of HBM, however, is its small size and given penalties in random memory access patterns.

Cardinality estimation is a crucial task in query optimization and typically relies on heuristics and basic statistical approximations. At execution time, estimation errors might result in situations where intermediate result sizes may differ from the estimated ones, so that the originally chosen plan is not the optimal plan anymore. In this paper we analyze the deviation from the estimate, and denote the cardinality range of an intermediate result, where the optimal plan remains optimal as the optimality range. While previous work used simple heuristics to calculate similar ranges, we generate the precise bounds for the optimality range considering all relevant plan alternatives. Our experimental results show that the fixed optimality ranges used in previous work fail to characterize the range of cardinalities where a plan is optimal. We derive theoretical worst case bounds for the number of enumerated plans required to compute the precise optimality range, and experimentally show that in real queries this number is significantly smaller. Our experiments also show the benefit for applications like Mid-Query Re-Optimization in terms of significant execution time improvement.

The quality of query execution plans in database systems determines how fast a query can be executed. It has been shown that conventional query optimization still selects sub-optimal or even bad execution plans, due to errors in the cardinality estimation. Although cardinality estimation errors are an evident problem, they are in general not considered in the selection of query execution plans. In this paper, we present three novel metrics for the robustness of relational query execution plans w.r.t. cardinality estimation errors. We also present a novel plan selection strategy that takes both, estimated cost and estimated robustness into account, when choosing a plan for execution. Finally, we share the results of our experimental comparison between robust and conventional plan selection on real world and synthetic benchmarks, showing a speedup of at most factor 3.49.

Nowadays, a vast amount of data is generated and collected every moment and often, this data has a spatial and/or temporal aspect. To analyze the massive data sets, big data platforms like Apache Hadoop MapReduce and Apache Spark emerged and extensions that take the spatial characteristics into account were created for them. In this paper, we analyze and compare existing solutions for spatial data processing on Hadoop and Spark. In our comparison, we investigate their features as well as their performances in a micro benchmark for spatial filter and join queries. Based on the results and our experiences with these frameworks, we outline the requirements for a general spatio-temporal benchmark for Big Spatial Data processing platforms and sketch first solutions to the identified problems.

Modern databases can run application logic defined in stored procedures inside the database server to improve application speed. The SQL standard specifies how to call external stored routines implemented in programming languages, such as C, C++, or JAVA, to complement declarative SQL-based application logic. This is beneficial for scientific and analytical algorithms because they are usually too complex to be implemented entirely in SQL. At the same time, database applications like matrix calculations or data mining algorithms benefit from multi-threading to parallelize compute-intensive operations. Multi-threaded application code, however, introduces a resource competition between the threads of applications and the threads of the database task scheduler. In this paper, we show that multi-threaded application code can render the database's workload scheduling ineffective and decrease the core throughput of the database by up to 50%. We present a general approach to address this issue by integrating shared memory programming solutions into the task schedulers of databases. In particular, we describe the integration of OpenMP into databases. We implement and evaluate our approach using SAP HANA. Our experiments show that our integration does not introduce overhead, and can improve the throughput of core database operations by up to 15%.

Usability often plays a key role when software is brought to market, including clearly structured workflows, the way of presenting information to the user, and, last but not least, how he interacts with the application. In this context, input devices as 3D cameras or (multi-)touch displays became om-nipresent in order to define new intuitive ways of user inter-action. State-of-the-art systems tightly couple application logic with separate gesture detection components for sup-ported devices. Hard-coded rules or static models obtained by applying machine learning algorithms on many training samples are used in order to robustly detect a pre-defined set of gesture patterns. If possible at all, it becomes difficult to extend these sets with new patterns or to modify exist-ing ones – difficult for both, application developers and end users. Further, adding gesture support for legacy software or for additional devices becomes difficult with this hard-wired approach. In previous research we demonstrated how the database community can contribute to this challenge by leveraging complex event processing on data streams to express gesture patterns. While this declarative approach decouples application logic from gesture detection compo-nents, its major drawback was the non-intuitive definition of gesture queries. In this paper, we present an approach that is related to density-based clustering in order to find declarative gesture descriptions using only a few samples. We demonstrate the algorithms on mining definitions for multi-dimensional gestures from the sensor data stream that is delivered by a Microsoft Kinect 3D camera, and provide a way for non-expert users to intuitively customize gesture-controlled user interfaces – even during runtime. 1.

Wireless sensor networks enable cost-effective data collection for tasks such as precision agriculture and environment monitoring. However, the resource-constrained nature of sensor nodes, which often have both limited computational capabilities and battery lifetimes, means that applications that use them must make judicious use of these resources. Research that seeks to support data intensive sensor applications has explored a range of approaches and developed many different techniques, including bespoke algorithms for specific analyses and generic sensor network query processors. However, all such proposals sit within a multi-dimensional design space, where it can be difficult to understand the implications of specific decisions and to identify optimal solutions. This paper presents a benchmark that seeks to support the systematic analysis and comparison of different techniques and platforms, enabling both development and user communities to make well informed choices. The contributions of the paper include: (i) the identification of key variables and performance metrics; (ii) the specification of experiments that explore how different types of task perform under different metrics for the controlled variables; and (iii) an application of the benchmark to investigate the behavior of several representative platforms and techniques.

Mobile systems which include sensor networks, generate a continuous unmatched volume of primitive event streams with various properties where the interior semantic information of these events is generally very limited. Moreover, forwarding all these events to a central processing entity is not favored for limited-resource systems, it would deplete nodes' resources e.g., the energy. The goal of this work is to address these issues by extracting useful information locally, transmitting only this information and avoiding transmission of unnecessary low-level data between nodes. Therefore, an In-Network Distributed Complex Event Processing (INDCEP) based solution is proposed. INDCEP technology is used to perform the processing within the network by pushing complex event processing into network nodes. This research aims to develop a robust and high performance Distributed Complex Event Processing Engine for Mobile Systems (CEPEMS) based on aforementioned technology. It focuses on distributed event detection via disseminating distributed plans into a network of sensor nodes to perform complex event tasks. Furthermore, we present an optimization technique for the distributed queries and cost model to decide which query portions can be executed whether inside sensor nodes or at local CEP engine instance in a centralized point.

Many emerging context-aware mobile applications involve the execution of continuous queries over sensor data streams generated by a variety of on-board sensors on multiple personal mobile devices (aka smartphones). To reduce the energy-overheads of such large-scale, continuous mobile sensing and query processing, this paper introduces CQP, a collaborative query processing framework that exploits the overlap (in both the sensor sources and the query predicates) across multiple smartphones. The framework automatically identifies the shareable parts of multiple executing queries, and then reduces the overheads of repetitive execution and data transmissions, by having a set of `leader' mobile nodes execute and disseminate these shareable partial results. To further reduce energy, CQP utilizes lower-energy short-range wireless links (such as Bluetooth) to disseminate such results directly among proximate smartphones. We describe algorithms to support our server-assisted distributed query sharing and optimization strategy. Simulation experiments indicate that this approach can result in 60% reduction in the energy overhead of continuous query processing; when `leader' selection is dynamically rotated to equitably share the burden, we observe an increase of up to 65% in operational lifetime.

Efficient lookups in huge, possibly multi-dimensional datasets are crucial for the performance of numerous use cases that generate multiple search operations at the same time, like point queries in ray tracing or spatial joins in collision detection of interactive 3D applications. These applications greatly benefit from index structures that quickly filter relevant candidates for further processing. Since different lookup operations are independent from each other, they might be processed in parallel on modern hardware like multi-core CPUs or GPUs. But implementing efficient algorithms for all kinds of indexes on various hardware platforms is a challenging task. In this paper, we present a new approach that extends the existing GiST index framework with an abstraction layer for the hardware where index operations are executed. Furthermore, we provide first performance evaluations for the scan execution on CPUs and an Nvidia Tesla GPU.

Motion sensing input devices like Microsoft's Kinect offer an alternative to traditional computer input devices like keyboards and mouses. Daily new applications using this interface appear. Most of them implement their own gesture detection. In our demonstration we show a new approach using the data stream engine Andu IN. The gesture detection is done based on Andu IN's complex event processing functionality. This way we build a system that allows to define new and complex gestures on the basis of a declarative programming interface. On this basis our demonstration data3provides a basic natural interaction OLAP interface for a sample star schema database using Microsoft's Kinect.

Wireless sensor networks are often deployed to detect occurring changes in the environment. Detectability of the changes in the ambient environment contributes to the success of emerging sensor networks. The major challenges in designing change detection algorithms for wireless sensor networks are the restricted resources of sensors such as memory, communication bandwidth, and battery power. We propose a decentralized change detection framework for wireless sensor networks, present a novel algorithm using DFT coefficients as synopsis structures from signal-oriented data streams, which can reduce the amount of local memory required by the change detector while assuring accuracy of local detection. Furthermore, we show how to use a gossip-based framework for transmitting and aggregating the change detection results from the ambient area of events to the sink. This helps to find consensus among nodes in order to improve global detection accuracy while maintaining reasonable communication cost for the wireless sensor networks. We make empirical evaluations to show the effectiveness and the deployment potential of our change detection schemes in wireless sensor networks.

Query performance is a critical factor in modern business intelligence and data warehouse systems. An increasing number of companies uses detailed analyses for conducting daily business and supporting management decisions. Thus, several techniques have been developed for achieving near realtime response times - techniques which try to alleviate I/O bottlenecks while increasing the throughputs of available processing units, i.e. by keeping relevant data in compressed main-memory data structures and exploiting the read-only characteristics of analytical workloads.

Flash devices (solid state disks) promise a significant performance improvement for disk-based database processing. However, database storage structures and processing strategies originally designed for magnetic disks prevent the optimal utilization of SSDs. Based on previous work on bench-marking SSDs and a detailed discussion of I/O methods, in this paper, we analyze appropriate execution methods for database processing as well as important parameters and boundaries and present a tool which helps to derive these parameters.

Sensor networks have evolved to a powerful infrastructure component for event monitoring in many application scenarios. In addition to simple filter and aggregation operations, an important task in processing sensor data is data mining - the identification of relevant information and patterns. Limited capabilities of sensor nodes in terms of storage and processing capacity, battery lifetime, and communication demand a power-efficient, preferably sensor-local processing. In this paper, we present AnduIN, a system for developing, deploying, and running in-network data mining tasks. The system consists of a data stream processing engine, a library of operators for sensor-local processing, a box-and-arrow editor for specifying data mining tasks and deployment, a GUI providing the user with current information about the network and running queries, and an alerter notifying the user if a better query execution plan is available. At the demonstration site, we plan to show our system in action using burst detection as example application.

Modern Web or ¿Eternal-Beta¿ applications necessitate a flexible and easy-to-use data management platform that allows the evolutionary development of databases and applications. The classical approach of relational database systems following strictly the ACID properties has to be extended by an extensible and easy-to-use persistency layer with specialized DB features. Using the underlying concept of Software as a Service (SaaS) also enables an economic advantage based on the ¿economy of the scale¿, where application and system environments only need to be provided once but can be used by thousands of users. Within this tutorial, we are looking at the current state-of-the-art from different perspectives. We outline foundations and techniques to build database services based on the SaaS-paradigm. We discuss requirements from a programming perspective, show different dimensions in the context of consistency and reliability, and also describe different non-functional properties under the umbrella of Service-Level agreements (SLA).

Many relational databases exhibit complex dependencies between data attributes, caused either by the nature of the underlying data or by explicitly denormalized schemas. In data warehouse scenarios, calculated key figures may be materialized or hierarchy levels may be held within a single dimension table. Such column correlations and the resulting data redundancy may result in additional storage requirements. They may also result in bad query performance if inappropriate independence assumptions are made during query compilation. In this paper, we tackle the specific problem of detecting functional dependencies between columns to improve the compression rate for column-based database systems, which both reduces main memory consumption and improves query performance. Although a huge variety of algorithms have been proposed for detecting column dependencies in databases, we maintain that increased data volumes and recent developments in hardware architectures demand novel algorithms with much lower runtime overhead and smaller memory footprint. Our novel approach is based on entropy estimations and exploits a combination of sampling and multiple heuristics to render it applicable for a wide range of use cases. We demonstrate the quality of our approach by means of an implementation within the SAP NetWeaver Business Warehouse Accelerator. Our experiments indicate that our approach scales well with the number of columns and produces reliable dependence structure information. This both reduces memory consumption and improves performance for nontrivial queries.

Typical approaches for querying structured Web Data collect (crawl) and pre-process (index) large amounts of data in a central data repository before allowing for query answering. However, this time-consuming pre-processing phase however leverages the benefits of Linked Data -- where structured data is accessible live and up-to-date at distributed Web resources that may change constantly -- only to a limited degree, as query results can never be current. An ideal query answering system for Linked Data should return current answers in a reasonable amount of time, even on corpora as large as the Web. Query processors evaluating queries directly on the live sources require knowledge of the contents of data sources. In this paper, we develop and evaluate an approximate index structure summarising graph-structured content of sources adhering to Linked Data principles, provide an algorithm for answering conjunctive queries over Linked Data on theWeb exploiting the source summary, and evaluate the system using synthetically generated queries. The experimental results show that our lightweight index structure enables complete and up-to-date query results over Linked Data, while keeping the overhead for querying low and providing a satisfying source ranking at no additional cost.

Materializing results from complex aggregation queries helps to significantly improve response times in OLAP servers. This problem is known as the view selection problem: choosing the optimal set of aggregation tables (called configuration) for a given workload. In this paper we present an online approach for adjusting the configuration dynamically to the current workload. This approach is implemented as part of an open source OLAP server and acts on the level of multidimensional MDX queries. The work presents the details of cost estimation and optimization of the system demonstrated in [10] and extends it by an online tuning strategy.

With an ever growing complexity and data volume, the administration of today's relational database management systems has become one of the most important cost factors in their operation. Dynamic workloads and shifting demands require continuous effort from the DBA to deliver adequate performance. The goal of a modern DBMS must be to support the DBA's work with automated processes and workflows that facilitate quick and precise decisions. In this paper, we present the concept of an integrated performance monitoring in the Ingres DBMS that provides long-term collection of information valuable for performance tuning, problem identification and prediction. The approach of enhancing the DBMS core with monitoring features rather than adding an additional watchdog on top of the system leads to a high data resolution while still having only a minimal overhead. This concept was successfully prototyped in Ingres with a very small overhead for most usage scenarios. The prototype is able to collect and analyze data and to give useful recommendations on the physical database design to improve overall performance of the DBMS.

Structured P2P overlays supporting standard database functionalities are a popular choice for building large-scale distributed data management systems. In such systems, estimating the number of answers for structured queries can help approximating query completeness, but is especially challenging. In this paper, we propose to use routing graphs in order to achieve this. We introduce the general approach and briefly discuss further aspects like overhead and guarantees.

DBMS are a ubiquitous building block of the software stack in many complex applications. Middleware technologies, application servers and mapping approaches hide the core database technologies just like power, networking infrastructure and operating system services. Furthermore, many enterprise-critical applications demand a certain degree of quality of service (QoS) or guarantees, e.g. wrt. response time, transaction throughput, latency but also completeness or more generally quality of results. Examples of such applications are billing systems in telecommunication, where each telephone call has to be monitored and registered in a database, Ecommerce applications where orders have to be accepted even in times of heavy load and the waiting time of customers should not exceed a few seconds, ERP systems processing a large number of transactions in parallel, or systems for processing streaming or sensor data in realtime, e.g. in process automation of traffic control. As part of complex multilevel software stack, database systems have to share or contribute to these QoS requirements, which means that guarantees have to be given by the DBMS, too, and that the processing of database requests is predictable. Todays mainstream DBMS typically follow a best effort approach: requests are processed as fast as possible without any guarantees: the optimization goal of query optimizers and tuning approaches is rather to minimize resource consumption instead of just fulfilling given service level agreements. However, motivated by the situation described above there is an emerging need for database services providing guarantees or simply behave in a predictable manner and at the same time interact with other components of the software stack in order to fulfill the requirements. This is also driven by the paradigm of service-oriented architectures widely discussed in industry. Currently, this is addressed only by very specialized solutions. Nevertheless, database researchers have developed several techniques contributing to the goal of QoS-aware database systems. The purpose of the tutorial is to introduce database researchers and practitioners to the scope, the challenges and the available techniques to the problem of predictability and QoS agreements in DBMS.

A crucial prerequisite for the deployment and success of Peer-to-Peer data management applications is the availability of metadata in a way that makes it easy to access and combine data from different sources and domains.

OLAP servers based on relational backends typically exploit materialized aggregate tables to improve response times of complex analytical queries. One of the key problems in this context is the view selection problem: choosing the optimal set of aggregation tables (called configuration) for a given workload. In this paper, we present a system that continuously monitors the workload and raises a quantified alert, when a better configuration is available. We address the tasks of query monitoring and view selection at the OLAP level instead of the SQL level, which simplifies the containment checks as well as rewriting and in this way helps to reduce the complexity of the backend system. At the demo we plan to show how our system works, i.e., how the system reacts upon arbitrary (interactive) workloads and how the user is alerted that a better configuration is available.

The idea of collecting and combining large public data sets and services became more and more popular. The special characteristics of such systems and the requirements of the participants demand for strictly decentralized solutions. However, this comes along with several ambitious challenges a corresponding system has to overcome. In this demonstration paper, we present a lightweight distributed universal storage capable of dealing with those challenges, and providing a powerful and flexible way of building Internet-scale public data management systems. We introduce our approach based on a triple storage on top of a distributed hash table (DHT) overlay system, based on the ideas of a universal relation model and the resource description framework (RDF), and outline solved challenges as well as open issues.

Peer Data Management Systems (PDMS) are a natural extension of heterogeneous database systems. One of the main tasks in such systems is efficient query processing. Insisting on complete answers, however, leads to asking almost every peer in the network. Relaxing these completeness requirements by applying approximate query answering techniques can significantly reduce costs. Since most users are not interested in the exact answers to their queries, rank-aware query operators like top-k or skyline play an important role in query processing. In this paper, we present the novel concept of relaxed skylines that combines the advantages of both rank-aware query operators and approximate query processing techniques. Furthermore, we propose a strategy for processing relaxed skylines in distributed environments that allows for giving guarantees for the completeness of the result using distributed data summaries as routing indexes.

Evolving from heterogeneous database systems one of the main problems in peer data management systems (PDMS) is distributed query processing. With the absence of global knowledge such strategies have to focus on routing the query efficiently to only those peers that are most likely to contribute to the final result. Using routing indexes is one possibility to achieve this. Since data may change over time these structures have to be updated and maintained which can be very expensive. In this paper, we present a novel kind of routing indexes that enables efficient query routing. Furthermore, we propose a threshold based update strategy that can help to reduce maintenance costs by far. We exemplify the benefit of these indexes using a distributed skyline strategy as an example. Finally, we show how relaxing exactness requirements, that are usually posed on results, can compensate the use of slightly outdated index information

Peer data management systems (PDMS) currently gain attention at an emerging scale in order to cope with the needs of growing organizational integration. Efficient query processing, as one of the main requirements in these systems, provides three major challenges: achieving robustness, scalability and self organization. In this paper we deal with the physical aspects of these requirements. We introduce an adaptive maintenance technique based on query feedback for keeping routing filters, used to optimize routing, up-to-date. These filters are applied in conjunction with an iterative query processing strategy and we show that this can improve robustness and scalability of query processing in distributed data management systems.

The general concept of grouping and aggregation appears to be a fitting paradigm for various issues in data integration, but in its common form of equality-based grouping, a number of problems remain unsolved. We propose a generic approach to user-defined grouping as part of a SQL extension, allowing for more complex functions, for instance integration of data mining algorithms. Furthermore, we discuss high-level language primitives for common applications.

Data annotations are an important kind of metadata that occur in the form of externally assigned descriptions of particular features in Web accessible documents. Such metadata are eventually used in data retrieval tasks on heterogeneous, possible distributed Web-accessible documents. In this paper, we present the model and realization of an annotation framework that scientists can employ to semantically enrich different types of documents, primarily scientific images made available through an image repository. Although we employ ontology like structures, called concepts, for metadata schemes used in annotations, our primary focus is on how concepts are actually used to annotate images and regions of interest, respectively, that exhibit features of interest to a researcher. It turns out that the combined consideration of domain specific concepts and annotated regions in images provides interesting means to analyze the usage of metadata regarding certain correctness and plausibility criteria. We detail our annotation management framework in the context of the Human Brain Project in which Neuroscientists record their observations on specific brain structures, and share and exchange information through concept-based annotations associated with images.

Scalable data mining in large databases is one of today's challenges to database technologies. Thus, substantial effort is dedicated to a tight coupling of database and data mining systems leading to database primitives supporting data mining tasks. In order to support a wide range of tasks and to be of general usage these primitives should be rather building blocks than implementations of specific algorithms. In this paper, we describe primitives for building and applying decision tree classifiers. Based on the analysis of available algorithms and previous work in this area we have identified operations which are useful for a number of classification algorithms. We discuss the implementation of these primitives on top of a commercial DBMS and present experimental results demonstrating the performance benefit.

New applications from the areas of analytical data processing and data integration require powerful features to condense and reconcile available data. As outlined in [1], the general concept of grouping and aggregation appears to be a fitting paradigm for a number of these issues, but in its common form of equality based groups or with current extensions like simple user-defined functions to derive group-by values on a per tuple basis and restricted aggregate functions a number of problems remain unsolved. We describe two extensions to the grouping mechanism, a generic one to support holistic user-defined grouping functions and higher level construct that provides similarity based grouping suitable in a number of applications like duplicate detection and elimination.

Integration and analysis of data from different sources have to deal with several problems resulting from potential heterogeneities. The activities addressing these problems are called data preparation and are supported by various available tools. However, these tools process mostly in a batch-like manner, not supporting the iterative and explorative nature of the integration and analysis process. The authors present a framework for important data preparation tasks based on a multidatabase language. This language offers features for solving common integration and cleaning problems as part of query processing. Combining data preparation mechanisms and multidatabase query facilities permits applying and evaluating different integration and cleaning strategies without explicit loading and materialization of data. The paper introduces the language concepts and discusses their application for individual tasks of data preparation.