Concept
Arbre splay
Publications associées (40)
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 ...
SPRINGER2023Fairness and Explainability in Clustering Problems
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 ...
EPFL2023Efficient 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, ...
2022Scalable 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 ...
arXiv2022Metric dimension of critical Galton–Watson trees and linear preferential attachment trees
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 ...
2021When Is Amplification Necessary for Composition in Randomized Query Complexity?
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 Informatik2020Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures
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 ...
2019Termination 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 ...
2017Interleaving 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.2017Optimal 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