The splay-list: a distribution-adaptive concurrent skip-list

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Ashenhurst-Curtis decomposition (ACD) is a decomposition technique used, in particular, to map combinational logic into lookup tables (LUTs) structures when synthesizing hardware designs. However, available implementations of ACD suffer from excessive comp ...

Car sharing systems (CSSs) are one of the environmentally beneficial solutions in urban transportation. However, the operators still struggle to make these systems profitable. One of the main contributors in operational cost is rebalancing operations. Ther ...

Vehicle sharing systems (VSSs) allow users to rent vehicles for a short period of time, in a more flexible and convenient manner compared to the traditional vehicle rental services. The long-term VSS subscription replaces the need for contract signing for ...

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

The metric dimension of a graph G is the minimal size of a subset R of vertices of G that, upon reporting their graph distance from a distinguished (source) vertex v⋆, enable unique identification of the source vertex v⋆ among all possible vertices of G. I ...

Non-Volatile Memory (NVM) is an emerging type of memory device that provides fast, byte-addressable, and high-capacity durable storage. NVM sits on the memory bus and allows durable data structures designs similar to the in-memory equivalent ones. Expensiv ...

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

Modern large-scale data platforms manage colossal amount of data, generated by the ever-increasing number of concurrent users. Geo-replicated and sharded key-value data stores play a central role when building such platforms. As the strongest consistency m ...

In this thesis, we revisit classic problems in shared-memory distributed computing through the lenses of (1) emerging hardware technologies and (2) changing requirements. Our contributions consist, on the one hand, in providing a better understanding of th ...

In this paper we revisit the kernel density estimation problem: given a kernel K(x, y) and a dataset of n points in high dimensional Euclidean space, prepare a data structure that can quickly output, given a query q, a (1 + epsilon)-approximation to mu := ...

The increase in the number of cores in processors has been an important trend over the past decade. In order to be able to efficiently use such architectures, modern software must be scalable: performance should increase proportionally to the number of all ...

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 ...

We propose an online algorithm for sequential learning in the contextual multiarmed bandit setting. Our approach is to partition the context space and, then, optimally combine all of the possible mappings between the partition regions and the set of bandit ...

Static estimation of resource utilisation of programs is a challenging and important problem with numerous applications. In this thesis, I present new algorithms that enable users to specify and verify their desired bounds on resource usage of functional p ...

Causal consistency is one of the most adopted consistency criteria for distributed implementations of data structures. It ensures that operations are executed at all sites according to their causal precedence. We address the issue of verifying automaticall ...

Geo-replicated data platforms are at the backbone of several large-scale online services. Transactional Causal Consistency (TCC) is an attractive consistency level for building such platforms. TCC avoids many anomalies of eventual consistency, eschews the ...

Virtual memory (VM) is a crucial abstraction in modern computer systems at any scale, from handheld devices to datacenters. VM provides programmers the illusion of an always sufficiently large and linear memory, making programming easier. Although the core ...

Database systems access memory either sequentially or randomly. Contrary to sequential access and despite the extensive efforts of computer architects, compiler writers, and system builders, random access to data larger than the processor cache has been s ...

In this thesis, we explore techniques for the development and verification of programs in a high-level, expressive, and safe programming language. Our programs can express problems over unbounded domains and over recursive and mutable data structures. We p ...

The splay-list: a distribution-adaptive concurrent skip-list

Chat with Graph Search

Enhancing Delay-Driven LUT Mapping with Boolean Decomposition

A general framework to evaluate different rebalancing operations strategies in one-way car sharing systems

Demand-based operations of vehicle sharing systems

Fairness and Explainability in Clustering Problems

Sketches, metrics and fast algorithms

Metric dimension of critical Galton–Watson trees and linear preferential attachment trees

Software Support for Non-Volatile Memory (NVM) Programming

Sequential metric dimension for random graphs

Efficient Protocols for Enforcing Causal Consistency in Geo-Replicated Key-Value Data Stores

Distributed Computing with Modern Shared Memory

Kernel Density Estimation through Density Constrained Near Neighbor Search

Universally Scalable Concurrent Data Structures

Interleaving with Coroutines: A Practical Approach for Robust Index Joins

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Algorithmic Resource Verification

On verifying causal consistency

PaRiS: Causally Consistent Transactions with Non-blocking Reads and Partial Replication

Near-Memory Address Translation

Improving Main-memory Database System Performance through Cooperative Multitasking

Verification by Reduction to Functional Programs