Publications related to Datalog

HyperLogLog: Exponentially Bad in Adversarial Settings

Computing the count of distinct elements in large data sets is a common task but naive approaches are memory-expensive. The HyperLogLog (HLL) algorithm (Flajolet et al., 2007) estimates a data set's cardinality while using significantly less memory than a ...

IEEE COMPUTER SOC2022

Micro-architectural Analysis of Database Workloads

Utku Sirin

Database workloads have significantly evolved in the past twenty years. Traditional database systems that are mainly used to serve Online Transactional Processing (OLTP) workloads evolved into specialized database systems that are optimized for particular ...

EPFL2021

Parallel-Correctness and Containment for Conjunctive Queries with Union and Negation

Bas Ketsman

Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a g ...

ASSOC COMPUTING MACHINERY2019

RAQ: Relationship-Aware Graph Querying in Large Networks

Akhil Arora, Arnab Bhattacharya

The phenomenal growth of graph data from a wide variety of real-world applications has rendered graph querying to be a problem of paramount importance. Traditional techniques use structural as well as node similarities to find matches of a given query grap ...

ASSOC COMPUTING MACHINERY2019

Interactive Visual Exploration of Spatio-Temporal Urban Data Sets using Urbane

Anastasia Ailamaki, Eleni Tzirita Zacharatou, Haoqiong Bian

The recent explosion in the number and size of spatio-temporal data sets from urban environments and social sensors creates new opportunities for data-driven approaches to understand and improve cities. Visual analytics systems like Urbane aim to empower d ...

2018

Efficient Online Processing for Advanced Analytics

Mohamed Elsayed Mohamed Ahmed El Seidy

With the advent of emerging technologies and the Internet of Things, the importance of online data analytics has become more pronounced. Businesses and companies are adopting approaches that provide responsive analytics to stay competitive in the global ma ...

EPFL2017

A Query Model to Capture Event Pattern Matching in RDF Stream Processing Query Languages

Jean Paul Calbimonte Perez

The current state of the art in RDF Stream Processing (RSP) proposes several models and implementations to combine Semantic Web technologies with Data Stream Management System (DSMS) operators like windows. Meanwhile, only a few solutions combine Semantic ...

Springer Int Publishing Ag2016

Fast Queries Over Heterogeneous Data Through Engine Customization

Anastasia Ailamaki, Ioannis Alagiannis, Manolis Karpathiotakis

Industry and academia are continuously becoming more data-driven and data-intensive, relying on the analysis of a wide variety of heterogeneous datasets to gain insights. The different data models and formats pose a significant challenge on performing anal ...

Assoc Computing Machinery2016

How to Architect a Query Compiler

Christoph Koch, Ioannis Klonatos, Amir Shaikhha, Lionel Emile Vincent Parreaux, Mohammad Dashti Rahmat Abadi, Lewis Alexander Brown

This paper studies architecting query compilers. The state of the art in query compiler construction is lagging behind that in the compilers field. We attempt to remedy this by exploring the key causes of technical challenges in need of well founded soluti ...

2016

Parallelizing Query Optimization on Shared-Nothing Architectures

Christoph Koch, Immanuel Trummer

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

Efficient Incremental Data Analysis

Milos Nikolic

Many data-intensive applications require real-time analytics over streaming data. In a growing number of domains -- sensor network monitoring, social web applications, clickstream analysis, high-frequency algorithmic trading, and fraud detections to name a ...

EPFL2016

On recursion-free Horn clauses and Craig interpolation

Viktor Kuncak, Hossein Hojjat

One of the main challenges in software verification is efficient and precise analysis of programs with procedures and loops. Interpolation methods remain among the most promising techniques for such verification. To accommodate the demands of various progr ...

Springer2015

Smooth Scan: Statistics-Oblivious Access Paths

Anastasia Ailamaki, Renata Borovica-Gajic

Query optimizers depend heavily on statistics representing column distributions to create efficient query plans. In many cases, though, statistics are outdated or non-existent, and the process of refreshing statistics is very expensive, especially for ad-h ...

2015

Building Efficient Query Engines in a High-Level Language

Christoph Koch, Ioannis Klonatos, Tiark Rompf, Hassan Chafi

In this paper we advocate that it is time for a radical rethinking of database systems design. Developers should be able to leverage high-level programming languages without having to pay a price in efficiency. To realize our vision of abstraction without ...

2014

Solid-State Storage and Work Sharing for Efficient Scaleup Data Analytics

Manoussos Gavriil Athanassoulis

Today, managing, storing and analyzing data continuously in order to gain additional insight is becoming commonplace. Data analytics engines have been traditionally optimized for read-only queries assuming that the main data reside on mechanical disks. The ...

EPFL2014

Jet: An Embedded DSL for High Performance Big Data Processing

Martin Odersky, Tiark Rompf, Vojin Jovanovic, Stefan Ackermann

Cluster computing systems today impose a trade-off between generality, performance and productivity. Hadoop and Dryad force programmers to write low level programs that are tedious to compose but easy to optimize. Systems like Dryad/LINQ and Spark allow co ...

2012

ConDense: Managing Data in Community-driven Mobile Geosensor Networks

Karl Aberer, Dipanjan Chakraborty, Saket Sathe, Sebastian Cartier

Effectively managing the data generated by community-driven mobile geo-sensor networks is a new and challenging problem. One important step for managing and querying sensor network data is to create abstractions of the data in the form of models. These mod ...

2012

Efficient Processing of Ranking Queries in Novel Applications

Parisa Haghani

Ranking queries, which return only a subset of results matching a user query, have been studied extensively in the past decade due to their importance in a wide range of applications. In this thesis, we study ranking queries in novel environments and setti ...

EPFL2010

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Zoltán Miklós

The generalized hypertree width GHW(H) of a hypergraph H is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, i ...

2009

A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses

George Candea

Conventional data warehouses employ the query-at-a-time model, which maps each query to a distinct physical plan. When several queries execute concurrently, this model introduces contention, because the physical plans—unaware of each other—compete for acce ...

2009