Publications associées à Approximation schemes for many-objective query optimization

Efficient Concurrent Analytical Query Processing using Data and Workload-conscious Sharing

Analytical workloads are evolving as the number of users surges and applications that submit queries in batches become popular. However, traditional analytical databases that optimize-then-execute each query individually struggle to provide timely response ...

EPFL2023

Aggregation and Exploration of High-Dimensional Data Using the Sudokube Data Cube Engine

Christoph Koch, Sachin Basil John, Peter Lindner, Zhekai Jiang

We present Sudokube, a novel system that supports interactive speed querying on high-dimensional data using partially materialized data cubes. Given a storage budget, it judiciously chooses what projections to precompute and materialize during cube constru ...

Association for Computing Machinery2023

Efficient GPU-accelerated Join Optimization for Complex Queries

Anastasia Ailamaki, Bikash Chandra, Srinivas Karthik Venkatesh, Riccardo Mancini, Vasileios Mageirakos

Analytics on modern data analytic and data warehouse systems often need to run large complex queries on increasingly complex database schemas. A lot of progress has been made on executing such complex queries using techniques like scale out query processin ...

IEEE2022

Efficient Massively Parallel Join Optimization for Large Queries

Anastasia Ailamaki, Bikash Chandra, Srinivas Karthik Venkatesh, Riccardo Mancini, Vasileios Mageirakos

Modern data analytical workloads often need to run queries over a large number of tables. An optimal query plan for such queries is crucial for being able to run these queries within acceptable time bounds. However, with queries involving many tables, find ...

ACM2022

Optimal Matching of Random Parts

Thomas Alois Weber

This paper examines the minimization of the cost for an expected random production output, given an assembly of finished goods from two random inputs, matched in two categories. We describe the optimal input portfolio, first using the standard normal appro ...

2022

Edit Based Grading of SQL Queries

Bikash Chandra

Grading student SQL queries manually is a tedious and error-prone process. Earlier work on testing correctness of student SQL queries, such as the XData system, can be used to test the correctness of a student query. However, in case a student query is fou ...

ASSOC COMPUTING MACHINERY2021

Scalable Multi-Query Execution using Reinforcement Learning

Anastasia Ailamaki, Panagiotis Sioulas

The growing demand for data-intensive decision support and the migration to multi-tenant infrastructures put databases under the stress of high analytical query load. The requirement for high throughput contradicts the traditional design of query-at-a-time ...

Association for Computing Machinery2021

Fair colorful k-center clustering

Ola Nils Anders Svensson, Xinrui Jia

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius rho such that there exist balls of radius rho aro ...

SPRINGER HEIDELBERG2022

Fair Colorful k-Center Clustering

Ola Nils Anders Svensson, Xinrui Jia

An instance of colorful k-center consists of points in a metric space that are colored red or blue, along with an integer k and a coverage requirement for each color. The goal is to find the smallest radius ρ such that there exist balls of radius ρ around ...

Springer2020

Timely and cost-efficient data exploration through adaptive tuning

Matthaios Alexandros Olma

Modern applications accumulate data at an exponentially increasing rate and traditional database systems struggle to keep up. Decision support systems used in industry, rely heavily on data analysis, and require real-time responses irrespective of data siz ...

EPFL2019

Time- and Space-Efficient Spatial Data Analytics

Mirjana Pavlovic

Advances in data acquisition technologies and supercomputing for large-scale simulations have led to an exponential growth in the volume of spatial data. This growth is accompanied by an increase in data complexity, such as spatial density, but also by mor ...

EPFL2019

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

A Constant-Factor Approximation Algorithm for the Asymmetric Traveling Salesman Problem

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant-factor approximation algorithm for the asymmetric traveling salesman problem. Our approximation guarantee is analyzed with respect to the standard LP relaxation, and thus our result confirms the conjectured constant integrality gap of th ...

ASSOC COMPUTING MACHINERY2018

Compilation Techniques for Incremental Collection Processing

Daniel Lupei

Many map-reduce frameworks as well as NoSQL systems rely on collection programming as their interface of choice due to its rich semantics along with an easily parallelizable set of primitives. Unfortunately, the potential of collection programming is not ...

EPFL2017

Interleaving with Coroutines: A Practical Approach for Robust Index Joins

Anastasia Ailamaki, Georgios Psaropoulos

Index join performance is determined by the efficiency of the lookup operation on the involved index. Although database indexes are highly optimized to leverage processor caches, main memory accesses inevitably increase lookup runtime when the index outsiz ...

VLDB Endowment Inc.2017

From Massive Parallelization to Quantum Computing: Seven Novel Approaches to Query Optimization

Immanuel Trummer

The goal of query optimization is to map a declarative query (describing data to generate) to a query plan (describing how to generate the data) with optimal execution cost. Query optimization is required to support declarative query interfaces. It is a co ...

EPFL2016

How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates

Milos Nikolic, Christoph Koch, Mohammad Dashti Rahmat Abadi

In the quest for valuable information, modern big data applications continuously monitor streams of data. These applications demand low latency stream processing even when faced with high volume and velocity of incoming changes and the user’s desire to ask ...

2016

Toward timely, predictable and cost-effective data analytics

Renata Borovica-Gajic

Modern industrial, government, and academic organizations are collecting massive amounts of data at an unprecedented scale and pace. The ability to perform timely, predictable and cost-effective analytical processing of such large data sets in order to ext ...

EPFL2016

Parallelizing Query Optimization on Shared-Nothing Architectures

Immanuel Trummer, Christoph Koch

Data processing systems offer an ever increasing degree of parallelism on the levels of cores, CPUs, and processing nodes. Query optimization must exploit high degrees of parallelism in order not to gradually become the bottleneck of query evaluation. We s ...

Assoc Computing Machinery2016

Cheap Data Analytics using Cold Storage Devices

Anastasia Ailamaki, Renata Borovica-Gajic, Raja Appuswamy

Enterprise databases use storage tiering to lower capital and operational expenses. In such a setting, data waterfalls from an SSD-based high-performance tier when it is "hot" (frequently accessed) to a disk-based capacity tier and finally to a tape-based ...

Assoc Computing Machinery2016