Search

Decision support systems that rely on data analytics are used in numerous applications. Their advantages are indisputable, however, they also present risks, possibly having severe impact on people’s lives. Consequently, the need to support ethical or responsible behavior of such systems has recently emerged, putting an emphasis on ensuring fairness, transparency, accountability, etc. This paper presents a novel system framework that offers transparent and personalized services tailored to user profiles to serve their best interest. Our framework personalizes the choice of model for individuals or groups of users based on metadata about data sets and machine learning models. Querying and processing these metadata ensures transparency by supporting various kinds of queries by different stakeholders. We discuss our framework in detail, show why existing solutions are inadequate, and highlight research questions that need to be tackled in the future. Based on a prototypical implementation, we showcase that even a baseline implementation of our framework supports the desired transparency and personalization.

Window aggregation is a core operation in data stream processing. Existing aggregation techniques focus on reducing latency, eliminating redundant computations, and minimizing memory usage. However, each technique operates under different assumptions with respect to workload characteristics such as properties of aggregation functions (e.g., invertible, associative), window types (e.g., sliding, sessions), windowing measures (e.g., time- or count-based), and stream (dis)order. Violating the assumptions of a technique can deem it unusable or drastically reduce its performance. In this paper, we present the first general stream slicing technique for window aggregation. General stream slicing automatically adapts to workload characteristics to improve performance without sacrificing its general applicability. As a prerequisite, we identify workload characteristics which affect the performance and applicability of aggregation techniques. Our experiments show that general stream slicing outperforms alternative concepts by up to one order of magnitude.

This paper demonstrates CURARE, an environment for curating and assisting data scientists to explore raw data collections. CURARE implements a data curation model used to store structural and quantitative metadata semi-automatically extracted. It provides associated functions for exploring these metadata. The demonstration proposed in this paper is devoted to evaluate and compare the effort invested by a data scientist when exploring data collections with and without CURARE assistance.

A relevant task in the exploration and understanding of large datasets is the discovery of hidden relationships in the data. In particular, functional dependencies have received considerable attention in the past. However, there are other kinds of relationships that are significant both for understanding the data and for performing query optimization. Order dependencies belong to this category. An order dependency states that if a table is ordered on a list of attributes, then it is also ordered on another list of attributes. The discovery of order dependencies has been only recently studied. In this paper, we propose a novel approach for discovering order dependencies in a given dataset. Our approach leverages the observation that discovering order dependencies can be guided by the discovery of a more specific form of dependencies called order compatibility dependencies. We show that our algorithm outperforms existing approaches on real datasets. Furthermore, our algorithm can be parallelized leading to further improvements when it is executed on multiple threads. We present several experiments that illustrate the effectiveness and efficiency of our proposal and discuss our findings.

Tools for visual data exploration allow users to visually browse through and analyze datasets to possibly reveal interesting infor- mation hidden in the data that users are a priori unaware of. Such tools rely on both query recommendations to select data to be visualized and visualization recommendations for these data to best support users in their visual data exploration process. EVLIN ( e xploring v isually with lin eage) is a system that assists users in visually exploring relational data stored in a data ware- house. EVLIN implements novel techniques for recommending both queries and their result visualization in an integrated and interactive way [ 3 ]. Recommendations rely on provenance (aka lineage) that describes the production process of displayed data . The demonstration of EVLIN includes an introduction to its features and functionality through sample exploration sessions. Conference attendees will then have the opportunity to gain hands- on experience of provenance-based visual data exploration by performing their own exploration sessions. These sessions will explore real-world data from several domains. While exploration sessions use a Web-based visual interface, the demonstration also features a researcher console, where attendees may have a look behind the scenes to get a more in-depth understanding of the underlying recommendation algorithms. published

National audience; With the increasing amount of available data and transformations manipulating the data, it has become essential to analyze and debug data transformations. A sub-problem of data transformation analysis is to understand why some data are not part of the result of a relational query. One possibility to explain the lack of data in a query result is to identify where in the query data pertinent to the expected, but missing output is lost during query processing. A first approach to this so called why-not provenance has been recently proposed, but we show that this first approach has some shortcomings. To overcome these shortcomings, we propose an algorithm to explain non-existing data in a query result. This algorithm allows to compute the why-not provenance for rela- tional queries involving selection, projection, join and union. After providing necessary definitions, this paper contributes a detailed description of the algorithm. A comparative evaluation shows that it is both more efficient and effective than the state-of-the-art ap- proach.

International audience; The European Union has created the European Institute of Technology (EIT), within which ICT Labs focuses on fostering exchange and new result creation in the sphere of Information and Communication Technology, across the areas of research, higher education, and industrial innovation. ''Digital Cities of the Future'' is an action line (or chapter) of EIT ICT Labs. Within this action line, we coordinated an activity called ''DataBridges: Data Integration for Digital cities'', whose aim is to produce, link, integrate and exploit open data in the Digital Cities data space, for the benefit of both citizens and administrations. In that context, DataBridges addresses many research challenges such as acquiring (or producing) Open City Data in RDF, data linking and integration, data provenance, and visualization. This position paper describes our efforts within DataBridges to integrate City Data. We provide a brief introduction to EIT ICT Labs, its goals and structures, and how DataBridges fits them. We then detail the activity and some selected results from 2011 - 2012, and plans for 2013. We conclude with some research challenges we plan to adress in the future.

Duplicate detection consists in determining different representations of real-world objects in a database. Recent research has considered the use of relationships among object representations to improve duplicate detection. In the general case where relationships form a graph, research has mainly focused on duplicate detection quality/effectiveness. Scalability has been neglected so far, even though it is crucial for large real-world duplicate detection tasks. In this paper we scale up duplicate detection in graph data (DDG) to large amounts of data and pairwise comparisons, using the support of a relational database system. To this end, we first generalize the process of DDG. We then present how to scale algorithms for DDG in space (amount of data processed with limited main memory) and in time. Finally, we explore how complex similarity computation can be performed efficiently. Experiments on data an order of magnitude larger than data considered so far in DDG clearly show that our methods scale to large amounts of data not residing in main memory.

Debugging analytical queries in big data analytics systems, such as Apache Spark, Flink, or Hive is a tedious process, especially when large datasets with nested data are involved. To ease this debugging process, we present novel approaches to obtain explanations for existing and missing data in the query result based on a formal data and execution model that faithfully captures the execution semantics of big data analytics systems to provide practically meaningful explanations. These explanations describe why data are present or absent from the result. Our first contribution is a novel, distributed, and scalable algorithm that matches tree-patterns on nested data in big data analytics systems. It enables us to precisely address and query nested data values and arbitrary combinations of them. We leverage this tree-pattern matching algorithm to request explanations for queries over large, nested data. The algorithm matches the pattern onto the data in two steps. It computes matches on the schema in the first step and applies these matches on the data values in a second step. Hence, it avoids complex global state that prevents other state-of-the-art algorithms to scale horizontally on large compute clusters and dataset sizes. In addition to the tree-pattern matching algorithm, we leverage provenance to find the explanations. Provenance describes the origins and derivation of the result data. To provide explanations for existing data, we introduce the novel structural provenance. It traces structural manipulations in addition to data dependencies through the query pipelines. It provides more comprehensive explanations than other existing approaches since it distinguishes between accessed and manipulated data at the granaluratity of individual nested attributes. We define formal capture rules for the structural provenance that extend our execution model. Capturing the strucural provenance according to these rules imposes a high runtime overhead. Thus, we contribute the Pebble algorithm that implements an optimized, lightweight structural provenance to scale to large, nested datasets. Pebble’s explanations enable novel use-cases beyond debugging, such as finding data-usage patterns or fine-grained auditing. Furthermore, we contribute a novel approach to query-based explanations for missing data in a query result. Query-based explanations pinpoint operators in the query that prevent expected data from appearing in the result. This data is called missing data or missing answer. Our approach is the first to support nested data and to consider operators that modify the schema and structure of the data such as the nesting or projection operator as potential causes of missing answers. Additionally, it accounts for mistakenly referenced attributes in the query. Hence, our explanations apply to a wider range of datasets and to novel error scenarios compared to existing, provenance-based solutions. Our approach extends these solutions with reparameterizations. Reparameterizations describe parameter modifications in query operators. We formally introduce them based on our execution model and derive a formal definition of our query-based explanations. To efficiently compute the explanations over large, nested datasets, we propose a novel heuristic algorithm, called Breadcrumb. It applies two unique techniques: (i) It reasons about multiple schema alternatives to account for the mistakenly referenced attributes and (ii) it re-validates each intermediate result to check whether its data can contribute to the missing answer. That is necessary to provide correct explanations for nested data. We implement the tree-pattern matching algorithm, Pebble, and Breadcrumb in Apache Spark to show that each algorithm scales with increasing dataset sizes. Therefore, we run the algorithms on at least two nested real-world workloads of up to 500GB. We illustrate that tree-patterns simplify the query pipelines and show that Pebble and Breadcrumb provide more comprehensive explanations than other state-of-the-art solutions which enable novel use-cases.

A key service in vehicular transportation is routing according to estimated travel times. With the availability of massive volumes of vehicle trajectory data, it has become increasingly feasible to estimate travel times, which are typically modeled as probability distributions in the form of histograms. An earlier study shows that use of a carefully selected, context-dependent subset of available trajectories when estimating a travel-time histogram along a user-specified path can significantly improve the accuracy of the estimates. This selection of trajectories cannot occur in a pre-processing step, but must occur online—it must be integrated into the routing itself. It is then a key challenge to be able to select very efficiently the "right" subset of trajectories that offer the best accuracy when the cost of a route is to be assessed. To address this challenge, we propose a solution that applies novel indexing to all available trajectories and that then is capable of selecting the most relevant trajectories and of computing a travel-time distribution based on these trajectories. Specifically, the solution utilizes an in-memory trajectory index and a greedy algorithm to identify and retrieve the relevant trajectories. The paper reports on an extensive empirical study with a large real-world GPS data set that offers insight into the accuracy and efficiency of the proposed solution. The study shows that the proposed online selection of trajectories can be performed efficiently and is able to provide highly accurate travel-time distributions.

Format transformation is one of the most labor intensive tasks of a data wrangling process. Recent advances in programming by example proposed synthesis algorithms that showed promising results on spreadsheet data. However, when employed on repositories consisting of multiple sources and large number of examples, such algorithms manifest scalability issues. This paper introduces a new transformation synthesis technique based on edit operations that enables efficient learning of transformation programs. Empirical results show comparable effectiveness and dramatic improvements in efficiency over the state-of-the art.

Entity Resolution (ER) aims to identify different descriptions in various Knowledge Bases (KBs) that refer to the same entity. ER is challenged by the Variety, Volume and Veracity of entity descriptions published in the Web of Data. To address them, we propose the MinoanER framework that simultaneously fulfills full automation, support of highly heterogeneous entities, and massive parallelization of the ER process. MinoanER leverages a token-based similarity of entities to define a new metric that derives the similarity of neighboring entities from the most important relations, as they are indicated only by statistics. A composite blocking method is employed to capture different sources of matching evidence from the content, neighbors, or names of entities. The search space of candidate pairs for comparison is compactly abstracted by a novel disjunctive blocking graph and processed by a non-iterative, massively parallel matching algorithm that consists of four generic, schema-agnostic matching rules that are quite robust with respect to their internal configuration. We demonstrate that the effectiveness of MinoanER is comparable to existing ER tools over real KBs exhibiting low Variety, but it outperforms them significantly when matching KBs with high Variety., Comment: Presented at EDBT 20019

Vast amounts of data are being generated daily with the adoption of Internet-of-Things (IoT) solutions in an ever-increasing number of application domains. There are problems associated with all stages of the lifecycle of these data (e.g., capture, curation and preservation). Moreover, the volume, variety, dynamicity and ubiquity of IoT data present additional challenges to their usability, prompting the need for constructing scalable data-intensive IoT data management and processing platforms. This paper presents a novel approach to model and build IoT data platforms based on the characteristics of an Actor-Oriented Database (AODB). We take advantage of two complementary case studies – in structural health monitoring and beef cattle tracking and tracing – to describe novel software requirements introduced by IoT data processing. Our investigation illustrates the challenges and benefits provided by AODB to meet these requirements in terms of modeling and IoT-based systems implementation. Obtained results reveal the advantages of using AODB in IoT scenarios and lead to principles on how to effectively use an actor model to design and implement IoT data platforms.

Lecture Notes in Informatics, P-265, Datenbanksysteme für Business, Technologie und Web (BTW 2017), ISBN:978-3-88579-659-6

International audience; In analyzing and debugging data transformations, or more specifically relational queries, a subproblem is to understand why some data are not part of the query result. This problem has recently been addressed from different perspectives for various fragments of relational queries. The different perspectives yield different, yet complementary explanations of such missing-answers. This paper first aims at unifying the different approaches by defining a new type of explanation, called hybrid explanation, that encompasses the variety of previously defined types of explanations. This solution goes beyond simply forming the union of explanations produced by different algorithms and is shown to be able to explain a larger set of missing-answers. Second, we present Conseil, an algorithm to generate hybrid explanations. Conseil is also the first algorithm to handle non-monotonic queries. Experiments on efficiency and explanation quality show that Conseil is comparable to and even outperforms previous algorithms.

International audience; Duplicate detection determines different representations of real-world objects in a database. Recent research has considered the use of relationships among object representations to improve duplicate detection. In the general case where relationships form a graph, research has mainly focused on duplicate detection quality/effectiveness. Scalability has been neglected so far, even though it is crucial for large real-world duplicate detection tasks. We scale-up duplicate detection in graph data (ddg) to large amounts of data and pairwise comparisons, using the support of a relational database management system. To this end, we first present a framework that generalizes the ddg process. We then present algorithms to scale ddg in space (amount of data processed with bounded main memory) and in time. Finally, we extend our framework to allow batched and parallel ddg, thus further improving efficiency. Experiments on data of up to two orders of magnitude larger than data considered so far in ddg show that our methods achieve the goal of scaling ddg to large volumes of data.