uk: Комп'ютерні науки

description: Accelerating machine learning (ML) over relational data is a key focus of the database community. While many real-world datasets are multi-table, most ML tools expect single-table inputs, forcing users to materialize joins before ML, leading to data redundancy and runtime waste. Recent works on 'factorized ML' address such issues by pushing ML through joins. However, they have hitherto been restricted to ML models linear in the feature space, rendering them less effective when users construct non-linear feature interactions such as pairwise products to boost ML accuracy. In this work, we take a first step towards closing this gap by introducing a new abstraction to enable pairwise feature interactions in multi-table data and present an extensive framework of algebraic rewrite rules for factorized LA operators over feature interactions. Our rewrite rules carefully exploit the interplay of the redundancy caused by both joins and interactions. We prototype our framework in Python to build a tool we call MorpheusFI. An extensive empirical evaluation with both synthetic and real datasets shows that MorpheusFI yields up to 5x speedups over materialized execution for a popular second-order gradient method and even an order of magnitude speedups over a popular stochastic gradient method.

uk: вхід без авторизації

name: Enabling and Optimizing Non-linear Feature Interactions in Factorized Linear Algebra


The Responsibility Challenge for Data

H. V. Jagadish

type: Person

cs: Informatika

de: Informatik

fi: tietojenkäsittelytiede

uk: Комп'ютерні науки

en: Computer Science

fr: Informatique

da: Datalogi

es: Ciencias de la Computación

nl: Informatica

cs: Technické vědy

de: Ingenieurwissenschaften

fi: tekniikka

uk: Інженерія

en: Engineering Sciences

fr: Ingénierie

da: Ingeniørvidenskab

es: Ingeniería

nl: Engineering

description: As data science and artificial intelligence become ubiquitous, they have an increasing impact on society. While many of these impacts are beneficial, others may not be. So understanding and managing these impacts is required of every responsible data scientist. Nevertheless, most human decision-makers use algorithms for efficiency purposes and not to make a better (i.e., fairer) decisions. Even the task of risk assessment in the criminal justice system enables efficiency instead of (and often at the expense of) fairness. So we need to frame the problem with fairness, and other societal impacts, as primary objectives. In this context, most attention has been paid to the machine learning of a model for a task, such as recognition, prediction, or classification. However, issues arise in all parts of the data eco-system, from data acquisition to data presentation. For example, the majority of the population is not white and male, yet this demographic is over-represented in the training data. It is challenging for a data scientist to satisfactorily discharge this broad responsibility.

TIB AV-Portal

type: Service

type: WebContent

type: MediaObject

@language: en

cs: přihlášení není vyžadováno

de: keine Anmeldung erforderlich

uk: вхід без авторизації

en: no login required

nl: geen login vereist

ACM SIGMOD

type: Organization

cs: Video

de: Video

fi: Video

uk: Відео

en: Video

fr: Vidéo

da: Video

nl: Video

es: Video


uk: Комп'ютерні науки

description: We introduce a few-shot learning framework for error detection. We show that data augmentation (a form of weak supervision) is key to training high-quality, ML-based error detection models that require minimal human involvement. Our framework consists of two parts: (1) an expressive model to learn rich representations that capture the inherent syntactic and semantic heterogeneity of errors; and (2) a data augmentation model that, given a small seed of clean records, uses dataset-specific transformations to automatically generate additional training data. Our key insight is to learn data augmentation policies from the noisy input dataset in a weakly supervised manner. We show that our framework detects errors with an average precision of ~94% and an average recall of ~93% across a diverse array of datasets that exhibit different types and amounts of errors. We compare our approach to a comprehensive collection of error detection methods, ranging from traditional rule-based methods to ensemble-based and active learning approaches. We show that data augmentation yields an average improvement of 20 F1 points while it requires access to 3x fewer labeled examples compared to other ML approaches.

uk: вхід без авторизації

name: HoloDetect: Few-Shot Learning for Error Detection


uk: Комп'ютерні науки

description: Data compression is a popular technique for improving the efficiency of data processing workloads such as SQL queries and more recently, machine learning (ML) with classical batch gradient methods. But the efficacy of such ideas for mini-batch stochastic gradient descent (MGD), arguably the workhorse algorithm of modern ML, is an open question. MGD's unique data access pattern renders prior art, including those designed for batch gradient methods, less effective. We fill this crucial research gap by proposing a new lossless compression scheme we call tuple-oriented compression (TOC) that is inspired by an unlikely source, the string/ text compression scheme Lempel-Ziv-Welch, but tailored to MGD in a way that preserves tuple boundaries within mini-batches. We then present a suite of novel compressed matrix operation execution techniques tailored to the TOC compression scheme that operate directly over the compressed data representation and avoid decompression overheads. An extensive empirical evaluation with real-world datasets shows that TOC consistently achieves substantial compression ratios by up to 51x and reduces runtimes for MGD workloads by up to 10.2x in popular ML systems.

uk: вхід без авторизації

name: Tuple-oriented Compression for Large-scale Mini-batch Stochastic Gradient Descent


uk: Комп'ютерні науки

description: Index structures are one of the most important tools that DBAs leverage to improve the performance of analytics and transactional workloads. However, building several indexes over large datasets can often become prohibitive and consume valuable system resources. In fact, a recent study showed that indexes created as part of the TPC-C benchmark can account for 55% of the total memory available in a modern DBMS. This overhead consumes valuable and expensive main memory, and limits the amount of space available to store new data or process existing data. In this paper, we present a novel data-aware index structure called FITing-Tree which approximates an index using piece-wise linear functions with a bounded error specified at construction time. This error knob provides a tunable parameter that allows a DBA to FIT an index to a dataset and workload by being able to balance lookup performance and space consumption. To navigate this tradeoff, we provide a cost model that helps determine an appropriate error parameter given either (1) a lookup latency requirement (e.g., 500ns) or (2) a storage budget (e.g., 100MB). Using a variety of real-world datasets, we show that our index is able to provide performance that is comparable to full index structures while reducing the storage footprint by orders of magnitude.

uk: вхід без авторизації

name: FITing-Tree: A Data-aware Index Structure


uk: Комп'ютерні науки

description: Indexes are essential in data management systems to increase the speed of data retrievals. Widespread data structures to provide fast and memory-efficient indexes are prefix tries. Implementations like Judy, ART, or HOT optimize their internal alignments for cache and vector unit efficiency. While these measures usually improve the performance substantially, they can have a negative impact on memory efficiency. In this paper we present Hyperion, a trie-based main-memory key-value store achieving extreme space efficiency. In contrast to other data structures, Hyperion does not depend on CPU vector units, but scans the data structure linearly. Combined with a custom memory allocator, Hyperion accomplishes a remarkable data density while achieving a competitive point query and an exceptional range query performance. Hyperion can significantly reduce the index memory footprint and its performance-to-memory ratio is more than two times better than the best implemented alternative strategy for randomized string data sets.

uk: вхід без авторизації

name: Hyperion: Building the Largest In-memory Search Tree


uk: Комп'ютерні науки

description: Programs for extracting structured information from text, namely information extractors, often operate separately on document segments obtained from a generic splitting operation such as sentences, paragraphs, k-grams, HTTP requests, and so on. An automated detection of this behavior of extractors, which we refer to as split-correctness, would allow text analysis systems to devise query plans with parallel evaluation on segments for accelerating the processing of large documents. Other applications include the incremental evaluation on dynamic content, where re-evaluation of information extractors can be restricted to revised segments, and debugging, where developers of information extractors are informed about potential boundary crossing of different semantic components. We propose a new formal framework for split-correctness within the formalism of document spanners. Our preliminary analysis studies the complexity of split-correctness over regular spanners. We also discuss different variants of split-correctness, for instance, in the presence of black-box extractors with split constraints.

uk: вхід без авторизації

name: Split-Correctness in Information Extraction


uk: Комп'ютерні науки

description: There has been a recent flurry of interest in providing query capability on raw data in today's big data systems. These raw data must be parsed before processing or use in analytics. Thus, a fundamental challenge in distributed big data systems is that of efficient parallel parsing of raw data. The difficulties come from the inherent ambiguity while independently parsing chunks of raw data without knowing the context of these chunks. Specifically, it can be difficult to find the beginnings and ends of fields and records in these chunks of raw data. To parallelize parsing, this paper proposes a speculation-based approach for the CSV format, arguably the most commonly used raw data format. Due to the syntactic and statistical properties of the format, speculative parsing rarely fails and therefore parsing is efficiently parallelized in a distributed setting. Our speculative approach is also robust, meaning that it can reliably detect syntax errors in CSV data. We experimentally evaluate the speculative, distributed parsing approach in Apache Spark using more than 11,000 real-world datasets, and show that our parser produces significant performance benefits over existing methods.

uk: вхід без авторизації

name: Speculative Distributed CSV Data Parsing for Big Data Analytics


uk: Комп'ютерні науки

description: In this article we review the main concepts around database repairs and consistent query answering, with emphasis on tracing back the origin, motivation, and early developments. We also describe some research directions that has spun from those main concepts and the original line of research. We emphasize, in particular, fruitful and recent connections between repairs and causality in databases.

uk: вхід без авторизації

name: Database Repairs and Consistent Query Answering: Origins and Further Developments


uk: Комп'ютерні науки

description: As data-size is increasing exponentially, new paradigm shifts have to emerge allowing fast exploitation of data by every- body. Large-scale predictive analytics is restricted to wealthy organizations as small-scale enterprises (SMEs) struggle to compete and are inundated by the sheer monetary cost of either procuring data infrastructures or analyzing datasets over the Cloud. The aim of this work is to study mechanisms which can democratize analytics, in the sense of making them affordable, while at the same time ensuring high efficiency, scalability, and accuracy. The crux of this proposal lies in developing query-driven solutions that can be used off the Cloud thus minimizing costs. Our query-driven approach will learn and adapt on-the-fly machine learning models, based solely on query-answer interactions, which can be used for answering analytical queries. In this abstract we describe the methodology followed for the implementation and evaluation of the system designed.

uk: вхід без авторизації

name: Query-Driven Learning for Next Generation Predictive Modeling and Analytics


uk: Комп'ютерні науки

description: In the late 1990s, the possibility of algorithmic extraction of insight from soulless data loomed potentially important and very intriguing. I will look back at our attempt at understanding and advancing this research program in the light of two decades of blistering progress in spectral methods, machine learning, data harvesting and deep nets.

uk: вхід без авторизації

name: Remembering the Probabilistic Analysis of Latent Semantic Indexing


uk: Комп'ютерні науки

description: Consistent query answering (CQA) aims to deliver meaningful answers when queries are evaluated over inconsistent databases. Such answers must be certainly true in all repairs, which are consistent databases whose difference from the inconsistent one is somehow minimal. An interesting task in this context is to count the number of repairs that entail the query. This problem has been already studied for conjunctive queries and primary keys; we know that it is #P-complete in data complexity under polynomial-time Turing reductions (a.k.a. Cook reductions). However, as it has been already observed in the literature of counting complexity, there are problems that are 'hard-to-count-easy-to-decide', which cannot be complete (under reasonable assumptions) for #P under weaker reductions, and, in particular, under standard many-one logspace reductions (a.k.a. parsimonious reductions). For such 'hard-to-count-easy-to-decide' problems, a crucial question is whether we can determine their exact complexity by looking for subclasses of #P to which they belong. Ideally, we would like to show that such a problem is complete for a subclass of #P under many-one logspace reductions. The main goal of this work is to perform such a refined analysis for the problem of counting the number of repairs under primary keys that entail the query.

uk: вхід без авторизації

name: Counting Database Repairs under Primary Keys Revisited


uk: Комп'ютерні науки

description: Dr Robert (Xiaobin) Shen from Astronomy Australia. (1.6.18) In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards).

uk: вхід без авторизації

name: Astro DEVL #1: ASVO - MWA Node - June 18

Australian Research Data Commons (ARDC)

addressCountry: AU

addressLocality: Melbourne

addressRegion: Victoria


uk: Комп'ютерні науки

description: 06.07.18 - Jeff Christiansen, Bioscience DEVL (Data enhanced Virtual Lab). In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards). DEVL #2 July (6th), we welcome speakers from: GeoScience (Carsten Friedrich), Characterisation (Lance Wilson), BioScience (Jeff Christiansen), and Culture and Communities (Sarah Nisbet, Alexis Tindall).

uk: вхід без авторизації

name: [Molecular] Bioscience DEVL + RDC Projects #2 - July 18


uk: Комп'ютерні науки

description: 06.07.18 - Lance Wilson Characterisation DEVL (Data enhanced Virtual Lab). In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards). DEVL #2 July (6th), we welcome speakers from: GeoScience (Carsten Friedrich), Characterisation (Lance Wilson), BioScience (Jeff Christiansen), and Culture and Communities (Sarah Nisbet, Alexis Tindall).

uk: вхід без авторизації

name: Technology of the Characterisation Virtual Laboratory (C-DEVL project) #2 - July 18


uk: Комп'ютерні науки

description: Clare Richards from Climate DEVL. (1.6.18) Senior HPC Innovation Manager, NCI In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards).

uk: вхід без авторизації

name: Climate Science Data Enhanced Virtual Laboratory #1 - June 18


uk: Комп'ютерні науки

description: Gerhard Weis from Eco DEVL. (1.6.18) In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards).

uk: вхід без авторизації

name: EcoCloud DEVL #1 - EcoScience Research Data Cloud & Data Enhanced Virtual Laboratory (RDC & DEVL) - June 18


uk: Комп'ютерні науки

description: 06.07.18 - Carsten Friedrich, Geoscience DEVL (Data enhanced Virtual Lab). In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards). DEVL #2 July (6th), we welcome speakers from: GeoScience (Carsten Friedrich), Characterisation (Lance Wilson), BioScience (Jeff Christiansen), and Culture and Communities (Sarah Nisbet, Alexis Tindall).

uk: вхід без авторизації

name: Geoscience DEVL #2 - GeoDEVL - July 18: Data and Analytic Services for the Geoscience community


uk: Комп'ютерні науки

description: 06.07.18 - Alexis Tindall, Sarah Nisbett ERSA on Humanities and Social Sciences (HASS) DEVL (Data enhanced Virtual Lab). In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards). DEVL #2 July (6th), we welcome speakers from: GeoScience (Carsten Friedrich), Characterisation (Lance Wilson), BioScience (Jeff Christiansen), and Culture and Communities (Sarah Nisbet, Alexis Tindall).

uk: вхід без авторизації

name: Humanities, Arts and Social Sciences DEVL #2 - July 18: Data Enhanced Virtual Lab


uk: Комп'ютерні науки

description: Roger Proctor from Australian Ocean Data Network, Uni of Tasmania (1.6.18) In June & July's TechTalk events, representatives from each of the DEVLs will introduce their projects from a developers' perspective: the problem the project is trying to solve, the tech stacks deployed and to be developed, the approaches of their software development and community engagement while developing tools and applications. The demonstration/discussion of 8 projects are scheduled as follows: DEVL #1 June (1st): Astronomy (Robert Shen), Marine Science (Roger Proctor), Terrestrial Ecology (Gerhard Weis), and Climate (Clare Richards).

uk: вхід без авторизації

name: Marine Data enhanced Virtual Laboratory DEVL #1 - June 18: information infrastructure in support of the national ocean modelling system


uk: Комп'ютерні науки

description: The ESIP Information Quality Cluster (IQC) has been active since 2014 covering a broad spectrum of topics related to information quality in Earth sciences. The cluster’s vision is to “become internationally recognized as an authoritative and responsive information resource for guiding the implementation of data quality standards and best practices of the science data systems, datasets, and data/metadata dissemination services.” The IQC considers four aspects of quality – Data Quality, Product Quality, Stewardship Quality and Service Quality.

uk: вхід без авторизації

name: ESIP Information Quality Cluster - A Brief Overview of Maturity Models for Consistemt Data Quality Ratings - March 2019


uk: Комп'ютерні науки

uk: вхід без авторизації

name: Australia National Computational Infrastructure - Implementing a Data Quality Strategy to simplify access to data - March 2019


uk: Комп'ютерні науки

uk: вхід без авторизації

name: ESIP Information Quality Cluster: Vision, Objectives, Accomplishments and Status - March 2019


uk: Комп'ютерні науки

description: Topic - Cart before the horse: system QA and data QC practices for sensor networks The ESIP EnviroSensing Cluster is a workgroup within the Earth Science Information Partners Federation. The cluster was formed in 2012 as a community of mostly NSF-LTER network and data managers. 2.The Earthcube CHORDS project Speaker: Mike Daniels, Principal Investigator and Project Manager at NCAR - The National Center for Atmospheric Research

uk: вхід без авторизації

name: ESIP EnviroSensing Cluster Pt. 3 - Cloud-Hosted Real-time Data Services for the Geosciences (CHORDS) - Nov 18: Standardized real-time data services being applied across a range of geosciences instrumentation


uk: Комп'ютерні науки

description: Topic - Cart before the horse: system QA and data QC practices for sensor networks The ESIP EnviroSensing Cluster is a workgroup within the Earth Science Information Partners Federation. The cluster was formed in 2012 as a community of mostly NSF-LTER network and data managers. 4.Highlight: SENSAQ startup Speaker: Dr. Paul Celicourt, Co-Founder and Inventor/Applied Research Scientist at SENSAQ

uk: вхід без авторизації

name: ESIP EnviroSensing Cluster Pt. 4 - An Integrated Sensor Data Management System (ISDMS) - Nov 18


uk: Комп'ютерні науки

description: The ESIP EnviroSensing Cluster is a workgroup within the Earth Science Information Partners Federation. The cluster was formed in 2012 as a community of mostly NSF-LTER network and data managers. 1.Introduction to the ESIP EnviroSensing Cluster Speaker: Dr. Scotty Strachan, Director of Nevada Climate-ecohydrological Assessment Network (NevCAN)

uk: вхід без авторизації

name: ESIP EnviroSensing Cluster Pt. 1 - Cart before the horse: system QA and data QC practices for sensor networks - Nov 18


uk: Комп'ютерні науки

description: Topic - Cart before the horse: system QA and data QC practices for sensor networks The ESIP EnviroSensing Cluster is a workgroup within the Earth Science Information Partners Federation. The cluster was formed in 2012 as a community of mostly NSF-LTER network and data managers. 5.QA for Mountain Observatories Speaker: Dr. Scotty Strachan, NevCAN

uk: вхід без авторизації

name: ESIP EnviroSensing Cluster Pt. 2 - Cluster Projects & Highlights - Nov 18


uk: Комп'ютерні науки

description: Processing Structured Scientific Data in Cloud The HDF5 file format has been used extensively in the HPC community for the storage of scientific data (e.g. multi-dimensional arrays). Unfortunately, the traditional HDF5 library doesn't work so well for applications running in the cloud. To address this, we've developed a service based implementation of HDF5, HDF Kita. Kita utilizes object based storage (e.g. AWS S3) and runs as a cluster of Docker Containers. In combination with the service, JupyterHub enables users to easily run notebooks in the cloud that can use an unlimited amount of data and take advantage of the parallelization capabilities of the Kita Server.

uk: вхід без авторизації

name: Scientific Data in the Cloud - Oct 18: HDF5 in the Cloud


uk: Комп'ютерні науки

description: Processing Structured Scientific Data in the Cloud Nigel Rees, Research Data Management Specialist at the National Computational Infrastructure (NCI) The Network Common Data Form (NetCDF) software is widely used throughout the world as a mechanism for storing and accessing scientific data. This presentation will introduce what NetCDF is and where NetCDF is applied, show examples from disciplines that actually use NetCDF, and summary pros and cons from examples.

uk: вхід без авторизації

name: Using NetCDF in Jupyter notebooks - Oct 18: Examples from collections at the National Computational Infrastructure (NCI)


The Prosecutions Project - Sept 18

uk: Комп'ютерні науки

description: Mark Finnane, ARC Laureate Fellow Griffith Criminology Institute, Griffith Uni I introduce the multi-jurisdictional, longitudinal criminal prosecutions project in Australia. I emphasise collaborative approaches to the design of research infrastructure, involving researchers, developers & data stakeholders; the value of citizen science to research; and the importance of digital and web technologies in making possible a new era of data-sharing for researchers and non-research communities of interest.

uk: вхід без авторизації


uk: Комп'ютерні науки

description: Computing Digital Humanities - Tim Sherratt, Assoc Prof Digital Heritage, Uni Canberra The GLAM sector (galleries, libraries, archives and museums) is making more and more collection data available online, but how do we use it? In this talk I'll introduce my GLAM data workbench, a new and growing collection of Jupyter notebooks that offer new pathways for historical research. Tim is an historian and hacker who researches the possibilities and politics of digital cultural collections.

uk: вхід без авторизації

name: Exploring GLAM data (with Jupyter notebooks) - Sept 18


uk: Комп'ютерні науки

description: Configuration tuning is vital to optimize the performance of database management system (DBMS). It becomes more tedious and urgent for cloud databases (CDB) due to the diverse database instances and query workloads, which make the database administrator (DBA) incompetent. Although there are some studies on automatic DBMS configuration tuning, they have several limitations. Firstly, they adopt a pipelined learning model but cannot optimize the overall performance in an end-to-end manner. Secondly, they rely on large-scale high-quality training samples which are hard to obtain. Thirdly, there are a large number of knobs that are in continuous space and have unseen dependencies, and they cannot recommend reasonable configurations in such high-dimensional continuous space. Lastly, in cloud environment, they can hardly cope with the changes of hardware configurations and workloads, and have poor adaptability. To address these challenges, we design an end-to-end automatic CDB tuning system, CDBTune, using deep reinforcement learning (RL). CDBTune utilizes the deep deterministic policy gradient method to find the optimal configurations in high-dimensional continuous space. CDBTune adopts a try-and-error strategy to learn knob settings with a limited number of samples to accomplish the initial training, which alleviates the difficulty of collecting massive high-quality samples. CDBTune adopts the reward-feedback mechanism in RL instead of traditional regression, which enables end-to-end learning and accelerates the convergence speed of our model and improves efficiency of online tuning. We conducted extensive experiments under 6 different workloads on real cloud databases to demonstrate the superiority of CDBTune. Experimental results showed that CDBTune had a good adaptability and significantly outperformed the state-of-the-art tuning tools and DBA experts.

uk: вхід без авторизації

name: An End-to-End Automatic Cloud Database Tuning System Using Deep Reinforcement Learning


uk: Комп'ютерні науки

description: In this paper, we focus on the problem of searching sorted, in-memory datasets. This is a key data operation, and Binary Search is the de facto algorithm that is used in practice. We consider an alternative, namely Interpolation Search, which can take advantage of hardware trends by using complex calculations to save memory accesses. Historically, Interpolation Search was found to underperform compared to other search algorithms in this setting, despite its superior asymptotic complexity. Also, Interpolation Search is known to perform poorly on non-uniform data. To address these issues, we introduce SIP (Slope reuse Interpolation), an optimized implementation of Interpolation Search, and TIP (Three point Interpolation), a new search algorithm that uses linear fractions to interpolate on non-uniform distributions. We evaluate these two algorithms against a similarly optimized Binary Search method using a variety of real and synthetic datasets. We show that SIP is up to 4 times faster on uniformly distributed data and TIP is 2-3 times faster on non-uniformly distributed data in some cases. We also design a meta-algorithm to switch between these different methods to automate picking the higher performing search algorithm, which depends on factors like data distribution.

uk: вхід без авторизації

name: Efficiently Searching In-Memory Sorted Arrays: Revenge of the Interpolation Search?


uk: Комп'ютерні науки

description: SkinnerDB is designed from the ground up for reliable join ordering. It maintains no data statistics and uses no cost or cardinality models. Instead, it uses reinforcement learning to learn optimal join orders on the fly, during the execution of the current query. To that purpose, we divide the execution of a query into many small time slices. Different join orders are tried in different time slices. We merge result tuples generated according to different join orders until a complete result is obtained. By measuring execution progress per time slice, we identify promising join orders as execution proceeds. Along with SkinnerDB, we introduce a new quality criterion for query execution strategies. We compare expected execution cost against execution cost for an optimal join order. SkinnerDB features multiple execution strategies that are optimized for that criterion. Some of them can be executed on top of existing database systems. For maximal performance, we introduce a customized execution engine, facilitating fast join order switching via specialized multi-way join algorithms and tuple representations. We experimentally compare SkinnerDB's performance against various baselines, including MonetDB, Postgres, and adaptive processing methods. We consider various benchmarks, including the join order benchmark and TPC-H variants with user-defined functions. Overall, the overheads of reliable join ordering are negligible compared to the performance impact of the occasional, catastrophic join order choice.

uk: вхід без авторизації

name: SkinnerDB: Regret-Bounded Query Evaluation via Reinforcement Learning


uk: Комп'ютерні науки

description: Statistical knowledge and domain expertise are key to extract actionable insights out of data, yet such skills rarely coexist together. In Machine Learning, high-quality results are only attainable via mindful data preprocessing, hyperparameter tuning and model selection. Domain experts are often overwhelmed by such complexity, de-facto inhibiting a wider adoption of ML techniques in other fields. Existing libraries that claim to solve this problem, still require well-trained practitioners. Those frameworks involve heavy data preparation steps and are often too slow for interactive feedback from the user, severely limiting the scope of such systems. In this paper we present Alpine Meadow, a first Interactive Automated Machine Learning tool. What makes our system unique is not only the focus on interactivity, but also the combined systemic and algorithmic design approach; on one hand we leverage ideas from query optimization, on the other we devise novel selection and pruning strategies combining cost-based Multi-Armed Bandits and Bayesian Optimization. We evaluate our system on over 300 datasets and compare against other AutoML tools, including the current NIPS winner, as well as expert solutions. Not only is Alpine Meadow able to significantly outperform the other AutoML systems while - in contrast to the other systems - providing interactive latencies, but also outperforms in 80% of the cases expert solutions over data sets we have never seen before.

uk: вхід без авторизації

name: Democratizing Data Science through Interactive Curation of ML Pipelines


uk: Комп'ютерні науки

description: Transactions can simplify distributed applications by hiding data distribution, concurrency, and failures from the application developer. Ideally the developer would see the abstraction of a single large machine that runs transactions sequentially and never fails. This requires the transactional subsystem to provide opacity (strict serializability for both committed and aborted transactions), as well as transparent fault tolerance with high availability. As even the best abstractions are unlikely to be used if they perform poorly, the system must also provide high performance. Existing distributed transactional designs either weaken this abstraction or are not designed for the best performance within a data center. This paper extends the design of FaRM - which provides strict serializability only for committed transactions - to provide opacity while maintaining FaRM's high throughput, low latency, and high availability within a modern data center. It uses timestamp ordering based on real time with clocks synchronized to within tens of microseconds across a cluster, and a failover protocol to ensure correctness across clock master failures. FaRM with opacity can commit 5.4 million neworder transactions per second when running the TPC-C transaction mix on 90 machines with 3-way replication.

uk: вхід без авторизації

name: Fast General Distributed Transactions with Opacity


uk: Комп'ютерні науки

description: Although deep learning models perform remarkably well across a range of tasks such as language translation and object recognition, it remains unclear what high-level logic, if any, they follow. Understanding this logic may lead to more transparency, better model design, and faster experimentation. Recent machine learning research has leveraged statistical methods to identify hidden units that behave (e.g., activate) similarly to human understandable logic, but those analyses require considerable manual effort. Our insight is that many of those studies follow a common analysis pattern, and therefore there is opportunity to provide a declarative abstraction to easily express, execute and optimize them. This paper describes DeepBase, a system to inspect neural network behaviors through a unified interface. We model logic with user-provided hypothesis functions that annotate the data with high-level labels (e.g., part-of-speech tags, image captions). DeepBase lets users quickly identify individual or groups of units that have strong statistical dependencies with desired hypotheses. We discuss how DeepBase can express existing analyses, propose a set of simple and effective optimizations to speed up a standard Python implementation by up to 72x, and reproduce recent studies from the NLP literature.

uk: вхід без авторизації

name: DeepBase: Deep Inspection of Neural Networks


uk: Комп'ютерні науки

description: Hybrid transactional and analytical processing (HTAP) systems like SAP HANA make it much simpler to manage both operational load and analytical queries without ETL, separate data warehouses, et al. To represent both transactional and analytical business logic in a single database system, stored procedures are often used to express analytical queries using control flow logic and DMLs. Optimizing these complex procedures requires a fair knowledge of imperative programming languages as well as the declarative query language. Therefore, unified optimization techniques considering both program and query optimization techniques are essential for achieving optimal query performance. In this paper, we propose a novel unified optimization technique for efficient iterative query processing. We present a notion of query motion that allows the movement of SQL queries in and out of a loop. Additionally, we exploit a new cost model that measures the quality of the execution plan with consideration for queries and loop iterations. We describe our experimental evaluation that demonstrates the benefit of our technique using both a standard decision support benchmark and real-world workloads. An extensive evaluation shows that our unified optimization technique enumerates plans that achieve performance improvements of up to an order of magnitude faster than plans generated by the existing loop-invariant code motion technique.

uk: вхід без авторизації

name: Iterative Query Processing based on Unified Optimization Techniques


uk: Комп'ютерні науки

description: The rising volume of datasets has made training machine learning (ML) models a major computational cost in the enterprise. Given the iterative nature of model and parameter tuning, many analysts use a small sample of their entire data during their initial stage of analysis to make quick decisions (e.g., what features or hyperparameters to use) and use the entire dataset only in later stages (i.e., when they have converged to a specific model). This sampling, however, is performed in an ad-hoc fashion. Most practitioners cannot precisely capture the effect of sampling on the quality of their model, and eventually on their decision-making process during the tuning phase. Moreover, without systematic support for sampling operators, many optimizations and reuse opportunities are lost. In this paper, we introduce BlinkML, a system for fast, quality-guaranteed ML training. BlinkML allows users to make error-computation tradeoffs: instead of training a model on their full data (i.e., full model), BlinkML can quickly train an approximate model with quality guarantees using a sample. The quality guarantees ensure that, with high probability, the approximate model makes the same predictions as the full model. BlinkML currently supports any ML model that relies on maximum likelihood estimation (MLE), which includes Generalized Linear Models (e.g., linear regression, logistic regression, max entropy classifier, Poisson regression) as well as PPCA (Probabilistic Principal Component Analysis). Our experiments show that BlinkML can speed up the training of large-scale ML tasks by 6.26×–629× while guaranteeing the same predictions, with 95% probability, as the full model.

uk: вхід без авторизації

name: BlinkML: Efficient Maximum Likelihood Estimation with Probabilistic Guarantees


uk: Комп'ютерні науки

description: Thanks to a simple SQL extension, Recursive-aggregate-SQL (RaSQL) can express very powerful queries and declarative algorithms, such as classical graph algorithms and data mining algorithms. A novel compiler implementation allows RaSQL to map declarative queries into one basic fixpoint operator supporting aggregates in recursive queries. A fully optimized implementation of this fixpoint operator leads to superior performance, scalability and portability. Thus, our RaSQL system, which extends Spark SQL with the before-mentioned new constructs and implementation techniques, matches and often surpasses the performance of other systems, including Apache Giraph, GraphX and Myria.

uk: вхід без авторизації

name: RaSQL: Greater Power and Performance for Big Data Analytics with Recursive-aggregate-SQL on Spark


uk: Комп'ютерні науки

description: Data-intensive key-value stores based on the Log-Structured Merge-Tree are used in numerous modern applications ranging from social media and data science to cloud infrastructure. We show that such designs exhibit an intrinsic contention between the costs of point reads, writes and memory, and that this trade-off deteriorates as the data size grows. The root of the problem is that in all existing designs, the capacity ratio between any pair of levels is fixed. This causes write cost to increase with the data size while yielding exponentially diminishing returns for point reads and memory. We introduce the Log-Structured Merge-Bush (LSM-Bush), a new data structure that sets increasing capacity ratios between adjacent pairs of smaller levels. As a result, smaller levels get lazier by gathering more runs before merging them. By using a doubly-exponential ratio growth rate, LSM-bush brings write cost down from O(log N) to O(loglog N), and it can trade this gain to either improve point reads or memory. Thus, it enables more scalable trade-offs all around. We further introduce Wacky, a design continuum that includes LSM-Bush as well as all state-of-the-art merge policies, from laziest to greediest, and can assume any of them within a single implementation. Wacky encompasses a vast space of performance properties, including ones that favor range reads, and it can be searched analytically to find the design that performs best for a given workload in practice.

uk: вхід без авторизації

name: The Log-Structured Merge-Bush & the Wacky Continuum


uk: Комп'ютерні науки

description: Cardinality estimation plays an important role in processing big data. We consider the challenging problem of computing millions or more distinct count aggregations in a single pass and allowing these aggregations to be further combined into coarser aggregations. These arise naturally in many applications including networking, databases, and real-time business reporting. We demonstrate existing approaches to solve this problem are inherently flawed, exhibiting bias that can be arbitrarily large, and propose new methods for solving this problem that have theoretical guarantees of correctness and tight, practical error estimates. This is achieved by carefully combining CountMin and HyperLogLog sketches and a theoretical analysis using statistical estimation techniques. These methods also advance cardinality estimation for individual multisets, as they provide a provably consistent estimator and tight confidence intervals that have exactly the correct asymptotic coverage.

uk: вхід без авторизації

name: Approximate Distinct Counts for Billions of Datasets


Pessimistic Cardinality Estimation

uk: Комп'ютерні науки

description: In this work we introduce a novel approach to the problem of cardinality estimation over multijoin queries. Our approach leveraging randomized hashing and data sketching to tighten these bounds beyond the current state of the art. We demonstrate that the bounds can be injected directly into the cost based query optimizer framework enabling it to avoid expensive physical join plans. We outline our base data structures and methodology, and how these bounds may be introduced to the optimizer's parameterized cost function as a new statistic for physical join plan selection. We demonstrate a complex tradeoff space between the tightness of our bounds and the size and complexity of our data structures. This space is not always monotonic as one might expect. In order combat this non-monotonicity, we introduce a partition budgeting scheme that guarantees monotonic behavior. We evaluate ourmethods on GooglePlus community graphs~citegoogleplus, and the Join Order Benchmark (JOB)~citeLeis:2015:GQO:2850583.2850594. In the presence of foreign key indexes, we demonstrate a 1.7times improvement in aggregate (time summed over all queries in benchmark) physical query plan runtime compared to plans chosen by Postgres using the default cardinality estimation methods. When foreign key indexes are absent, this advantage improves to over 10times.

uk: вхід без авторизації


uk: Комп'ютерні науки

description: The SIGMOD New Researcher Symposium is an informative and entertaining event geared at giving graduate students and junior researchers advice on starting a career in data management, though it often attracts a broader audience. This year's topic is: publication strategies for new researchers. The symposium will discuss issues that span the gamut from questions on how scholarship is evaluated, advice on venue selection, strategies to tolerate randomness in reviewing, and suggestions on how to become a more engaged member of the data management community. The emphasis will be on new researchers ranging from early graduate school to early post-graduation. Our panelists span different career stages, geographical regions, and research styles. Each panelist will give a 10-minute presentation based on their personal experiences and perspectives gained over the years. After the presentations, an informal discussion will ensue based on questions from the audience.

uk: вхід без авторизації

name: SIGMOD New Researcher Symposium (NRS): Publication Strategies for New Researchers: 10 min Talks and Discussion


uk: Комп'ютерні науки

description: Query optimizers often produce sub-optimal query plans due to inaccurate cardinality estimates. The goal of exact cardinality query optimization (ECQO) is to produce optimal plans based on guaranteed exact cardinality values, obtained via probe executions. We propose a novel algorithm for ECQO. It improves over prior work by limiting the overheads of probe executions. Instead of fully generating each relation in the optimizer's plan space, it calculates cardinality bounds based on partially generated relations. Thereby, it is often able to prune relations early if they are too large to participate in any optimal plan. Our algorithm exploits dependencies between relations to propagate exclusions, it selects probing targets for maximum information gain, and it caps probing overheads by conservative bounds on execution cost. Those bounds are iteratively increased once lower bounds on optimal query execution cost have been established. The algorithm is non-intrusive and can be used on top of any database management system supporting SQL limit clauses. We formally prove that probing costs are bounded as a function of the optimal execution cost and evaluate our algorithm experimentally. Our algorithm is in average six times and up to 69 times faster than a state-of-the-art baseline for ECQO on the recently proposed join order benchmark.

uk: вхід без авторизації

name: Exact Cardinality Query Optimization with Bounded Execution Cost


RRR: Rank-Regret Representative

uk: Комп'ютерні науки

description: Selecting the best items in a dataset is a common task in data exploration. However, the concept of 'best' lies in the eyes of the beholder: different users may consider different attributes more important, and hence arrive at different rankings. Nevertheless, one can remove 'dominated' items and create a 'representative' subset of the data, comprising the 'best items' in it. A Pareto-optimal representative is guaranteed to contain the best item of each possible ranking, but it can be a large portion of data. A much smaller representative can be found if we relax the requirement to include the best item for each user, and instead just limit the users' 'regret'. Existing work defines regret as the loss in score by limiting consideration to the representative instead of the full data set, for any chosen ranking function. However, the score is often not a meaningful number and users may not understand its absolute value. Sometimes small ranges in score can include large fractions of the data set. In contrast, users do understand the notion of rank ordering. Therefore, we consider the position of the items in the ranked list for defining the regret and propose the rank-regret representative as the minimal subset of the data containing at least one of the top-k of any possible ranking function. This problem is NP-complete. We use a geometric interpretation of items to bound their ranks on ranges of functions and to utilize combinatorial geometry notions for developing effective and efficient approximation algorithms for the problem. Experiments on real datasets demonstrate that we can efficiently find small subsets with small rank-regrets.

uk: вхід без авторизації


uk: Комп'ютерні науки

description: This paper introduces LMFAO (Layered Multiple Functional Aggregate Optimization), an in-memory optimization and execution engine for batches of aggregates over the input database. The primary motivation for this work stems from the observation that for a variety of analytics over databases, their data-intensive tasks can be decomposed into group-by aggregates over the join of the input database relations. We exemplify the versatility and competitiveness of LMFAO for a handful of widely used analytics: learning ridge linear regression, classification trees, regression trees, and the structure of Bayesian networks using Chow-Liu trees; and data cubes used for exploration in data warehousing. LMFAO consists of several layers of logical and code optimizations that systematically exploit sharing of computation, parallelism, and code specialization. We conducted two types of performance benchmarks. In experiments with four datasets, LMFAO outperforms by several orders of magnitude on one hand, a commercial database system and MonetDB for computing batches of aggregates, and on the other hand, TensorFlow, Scikit, R, and AC/DC for learning a variety of models over databases.

uk: вхід без авторизації

name: A Layered Aggregate Engine for Analytics Workloads


uk: Комп'ютерні науки

description: Physical and digital documents often contain visually rich information. With such information, there is no strict ordering or positioning in the document where the data values must appear. Along with textual cues, these documents often also rely on salient visual features to define distinct semantic boundaries and augment the information they disseminate. When performing information extraction (IE), traditional techniques fall short, as they use a text-only representation and do not consider the visual cues inherent to the layout of these documents. We propose VS2, a generalized approach for information extraction from heterogeneous visually rich documents. There are two major contributions of this work. First, we propose a robust segmentation algorithm that decomposes a visually rich document into a bag of visually isolated but semantically coherent areas, called logical blocks. Document type agnostic low-level visual and semantic features are used in this process. Our second contribution is a distantly supervised search-and-select method for identifying the named entities within these documents by utilizing the context boundaries defined by these logical blocks. Experimental results on three heterogeneous datasets suggest that the proposed approach significantly outperforms its text-only counterparts on all datasets. Comparing it against the state-of-the-art methods also reveal that VS2 performs comparably or better on all datasets.

uk: вхід без авторизації

name: Visual Segmentation for Information Extraction from Heterogeneous Visually Rich Documents


uk: Комп'ютерні науки

description: Streaming applications from cluster monitoring to algorithmic trading deploy Kleene queries to detect and aggregate event trends. Rich event matching semantics determine how to compose events into trends. The expressive power of state-of-the-art streaming systems remains limited since they do not support many of these semantics. Worse yet, they suffer from long delays and high memory costs because they maintain aggregates at a fine granularity. To overcome these limitations, our Coarse-Grained Event Trend Aggregation (Cogra) approach supports a rich variety of event matching semantics within one system. Better yet, Cogra incrementally maintains aggregates at the coarsest granularity possible for each of these semantics. In this way, Cogra minimizes the number of aggregates -- reducing both time and space complexity. Our experiments demonstrate that Cogra achieves up to six orders of magnitude speed-up and up to seven orders of magnitude memory reduction compared to state-of-the-art approaches.

uk: вхід без авторизації

name: Event Trend Aggregation Under Rich Event Matching Semantics


Top-k Queries over Digital Traces

uk: Комп'ютерні науки

description: Recent advances in social and mobile technology have enabled an abundance of digital traces (in the form of mobile check-ins, association of mobile devices to specific WiFi hotspots, etc.) revealing the physical presence history of diverse sets of entities (e.g., humans, devices, and vehicles). One challenging yet important task is to identify k entities that are most closely associated with a given query entity based on their digital traces. We propose a suite of indexing techniques and algorithms to enable fast query processing for this problem at scale. We first define a generic family of functions measuring the association between entities, and then propose algorithms to transform digital traces into a lower-dimensional space for more efficient computation. We subsequently design a hierarchical indexing structure to organize entities in a way that closely associated entities tend to appear together. We then develop algorithms to process top-k queries utilizing the index. We theoretically analyze the pruning effectiveness of the proposed methods based on a mobility model which we propose and validate in real life situations. Finally, we conduct extensive experiments on both synthetic and real datasets at scale, evaluating the performance of our techniques both analytically and experimentally, confirming the effectiveness and superiority of our approach over other applicable approaches across a variety of parameter settings and datasets.

uk: вхід без авторизації


uk: Комп'ютерні науки

description: Rapid advances in data-driven applications over recent years have intensified the need for efficient mechanisms capable of monitoring and detecting arbitrarily complex patterns in massive data streams. This task is usually performed by complex event processing (CEP) systems. CEP engines are required to process hundreds or even thousands of user-defined patterns in parallel under tight real-time constraints. To enhance the performance of this crucial operation, multiple techniques have been developed, utilizing well-known optimization approaches such as pattern rewriting and sharing common subexpressions. However, the scalability of these methods is limited by the high computation overhead, and the quality of the produced plans is compromised by ignoring significant parts of the solution space. In this paper, we present a novel framework for real-time multi-pattern complex event processing. Our approach is based on formulating the above task as a global optimization problem and applying a combination of sharing and pattern reordering techniques to construct an optimal plan satisfying the problem constraints. To the best of our knowledge, no such fusion was previously attempted in the field of CEP optimization. To locate the best possible evaluation plan in the resulting hyperexponential solution space, we design efficient local search algorithms that utilize the unique problem structure. An extensive theoretical and empirical analysis of our system demonstrates its superiority over state-of-the-art solutions.

uk: вхід без авторизації

name: Real-Time Multi-Pattern Detection over Event Streams


uk: Комп'ютерні науки

description: In the last decade, many distributed stream processing engines (SPEs) were developed to perform continuous queries on massive online data. The central design principle of these engines is to handle queries that potentially run forever on data streams with a query-at-a-time model, i.e., each query is optimized and executed separately. In many real applications, streams are not only processed with long-running queries, but also thousands of short-running ad-hoc queries. To support this efficiently, it is essential to share resources and computation for stream ad-hoc queries in a multi-user environment. The goal of this paper is to bridge the gap between stream processing and ad-hoc queries in SPEs by sharing computation and resources. We define three main requirements for ad-hoc shared stream processing: (1) Integration: Ad-hoc query processing should be a composable layer which can extend stream operators, such as join, aggregation, and window operators; (2) Consistency: Ad-hoc query creation and deletion must be performed in a consistent manner and ensure exactly-once semantics and correctness; (3) Performance: In contrast to state-of-the-art SPEs, ad-hoc SPE should not only maximize data throughput but also query throughout via incremental computation and resource sharing. Based on these requirements, we have developed AStream, an ad-hoc, shared computation stream processing framework. To the best of our knowledge, AStream is the first system that supports distributed ad-hoc stream processing. AStream is built on top of Apache Flink. Our experiments show that AStream shows comparable results to Flink for single query deployments and outperforms it in orders of magnitude with multiple queries.

uk: вхід без авторизації

name: AStream: Ad-hoc Shared Stream Processing


uk: Комп'ютерні науки

description: Resource interferences caused by concurrent queries is one of the key reasons for unpredictable performance and missed workload SLAs in cluster computing systems. Analyzing these inter-query resource interactions is critical in order to answer time-sensitive questions like 'who is creating resource conflicts to my query'. More importantly, diagnosing whether the resource blocked times of a 'victim' query are caused by other queries or some other external factor can help the database administrator narrow down the many possibilities of query performance degradation. We introduce iQCAR, an inter-Query Contention Analyzer, that attributes blame for the slowdown of a query to concurrent queries. iQCAR models the resource conflicts using a multi-level directed acyclic graph that can help administrators compare impacts from concurrent queries, identify most contentious queries, resources and hosts in an online execution for a selected time window. Our experiments using TPCDS queries on Apache Spark show that our approach is substantially more accurate than other methods based on overlap time between concurrent queries.

uk: вхід без авторизації

name: iQCAR: inter-Query Contention Analyzer for Data Analytics Frameworks


uk: Комп'ютерні науки

description: Data Analytics Frameworks encourage sharing of clusters for execution of mixed workloads by promising fairness and isolation along with high performance and resource utilization. However, concurrent query executions on such shared clusters result in increased queue and resource waiting times for queries affecting their overall performance. MIFO is a dataflow aware scheduling policy that mitigates the impacts due to queue and resource contentions by reducing the waiting times for queries near completion. We present heuristics that exploit query semantics to proactively trigger MIFO-based allocations in a workload. Our experiments on Apache Spark using TPCDS benchmark show that compared to a FAIR policy, MIFO provides an improved mean response time, reduced makespan of the workload and average speedup between 1.2x-2.7x in highly concurrent setting with only a momentary deviation in fairness.

uk: вхід без авторизації

name: MIFO: A Query-Semantic Aware Resource Allocation Policy


uk: Комп'ютерні науки

description: Matrix computation, in particular, matrix multiplication is time-consuming, but essentially and widely used in a large number of applications in science and industry. The existing distributed matrix multiplication methods only focus on either low communication cost (i.e., high performance) with the risk of out of memory or large-scale processing with high communication overhead. We propose a distributed elastic matrix multiplication method called CuboidMM that achieves both high performance and large-scale processing. We also propose a GPU acceleration method that can be combined with CuboidMM. CuboidMM partitions matrices into cuboids for optimizing the network communication cost with considering memory usage per task, and the GPU acceleration method partitions a cuboid into subcuboids for optimizing the PCI-E communication cost with considering GPU memory usage. We implement a fast and elastic matrix computation engine called DistME by integrating CuboidMM with GPU acceleration on top of Apache Spark. Through extensive experiments, we have demonstrated that CuboidMM and DistME significantly outperform the state-of-the-art methods and systems, respectively, in terms of both performance and data size.

uk: вхід без авторизації

name: DistME: A Fast and Elastic Distributed Matrix Computation Engine using GPUs


uk: Комп'ютерні науки

description: Subgraph matching (or subgraph isomorphism) is one of the fundamental problems in graph analysis. Extensive research has been done to develop practical solutions for subgraph matching. The state-of-the-art algorithms such as textsfCFL-Match and textsfTurbotextsubscriptiso convert a query graph into a spanning tree for obtaining candidates for each query vertex and obtaining a good matching order with the spanning tree. However, by using the spanning tree instead of the original query graph, it could lead to lower pruning power and a sub-optimal matching order. Another limitation is that they perform redundant computation in search without utilizing the knowledge learned from past computation. In this paper, we introduce three novel concepts to address these inherent limitations: 1) dynamic programming between a directed acyclic graph (DAG) and a graph, 2) adaptive matching order with DAG ordering, and 3) pruning by failing sets, which together lead to a much faster algorithm textsfDAF for subgraph matching. Extensive experiments with real datasets show that textsfDAF outperforms the fastest existing solution by up to orders of magnitude in terms of recursive calls as well as in terms of the elapsed time.

uk: вхід без авторизації

name: Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together


uk: Комп'ютерні науки

uk: вхід без авторизації

name: SIGMOD Test-Of-Time Award Talk: Building Tools for Differentially Private Data Analysis


uk: Комп'ютерні науки

description: We are at an exciting point in the evolution of memory technology. Device manufacturers have created a new non- volatile memory (NVM) technology that can serve as both system memory and storage. NVM supports fast reads and writes similar to volatile memory, but all writes to it are persistent like a solid-state disk. The advent of NVM invalidates decades of design decisions that are deeply embedded in today's database management systems (DBMSs). These systems are unable to take full advantage of NVM because their internal architectures are predicated on the assumption that memory is volatile. With NVM, many of the components of today's DBMSs are unnecessary and will degrade the performance of data-intensive applications. Thus, the best way to resolve these shortcomings is by designing a new system explicitly tailored for NVM. In this talk, I will present our research on the design and development of an NVM DBMS, called Peloton. Peloton's architecture shows that the impact of NVM spans across all the layers of the DBMS. I will first introduce write-behind logging, an NVM-centric protocol that improves the availability of the database system by two orders-of-magnitude compared to the widely-used write- ahead logging protocol. I will then present the BzTree, an NVM-centric index data structure that illustrates how to simplify programming on NVM. In drawing broader lessons from this work, I will argue that all types of software systems, including file systems, machine-learning systems, and key-value stores, are amenable to similar architectural changes to achieve high performance and availability on NVM.

uk: вхід без авторизації

name: Jim Gray SIGMOD Dissertation Award Winning Thesis: Data Management on Non-Volatile Memory


uk: Комп'ютерні науки

description: Over the past decade, in-memory database systems have become prevalent in academia and industry. However, large data sets often need to be stored distributed across the memory of several nodes in a cluster, since they often do not fit into the memory of a single machine. A database architecture that has recently been proposed for building distributed in-memory databases for fast RDMA-capable networks is the Network-Attached-Memory (NAM) architecture. The NAM architecture logically separates compute and memory servers and thus provides independent scalability of both resources. One important key challenge in the NAM architecture, is to provide efficient remote access methods for compute nodes to access data residing in memory nodes. In this paper, we therefore discuss design alternatives for distributed tree-based index structures in the NAM architecture. The two main aspects that we focus on in our paper are: (1) how the index itself should be distributed across several memory servers and (2) which RDMA primitives should be used by compute servers to access the distributed index structure in the most efficient manner. Our experimental evaluation shows the trade-offs for different distributed index design alternatives using a variety of workloads. While the focus of this paper is on the NAM architecture, we believe that the findings can also help to understand the design space on how to build distributed tree-based indexes for other RDMA-based distributed database architectures in general.

uk: вхід без авторизації

name: Designing Distributed Tree-based Index Structures for Fast RDMA-capable Networks


uk: Комп'ютерні науки

description: Interactive tools make data analysis more efficient and more accessible to end-users by hiding the underlying query complexity and exposing interactive widgets for the parts of the query that matter to the analysis. However, creating custom tailored (i.e., precise) interfaces is very costly, and automated approaches are desirable. We propose a syntactic approach that uses queries from an analysis to generate a tailored interface. We model interface widgets as functions I(q) -> q' that modify the current analysis query q, and interfaces as the set of queries that its widgets can express. Our system, Precision Interfaces, analyzes structural changes between input queries from an analysis, and generates an output interface with widgets to express those changes. Our experiments on the Sloan Digital Sky Survey query log suggest that Precision Interfaces can generate useful interfaces for simple unanticipated tasks, and our optimizations can generate interfaces from logs of up to 10,000 queries in <10s.

uk: вхід без авторизації

name: Mining Precision Interfaces From Query Logs


uk: Комп'ютерні науки

description: We introduce BriskStream, an in-memory data stream processing system (DSPSs) specifically designed for modern shared-memory multicore architectures. BriskStream’s key contribution is an execution plan optimization paradigm, namely RLAS, which takes relative-location (i.e., NUMA distance) of each pair of producer-consumer operators into consideration. We propose a branch and bound based approach with three heuristics to resolve the resulting nontrivial optimization problem. The experimental evaluations demonstrate that BriskStream yields much higher throughput and better scalability than existing DSPSs on multi-core architectures when processing different types of workloads.

uk: вхід без авторизації

name: BriskStream: Scaling Data Stream Processing on Shared-Memory Multicore Architectures


uk: Комп'ютерні науки

description: This paper presents GraphRex, an efficient, robust, scalable, and easy-to-program framework for graph processing on datacenter infrastructure. To users, GraphRex presents a declarative, Datalog-like interface that is natural and expressive. Underneath, it compiles those queries into efficient implementations. A key technical contribution of GraphRex is the identification and optimization of a set of global operators whose efficiency is crucial to the good performance of datacenter-based, large graph analysis. Our experimental results show that GraphRex significantly outperforms existing frameworks-both high- and low-level-in scenarios ranging across a wide variety of graph workloads and network conditions, sometimes by two orders of magnitude.

uk: вхід без авторизації

name: Optimizing Declarative Graph Queries at Large Scale


uk: Комп'ютерні науки

description: When faced with a database containing millions of tuples, an end user might be only interested in finding his/her (close to) favorite tuple in the database. Recently, a regret minimization query was proposed to obtain a small subset from the database that fits the user's needs, which are expressed through an unknown utility function. Specifically, it minimizes the 'regret' level of a user, which we quantify as the regret ratio if s/he gets the best tuple in the selected subset but not the best tuple among all tuples in the database. We study how to enhance the regret minimization query with user interactions: when presented with a small number of tuples (which can be artificial tuples or true tuples inside the database), a user is asked to indicate the tuple s/he favors the most among them. In particular, we are also interested in the special case of determining the favorite tuple for a user in the entire database with a small amount of interaction, measured by the number of questions we ask the user. Different from the previous work which displays artificial tuples to users, we achieve a stronger result in this paper by always displaying true tuples in the database. Specifically, we present a generic framework for interactive regret minimization, under which we propose algorithms that ask an asymptotically optimal number of questions in 2-dimensional spaces and algorithms with provable performance guarantees in d-dimensional spaces (d geq 2) where each dimension corresponds to a description of a tuple. Experiments on real and synthetic datasets showed that our algorithms outperform the existing one by locating the favorite tuple and guaranteeing a small regret ratiowith much fewer questions.

uk: вхід без авторизації

name: Strongly Truthful Interactive Regret Minimization


uk: Комп'ютерні науки

description: The last decade has witnessed a huge increase in data being ingested into the cloud, in forms such as JSON, CSV, and binary formats. Traditionally, data is either ingested into storage in raw form, indexed ad-hoc using range indices, or cooked into analytics-friendly columnar formats. None of these solutions is able to handle modern requirements on storage: making the data available immediately for ad-hoc and streaming queries while ingesting at extremely high throughputs. This paper builds on recent advances in parsing and indexing techniques to propose FishStore, a concurrent latch-free storage layer for data with flexible schema, based on multi-chain hash indexing of dynamically registered predicated subsets of data. We find predicated subset hashing to be a powerful primitive that supports a broad range of queries on ingested data and admits a high-performance concurrent implementation. Our detailed evaluation on real datasets and queries shows that FishStore can handle a wide range of workloads and can ingest and retrieve data at an order of magnitude lower cost than state-of-the-art alternatives.

uk: вхід без авторизації

name: FishStore: Faster Ingestion with Subset Hashing


uk: Комп'ютерні науки

description: Elasticity is highly desirable for stream systems to guarantee low latency against workload dynamics, such as surges in arrival rate and fluctuations in data distribution. Existing systems achieve elasticity using a resource-centric approach that repartitions keys across the parallel instances, i.e., executors, to balance the workload and scale operators. However, such operator-level repartitioning requires global synchronization and prohibits rapid elasticity. We propose an executor-centric approach that avoids operator-level key repartitioning and implements executors as the building blocks of elasticity. By this new approach, we design the Elasticutor framework with two level of optimizations: i) a novel implementation of executors, i.e., elastic executors, that perform elastic multi-core execution via efficient intra-executor load balancing and executor scaling and ii) a global model-based scheduler that dynamically allocates CPU cores to executors based on the instantaneous workloads. We implemented a prototype of Elasticutor and conducted extensive experiments. We show that Elasticutor doubles the throughput and achieves up to two orders of magnitude lower latency than previous methods for dynamic workloads of real-world applications.

uk: вхід без авторизації

name: Elasticutor: Rapid Elasticity for Realtime Stateful Stream Processing


uk: Комп'ютерні науки

description: We focus on the problem of answering OLAP queries via voice output. We present a holistic approach that combines query processing and result vocalization. We use the following key ideas to minimize processing overheads and maximize answer quality. First, our approach samples from the database to evaluate alternative speech fragments. OLAP queries are not fully evaluated. Instead, sampling focuses on result aspects that are relevant for voice output. To guide sampling, we rely on methods from the area of Monte-Carlo Tree Search. Second, we use pipelining to interleave query processing and voice output. The system starts providing the user with high-level insights while generating more fine-grained results in the background. Third, we optimize speech output to maximize the user's information gain under speaking time constraints. We use a maximum-entropy model to predict the user's belief about OLAP results, after listening to voice output. Based on that model, we select the most informative speech fragments (i.e., the ones minimizing the distance between user belief and actual data). We analyze formal properties of the proposed speech structure and analyze complexity of our algorithm. Also, we compare alternative vocalization approaches in an extensive user study.

uk: вхід без авторизації

name: A Holistic Approach for Query Evaluation and Result Vocalization in Voice-Based OLAP


uk: Комп'ютерні науки

description: Many distributed databases employ consensus protocols to ensure that data is replicated in a strongly-consistent manner on multiple machines despite failures and concurrency. Unfortunately, these protocols show widely varying performance under different network, workload, and deployment conditions, and no previous study offers a comprehensive dissection and comparison of their performance. To fill this gap, we study single-leader, multi-leader, hierarchical multi-leader, and leaderless (opportunistic leader) consensus protocols, and present a comprehensive evaluation of their performance in local area networks (LANs) and wide area networks (WANs). We take a two-pronged systematic approach. We present an analytic modeling of the protocols using queuing theory and show simulations under varying controlled parameters. To cross-validate the analytic model, we also present empirical results from our prototyping and evaluation framework, Paxi. We distill our findings to simple throughput and latency formulas over the most significant parameters. These formulas enable the developers to decide which category of protocols would be most suitable under given deployment conditions.

uk: вхід без авторизації

name: Dissecting the Performance of Strongly-Consistent Replication Protocols


uk: Комп'ютерні науки

description: Big data applications routinely involve diverse datasets: relations flat or nested, complex-structure graphs, documents, poorly structured logs, or even text data. To handle the data, application designers usually rely on several data stores used side-by-side, each capable of handling one or a few data models, and each very efficient for some, but not all, kinds of processing on the data. A current limitation is that applications are written taking into account which part of the data is stored in which store and how. This fails to take advantage of (i) possible redundancy, when the same data may be accessible (with different performance) from distinct data stores; (ii) partial query results (in the style of materialized views) which may be available in the stores. We present ESTOCADA, a novel approach connecting applications to the potentially heterogeneous systems where their input data resides. ESTOCADA can be used in a polystore setting to transparently enable each query to benefit from the best combination of stored data and available processing capabilities. ESTOCADA leverages recent advances in the area of view-based query rewriting under constraints, which we use to describe the various data models and stored data. Our experiments illustrate the significant performance gains achieved by ESTOCADA.

uk: вхід без авторизації

name: Towards Scalable Hybrid Stores: Constraint-Based Rewriting to the Rescue


uk: Комп'ютерні науки

uk: вхід без авторизації

name: SIGMOD Edgar F. Codd Innovations Award Talk


uk: Комп'ютерні науки

description: With increasing multi-core parallelism, modern databases and key-value stores are designed for scalability and presently yield very high throughput for the in-memory working set. These systems typically depend on group commit using a write-ahead log (WAL) to provide durability and crash recovery. However, a WAL is expensive, particularly for update-intensive workloads, where it also introduces a concurrency bottleneck (the log) besides log creation and I/O overheads. In this paper, we propose a new recovery model based on group commit, called concurrent prefix recovery (CPR). CPR differs from traditional group commit implementations in two ways: (1) it provides a semantic description of committed operations, of the form all operations until time Ti from session i; and (2) it uses asynchronous incremental checkpointing instead of a WAL to implement group commit in a scalable bottleneck-free manner. CPR provides the same consistency as a point-in-time commit, but allows a scalable concurrent implementation. We used CPR to make two systems durable: (1) a custom in-memory transactional database; and (2) Faster, our state-of-the-art, scalable, larger-than-memory key-value store. Our detailed evaluation of these modified systems shows that CPR is highly scalable and supports concurrent performance reaching hundreds of millions of operations per second on a multi-core machine.

uk: вхід без авторизації

name: Concurrent Prefix Recovery: Performing CPR on a Database


uk: Комп'ютерні науки

description: This paper studies the problem of answering Why-questions for graph pattern queries. Given a query Q, its answers Q(G) in a graph G, and an exemplar E that describes desired answers, it aims to compute a query rewrite Q', such that Q'(G) incorporates relevant entities and excludes irrelevant ones wrt E under a closeness measure. (1) We characterize the problem by Q-Chase. It rewrites Q by applying a sequence of applicable operators guided by E, and backtracks to derive optimal query rewrite. (2) We develop feasible Q-Chase-based algorithms, from anytime solutions to fixed-parameter approximations to compute query rewrites. These algorithms implement Q-Chase by detecting picky operators at run time, which discriminately enforce E to retain answers that are closer to exemplars, and effectively prune both operators and irrelevant matches, by consulting a cache of star patterns (called star views). Using real-world graphs, we experimentally verify the efficiency and effectiveness of qchase techniques and their applications.

uk: вхід без авторизації

name: Answering Why-questions by Exemplars in Attributed Graphs


uk: Комп'ютерні науки

description: Query containment is a fundamental operation used to expedite query processing in view materialisation and query caching techniques. Since query containment has been shown to be NP-complete for arbitrary conjunctive queries on RDF graphs, we introduce a simpler form of conjunctive queries that we name f-graph queries. We first show that containment checking for f-graph queries can be solved in polynomial time. Based on this observation, we propose a novel indexing structure, named mv-index, that allows for fast containment checking between a single f-graph query and an arbitrary number of stored queries. Search is performed in polynomial time in the combined size of the query and the index. We then show how our algorithms and structures can be extended for arbitrary conjunctive queries on RDF graphs by introducing f-graph witnesses, i.e., f-graph representatives of conjunctive queries. F-graph witnesses have the following interesting property, a conjunctive query for RDF graphs is contained in another query only if its corresponding f-graph witness is also contained in it. The latter allows to use our indexing structure for the general case of conjunctive query containment. This translates in practice to microseconds or less for the containment test against hundreds of thousands of queries that are indexed within our structure.

uk: вхід без авторизації

name: An Efficient Index for RDF Query Containment


uk: Комп'ютерні науки

description: Given a query tree Q, the top-k subtree similarity query retrieves the k subtrees in a large document tree T that are closest to Q in terms of tree edit distance. The classical solution scans the entire document, which is slow. The state-of-the-art approach precomputes an index to reduce the query time. However, the index is large (quadratic in the document size), building the index is expensive, updates are not supported, and data-specific tuning is required.We present a scalable solution for the top-k subtree similarity problem that does not assume specific data types, nor does it require any tuning. The key idea is to process promising subtrees first. A subtree is promising if it shares many labels with the query. We develop a new technique based on inverted lists that efficiently retrieves subtrees in the required order and supports incremental updates of the document. To achieve linear space, we avoid full list materialization but build relevant parts of a list on the fly.In an extensive empirical evaluation on synthetic and real-world data, our technique consistently outperforms the state-of-the-art index w.r.t. memory usage, indexing time, and the number of candidates that must be verified. In terms of query time, we clearly outperform the state of the art and achieve runtime improvements of up to four orders of magnitude.

uk: вхід без авторизації

name: A Scalable Index for Top-k Subtree Similarity Queries


uk: Комп'ютерні науки

description: Actions changing the state of databases are all logged with proper ordering being imposed. Database engines obeying this golden rule of logging enforce total ordering on all events, and this poses challenges in addressing the scalability bottlenecks of database logging on multicore hardware. We reexamined the problem of database logging and realized that in any given log history, obtaining an upper bound on the size of a set that preserves the happen-before relation is the essence of the matter. Based on our understanding, we propose Border-Collie, a wait-free and read-optimal algorithm for database logging that finds such an upper bound even with some worker threads often being idle. We show that (1) Border-Collie always finds the largest set of logged events satisfying the condition in a finite number of steps (i.e., wait-free), (2) the number of logged events to be read is also minimal (i.e., read-optimal), and (3) both properties hold even with threads being in intermittent work. Experimental results demonstrated that Border-Collie proves our claims under various workloads; Border-Collie outperforms the state-of-the-art centralized logging techniques (i.e., Eleda and ERMIA) by up to ~2X and exhibits almost the same throughput with much shorter commit latency than the state-of-the-art decentralized logging techniques (i.e., Silo and FOEDUS).

uk: вхід без авторизації

name: Border-Collie: A Wait-free, Read-optimal Algorithm for Database Logging on Multicore Hardware


uk: Комп'ютерні науки

description: Recently, video database management systems (VDBMSs) have re-emerged as an active area of research and development. To accelerate innovation in this area, we present Visual Road, a benchmark that evaluates the performance of these systems. Visual Road comes with a data generator and a suite of queries over cameras positioned within a simulated metropolitan environment. Visual Road's video data is automatically generated with a high degree of realism, and annotated using a modern simulation and visualization engine. This allows for VDBMS performance evaluation while scaling up the size of the input data. Visual Road is designed to evaluate a broad variety of VDBMSs: real-time systems, systems for longitudinal analytical queries, systems processing traditional videos, and systems designed for 360 videos. We use the benchmark to evaluate three recent VDBMSs both in capabilities and performance.

uk: вхід без авторизації

name: Visual Road: A Video Data Management Benchmark


uk: Комп'ютерні науки

description: We present a novel natural language query interface, the AggChecker, aimed at text summaries of relational data sets. The tool focuses on natural language claims that translate into an SQL query and a claimed query result. Similar in spirit to a spell checker, the AggChecker marks up text passages that seem to be inconsistent with the actual data. At the heart of the system is a probabilistic model that reasons about the input document in a holistic fashion. Based on claim keywords and the document structure, it maps each text claim to a probability distribution over associated query translations. By efficiently executing tens to hundreds of thousands of candidate translations for a typical input document, the system maps text claims to correctness probabilities. This process becomes practical via a specialized processing backend, avoiding redundant work via query merging and result caching. Verification is an interactive process in which users are shown tentative results, enabling them to take corrective actions if necessary. We tested our system on 53 publicly available articles containing 392 claims. Our tool revealed erroneous claims in roughly a third of test cases. Also, AggChecker compares favorably against several automated and semi-automated fact checking baselines.

uk: вхід без авторизації

name: Verifying Text Summaries of Relational Data Sets


uk: Комп'ютерні науки

uk: вхід без авторизації

name: SIGMOD Systems Award Talk on the Aurora Database System


uk: Комп'ютерні науки

description: Data enrichment is the act of extending a local database with new attributes from external data sources. In this paper, we study a novel problem—how to progressively crawl the deep web (i.e., a hidden database) through a keyword-search API to enrich a local database in an e ective way. This is chal- lenging because these interfaces often limit the data access by enforcing the top-k constraint or limiting the number of queries that can be issued within a time window. In response, we propose SmartCrawl, a new framework to collect re- sults e ectively. Given a query budget b, SmartCrawl rst constructs a query pool based on the local database, and then iteratively issues a set of most bene cial queries to the hidden database such that the union of the query results can cover the maximum number of local records. The key technical challenge is how to estimate query bene t, i.e., the number of local records that can be covered by a given query. A simple approach is to estimate it as the query frequency in the local database. We nd that this is ine ective due to i) the impact of |?D|, where |?D| represents the number of local records that cannot be found in the hidden database, and ii) the top-k constraint enforced by the hidden database. We study how to mitigate the negative impacts of the two factors and propose e ective optimization techniques to improve performance. The experimental results show that on both simulated and real-world hidden databases, SmartCrawl signi cantly increases coverage over the local database as compared to the baselines.

uk: вхід без авторизації

name: Progressive Deep Web Crawling Through Keyword Queries For Data Enrichment


Data Platform for Machine Learning

uk: Комп'ютерні науки

description: In this paper, we present a purpose-built data management system, MLdp, for all machine learning (ML) datasets. ML applications pose some unique requirements different from common conventional data processing applications, including but not limited to: data lineage and provenance tracking, rich data semantics and formats, integration with diverse ML frameworks and access patterns, trial-and-error driven data exploration and evolution, rapid experimentation, reproducibility of the model training, strict compliance and privacy regulations, etc. Current ML systems/services, often named MLaaS, to-date focus on the ML algorithms, and offer no integrated data management system. Instead, they require users to bring their own data and to manage their own data on either blob storage or on file systems. The burdens of data management tasks, such as versioning and access control, fall onto the users, and not all compliance features, such as terms of use, privacy measures, and auditing, are available. MLdp offers a minimalist and flexible data model for all varieties of data, strong version management to guarantee re-producibility of ML experiments, and integration with major ML frameworks. MLdp also maintains the data provenance to help users track lineage and dependencies among data versions and models in their ML pipelines. In addition to table-stake features, such as security, availability and scalability, MLdp's internal design choices are strongly influenced by the goal to support rapid ML experiment iterations, which cycle through data discovery, data exploration, feature engineering, model training, model evaluation, and back to data discovery. The contributions of this paper are: 1) to recognize the needs and to call out the requirements of an ML data platform, 2) to share our experiences in building MLdp by adopting existing database technologies to the new problem as well as by devising new solutions, and 3) to call for actions from our communities on future challenges.

uk: вхід без авторизації


uk: Комп'ютерні науки

description: The database-as-a-service paradigm in the cloud (DBaaS) is becoming increasingly popular. Organizations adopt this paradigm because they expect higher security, higher availability, and lower and more flexible cost with high performance. It has become clear, however, that these expectations cannot be met in the cloud with the traditional, monolithic database architecture. This paper presents a novel DBaaS architecture, called Socrates. Socrates has been implemented in Microsoft SQL Server and is available in Azure as SQL DB Hyperscale. This paper describes the key ideas and features of Socrates, and it compares the performance of Socrates with the previous SQL DB offering in Azure.

uk: вхід без авторизації

name: Socrates: The New SQL Server in the Cloud


uk: Комп'ютерні науки

description: Labeling training data is one of the most costly bottlenecks in developing machine learning-based applications. We present a first-of-its-kind study showing how existing knowledge resources from across an organization can be used as weak supervision in order to bring development time and cost down by an order of magnitude, and introduce Snorkel DryBell, a new weak supervision management system for this setting. Snorkel DryBell builds on the Snorkel framework, extending it in three critical aspects: flexible, template-based ingestion of diverse organizational knowledge, cross-feature production serving, and scalable, sampling-free execution. On three classification tasks at Google, we find that Snorkel DryBell creates classifiers of comparable quality to ones trained with tens of thousands of hand-labeled examples, converts non-servable organizational resources to servable models for an average 52% performance improvement, and executes over millions of data points in tens of minutes.

uk: вхід без авторизації

name: Snorkel DryBell: A Case Study in Deploying Weak Supervision at Industrial Scale


uk: Комп'ютерні науки

description: Motivated by applications such as viral marketing, the problem of influence maximization (IM) has been extensively studied in the literature. The goal is to select a small number of users to adopt an item such that it results in a large cascade of adoptions by others. Existing works have three key limitations. (1) They do not account for economic considerations of a user in buying/adopting items. (2) Most studies on multiple items focus on competition, with complementary items receiving limited attention. (3) For the network owner, maximizing social welfare is important to ensure customer loyalty, which is not addressed in prior work in the IM literature. In this paper, we address all three limitations and propose a novel model called UIC that combines utility-driven item adoption with influence propagation over networks. Focusing on the mutually complementary setting, we formulate the problem of social welfare maximization in this novel setting. We show that while the objective function is neither submodular nor supermodular, surprisingly a simple greedy allocation algorithm achieves a factor of (1-1/e-epsilon) of the optimum expected social welfare. We develop textsfbundleGRD, a scalable version of this approximation algorithm, and demonstrate, with comprehensive experiments on real and synthetic datasets, that it significantly outperforms all baselines.

uk: вхід без авторизації

name: Maximizing Welfare in Social Networks under A Utility Driven Influence Diffusion model


uk: Комп'ютерні науки

description: Real-time data analysis and management are increasingly critical for today’s businesses. SQL is the de facto lingua franca for these endeavors, yet support for robust streaming analysis and management with SQL remains limited. Many approaches restrict semantics to a reduced subset of features and/or require a suite of non-standard constructs. Additionally, use of event timestamps to provide native support for analyzing events according to when they actually occurred is not pervasive, and often comes with important limitations. We present a three-part proposal for integrating robust streaming into SQL, namely: (1) time-varying relations as a foundation for classical tables as well as streaming data, (2) event time semantics, (3) a limited set of optional keyword extensions to control the materialization of time-varying query results. We show how with these minimal additions it is possible to utilize the complete suite of standard SQL semantics to perform robust stream processing. We motivate and illustrate these concepts using examples and describe lessons learned from implementations in Apache Calcite, Apache Flink, and Apache Beam. We conclude with syntax and semantics of a concrete proposal for extensions of the SQL standard and note further areas of exploration

uk: вхід без авторизації

name: One SQL to Rule Them All - an Efficient and Syntactically Idiomatic Approach to Management of Streams and Tables


uk: Комп'ютерні науки

description: Spreadsheet systems enable users to store and analyze data in an intuitive and flexible interface. Yet the scale of data being analyzed often leads to spreadsheets hanging and freezing on small changes. We propose a new asynchronous formula computation framework: instead of freezing the interface we return control to users quickly to ensure interactivity, while computing the formulae in the background. To ensure consistency, we indicate formulae being computed in the background via visual cues on the spreadsheet. Our asynchronous computation framework introduces two novel challenges: (a) How do we identify dependencies for a given change in a bounded time? (b) How do we schedule computation to maximize the number of spreadsheet cells available to the user over time? We bound the dependency identification time by compressing the formula dependency graph lossily, a problem we show to be NP-Hard. A compressed dependency table enables us to quickly identify the spreadsheet cells that need recomputation and indicate them as such to users. Finding an optimal computation schedule to maximize cell availability is also NP-Hard, and even merely obtaining a schedule can be expensive—we propose an on-the-fly scheduling technique to address this. We have incorporated asynchronous computation in DataSpread, a scalable spreadsheet system targeted at operating on arbitrarily large datasets on a spreadsheet frontend.

uk: вхід без авторизації

name: Anti-Freeze for Large and Complex Spreadsheets: Asynchronous Formula Computation