Publications related to Red–black tree

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

Michel Bierlaire, Nikola Obrenovic, Selin Ataç

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

2022

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

Demand-based operations of vehicle sharing systems

Selin Ataç

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

EPFL2023

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

Tree root distribution modelling in different environmental conditions

David Andrew Barry, Paolo Perona, Massimiliano Schwarz

The ability to predict the spatial distribution of tree root system variables (e.g., the Root system Area (RA), the maximum root diameter, the number of roots in diameter classes, the density of fine roots, etc.) under different environmental conditions is ...

2022

Feature-based no-reference video quality assessment using Extra Trees

Arash Amini, Hatef Otroshi Shahreza

With the emergence of social networks and improvements in the internet speed, the video data has become an ever-increasing portion of the global internet traffic. Besides the content, the quality of a video sequence is an important issue at the user end wh ...

WILEY2022

Improving Spatial Data Processing by Clipping Minimum Bounding Boxes

Anastasia Ailamaki, Darius Sidlauskas, Eleni Tzirita Zacharatou

The majority of spatial processing techniques rely heavily on the idea of approximating each group of spatial objects by their minimum bounding box (MBB). As each MBB is compact to store (requiring only two multi-dimensional points) and intersection tests ...

IEEE2018

A Two Phase Heuristic Approach For The Dynamic Electric Autonomous Dial-a-Ride Problem

Nikolaos Geroliminis, Claudia Bongiovanni, Mor Kaspi

In the Dial-a-Ride-Problem (DARP) a fleet of vehicles provide shared-ride services to users specifying their origin, destination, and preferred arrival time. In the dynamic version of the DARP, some trips are booked in advance while others come in real-tim ...

2018

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

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

Tropical soils degraded by slash-and-burn cultivation can be recultivated when amended with ashes and compost

Alexandre Buttler, Vincent Eric Jules Jassey, Bjorn Jozef Maria Robroek, Robert Thomas Edmund Mills, Justine Marie Gay des Combes, Muhammad Saleem Arif, Leia Soraya Véronique Falquet, Clara Sanz Carrillo

In many tropical regions, slash-and-burn agriculture is considered as a driver of deforestation; the forest is converted into agricultural land by cutting and burning the trees. However, the fields are abandoned after few years because of yield decrease an ...

Wiley2017

OLTP in Wonderland -- Where do cache misses come from in major OLTP components?

Anastasia Ailamaki, Pinar Tözün

For several decades, online transaction processing has been one of the main applications that drives innovations in the data management ecosystem, and in turn the database and computer architecture communities. Despite the novel approaches from industry an ...

ACM2013

A Speculation-Friendly Binary Search Tree

Vincent Gramoli

We introduce the first binary search tree algorithm designed for speculative executions. Prior to this work, tree structures were mainly designed for their pessimistic (non-speculative) accesses to have a bounded complexity. Researchers tried to evaluate t ...

Assoc Computing Machinery2012

A metric for phylogenetic trees based on matching

Bernard Moret, Yu Lin, Vaibhav Rajan

Comparing two or more phylogenetic trees is a fundamental task in computational biology. The simplest outcome of such a comparison is a pairwise measure of similarity, dissimilarity, or distance. A large number of such measures have been proposed, but so t ...

Springer Verlag2011

Automated Detection and Delineation of Tree Structures in Noisy Micrographs

Germán González Serrano

Despite more than a century of research, we still lack a concise description of the different types of neurons in the brain. This is a result of their large variance in morphology and the time consuming reconstruction process. In this thesis we design nove ...

EPFL2011

Complexity of stochastic branch and bound methods for belief tree search in Bayesian reinforcement learning

Christos Dimitrakakis

There has been a lot of recent work on Bayesian methods for reinforcement learning exhibiting near-optimal online performance. The main obstacle facing such methods is that in most problems of interest, the optimal solution involves planning in an infinite ...

2009

Complexity of stochastic branch and bound methods for belief tree search in Bayesian reinforcement learning

Christos Dimitrakakis

There has been a lot of recent work on Bayesian methods for reinforcement learning exhibiting near-optimal online performance. The main obstacle facing such methods is that in most problems of interest, the optimal solution involves planning in an infinite ...

2009

Subtree-based bounds and simulation-based estimations for the partition function

Mehdi Molkaraie

Many different algorithms developed in statistical physics, coding theory, signal processing, and artificial intelligence can be expressed by graphical models and solved (either exactly or approximately) with iterative message-passing algorithms on the mod ...

EPFL2007

Configurable Software Verification: Concretizing the Convergence of Model Checking and Program Analysis

Grégory Théoduloz, Dirk Thilo Beyer

In automatic software verification, we have observed a theoretical convergence of model checking and program analysis. In practice, however, model checkers are still mostly concerned with precision, e.g., the removal of spurious counterexamples; for this p ...

Springer2007

Service discovery, composition and execution for large scale open environments

Ion Constantinescu

In today's largest open environment, the World Wide Web, human-to-computer interactions are predominant. The natural evolution envisioned by many people is towards a Web in which the majority of interactions will be computer-to-computer. This has certain b ...

EPFL2006