Publications associées à Self-balancing binary search tree

Planetary-Scale Byzantine Fault Tolerance

The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...

EPFL2024

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

From Trees to Barcodes and Back Again: A Combinatorial, Probabilistic and Geometric Study of a Topological Inverse Problem

Adélie Eliane Garin

In this thesis, we investigate the inverse problem of trees and barcodes from a combinatorial, geometric, probabilistic and statistical point of view. Computing the persistent homology of a merge tree yields a barcode B. Reconstructing a tree from B invol ...

EPFL2022

Beyond Local Optimality of Buffer and Splitter Insertion for AQFP Circuits

Giovanni De Micheli, Heinz Riener, Siang-Yun Lee

Adiabatic quantum-flux parametron (AQFP) is an energy-efficient superconducting technology. Buffer and splitter (B/S) cells must be inserted to an AQFP circuit to meet the technology-imposed constraints on path balancing and fanout branching. These cells a ...

ACM2022

Mapping forest in the Swiss Alps treeline ecotone with explainable deep learning

Devis Tuia, Benjamin Alexander Kellenberger, Thiên-Anh Claris Nguyen

Forest maps are essential to understand forest dynamics. Due to the increasing availability of remote sensing data and machine learning models like convolutional neural networks, forest maps can these days be created on large scales with high accuracy. Com ...

Elsevier2022

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

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

2021

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

Scalable and Efficient Comparison-based Search without Features

Matthias Grossglauser, Lucas Maystre, Daniyar Chumbalov

We consider the problem of finding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i, j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generate ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2020

Asymptotically Optimal Contextual Bandit Algorithm Using Hierarchical Structures

Hakan Gökcesu, Kaan Gökcesu

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

Unsupervised Robust Nonparametric Learning Of Hidden Community Properties

Martin Jaggi, Akhilesh Deepak Gotmare, Mikhail Langovoy

We consider learning of fundamental properties of communities in large noisy networks, in the prototypical situation where the nodes or users are split into two classes according to a binary property, e.g., according to their opinions or preferences on a t ...

2019

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

Miniphases: Compilation using Modular and Efficient Tree Transformations

Martin Odersky, Dmytro Petrashko, Ondrej Lhoták

Production compilers commonly perform dozens of transformations on an intermediate representation. Running those transformations in separate passes harms performance. One approach to recover performance is to combine transformations by hand in order to red ...

Assoc Computing Machinery2017

Elastic transactions

Rachid Guerraoui, Vincent Gramoli, Pascal Felber

This paper presents elastic transactions, an appealing alternative to traditional transactions, in particular to implement search structures in shared memory multicore architectures. Upon conflict detection, an elastic transaction might drop what it did so ...

Academic Press Inc Elsevier Science2017

Algorithmic Resource Verification

Ravichandhran Kandhadai Madhavan

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

EPFL2017

Fast generation of lexicographic satisfiable assignments: enabling canonicity in SAT-based applications

Giovanni De Micheli, Paolo Ienne, Mathias Soeken, Ana Petkovska

Lexicographic Boolean satisfiability (LEXSAT) is a variation of the Boolean satisfiability problem (SAT). Given a variable order, LEXSAT finds a satisfying assignment whose integer value under the given variable order is minimum (maximum) among all satisfi ...

Assoc Computing Machinery2016

A 65k pixel, 150k frames-per-second camera with global gating and micro-lenses suitable for fluorescence lifetime imaging

Edoardo Charbon, Claudio Bruschini, Samuel Burri, Francesco Regazzoni, François Eric Powolny

This paper presents our work on a 65k pixel single-photon avalanche diode (SPAD) based imaging sensor realized in a 0.35 mu m standard CMOS process. At a resolution of 512 by 128 pixels the sensor is read out in 6.4ps to deliver over 150k monochrome frames ...

Spie-Int Soc Optical Engineering2014

A novel cmos image sensor with event/change detection and reduced data redundancy

Giovanni De Micheli, Sandro Carrara, Gözen Köklü

A Digital Pixel Sensor (DPS) based CMOS camera configured to record frames and comprising an event detection sensor configured to look for an event happening in a determined frame, comprising an array of event detection pixels, a first reference voltage ge ...

2014

Accelerating Spatial Range Queries

Anastasia Ailamaki, Thomas Heinis, Farhan Tauheed, Alexandros Stougiannis

It is increasingly common for domain scientists to use computational tools to build and simulate spatial models of the phenomena they are studying. The spatial models they build are more and more detailed as well as dense and are consequently difficult to ...

2013