Concept

Splay tree

Related publications (40)

Graph Chatbot

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.

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

Amirkeivan Mohtashami, Dan Alistarh

The design and implementation of efficient concurrent data structures has seen significant attention. However, most of this work has focused on concurrent data structures providing good worst-case guarantees, although, in real workloads, objects are often ...

SPRINGER2023

Fairness and Explainability in Clustering Problems

Xinrui Jia

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

EPFL2023

Efficient Max-Pressure Traffic Management for Large-Scale Congested Urban Networks

Nikolaos Geroliminis, Dimitrios Tsitsokas, Anastasios Kouvelas

Traffic responsive signal control systems bear high potential in reducing delays in congested networks due to their ability of dynamically adjusting right-of-way assignment among conflicting movements, based on real-time traffic measurements. In this work, ...

2022

Scalable Fine-Grained Parallel Cycle Enumeration Algorithms

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Enumerating simple cycles has important applications in computational biology, network science, and financial crime analysis. In this work, we focus on parallelising the state-of-the-art simple cycle enumeration algorithms by Johnson and Read-Tarjan along ...

arXiv2022

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

Gergely Odor

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

2021

When Is Amplification Necessary for Composition in Randomized Query Complexity?

Mika Tapani Göös

Suppose we have randomized decision trees for an outer function f and an inner function g. The natural approach for obtaining a randomized decision tree for the composed function (f∘ gⁿ)(x¹,…,xⁿ) = f(g(x¹),…,g(xⁿ)) involves amplifying the success probabili ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2020

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

2019

Termination of Open Higher-Order Programs

Viktor Kuncak, Nicolas Charles Yves Voirol, Ravichandhran Kandhadai Madhavan

We study the problem of proving termination of open, higher-order programs with recursive functions and datatypes. We identify a new point in the design space of solutions, with an appealing trade-off between simplicity of specification, modularity, and am ...

2017

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

Optimal Software Patching Plan for PMUs

Jean-Yves Le Boudec, Ola Nils Anders Svensson, Teklemariam Tsegay Tesfay

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the ...

2017