Publications related to Search data structure

Automated Formal Verification of Software Network Functions

Formally verifying the correctness of software is necessary to merit the trust people put in software systems. Currently, formal verification requires human effort to prove that a piece of code matches its specification and code changes to improve verifiab ...

EPFL2024

Capturing Types

Martin Odersky, Aleksander Slawomir Boruch-Gruszecki, Ondrej Lhoták

Type systems usually characterize the shape of values but not their free variables. However, many desirable safety properties could be guaranteed if one knew the free variables captured by values. We describe CC

Assoc Computing Machinery2023

Fast correlation function calculator A high-performance pair-counting toolkit

Cheng Zhao

Context. A novel high-performance exact pair-counting toolkit called fast correlation function calculator (FCFC) is presented.Aims. With the rapid growth of modern cosmological datasets, the evaluation of correlation functions with observational and simula ...

EDP SCIENCES S A2023

Automated Verification of Network Function Binaries

George Candea, Solal Vincenzo Pirelli, Aikaterini Argyraki

Formally verifying the correctness of software network functions (NFs) is necessary for network reliability, yet existing techniques require full source code and mandate the use of specific data structures. We describe an automated technique to verify NF b ...

USENIX Association2022

Characterization and prediction of peptide structures on inorganic surfaces

Dmitrii Maksimov

Interfaces between peptides and metallic surfaces are the subject of great interest for possible use in technological and medicinal applications, mainly since organic systems present an extensive range of functionalities, are abundant, cheap, and exhibit l ...

EPFL2022

Benchmarking of objective quality metrics for point cloud compression

Touradj Ebrahimi, Davi Nachtigall Lazzarotto, Evangelos Alexiou

Point cloud is a promising imaging modality for the representation of 3D media. The vast volume of data associated with it requires efficient compression solutions, with lossy algorithms leading to larger bit-rate savings at the expense of visual impairmen ...

IEEE2021

Using an antenna as a tool for studying microturbulence and zonal structures in tokamaks with a global gyrokinetic GPU-enabled particle-in-cell code

Noé Thomas Elie Ohana

In order to get a better understanding of the interaction of plasma microinstabilities and associated turbulence with specific modes, an antenna is implemented in the global gyrokinetic Particle-In-Cell (PIC) code ORB5. It consists in applying an external ...

EPFL2020

Data stream statistics over sliding windows: How to summarize 150 Million updates per second on a single node

Odysseas Papapetrou, Grigorios Chrysos, Dionysios Pnevmatikatos

Traditional data management systems map information using centralized and static data structures. Modern applications need to process in real time datasets much larger than system memory. To achieve this, they use dynamic entities that are updated with str ...

2019

Fine-Grain Checkpointing with In-Cache-Line Logging

James Richard Larus, David Teksen Aksun, Nachshon Cohen

Non-Volatile Memory offers the possibility of implementing high-performance, durable data structures. However, achieving performance comparable to well-designed data structures in non-persistent (transient) memory is difficult, primarily because of the cos ...

ACM2019

Verifying Software Network Functions with No Verification Expertise

George Candea, Solal Vincenzo Pirelli, Rishabh Ramesh Iyer, Aikaterini Argyraki, Luis David Figueiredo Mascarenhas Moreira Pedrosa, Matteo Rizzo

We present the design and implementation of Vigor, a software stack and toolchain for building and running software network middleboxes that are guaranteed to be correct, while preserving competitive performance and developer productivity. Developers write ...

ACM2019

Mitsuba 2: A Retargetable Forward and Inverse Renderer

Wenzel Alban Jakob, Tizian Lucien Zeltner, Delio Aleardo Vicini, Merlin Eléazar Nimier-David

Modern rendering systems are confronted with a dauntingly large and growing set of requirements: in their pursuit of realism, physically based techniques must increasingly account for intricate properties of light, such as its spectral composition or polar ...

ASSOC COMPUTING MACHINERY2019

Algorithms for the implementation of adaptive isogeometric methods using hierarchical B-splines

Rafael Vazquez Hernandez

In this article we introduce all the ingredients to develop adaptive isogeometric methods based on hierarchical B-splines. In particular, we give precise definitions of local refinement and coarsening that, unlike previously existing methods, can be unders ...

Elsevier2018

Every data structure deserves lock-free memory reclamation

Nachshon Cohen

Memory-management support for lock-free data structures is well known to be a tough problem. Recent work has successfully reduced the overhead of such schemes. However, applying memory-management support to a data structure remains complex and, in many cas ...

2018

Log-Free Concurrent Data Structures

Rachid Guerraoui, Aleksandar Dragojevic, Mihail Igor Zablotchi, Tudor Alexandru David

Non-volatile RAM (NVRAM) makes it possible for data structures to tolerate transient failures, assuming however that programmers have designed these structures such that their consistency is preserved upon recovery. Previous ap- proaches are typically tran ...

USENIX Association2018

Log-Free Concurrent Data Structures

Rachid Guerraoui, Aleksandar Dragojevic, Mihail Igor Zablotchi, Tudor Alexandru David

Non-volatile RAM (NVRAM) makes it possible for data structures to tolerate transient failures, assuming however that programmers have designed these structures such that their consistency is preserved upon recovery. Previous approaches are typically transa ...

USENIX ASSOC2018

Sequential Proximity: Towards Provably Scalable Concurrent Search Algorithms

Rachid Guerraoui, Vasileios Trigonakis, Karolos Antoniadis, Julien Michel Stainer

Establishing the scalability of a concurrent algorithm a priori, before implementing and evaluating it on a concrete multi-core platform, seems difficult, if not impossible. In the context of search data structures however, according to all practical work ...

Springer International Publishing2017

On verifying causal consistency

Rachid Guerraoui, Jad Hamza

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

Concurrent Search Data Structures Can Be Blocking and Practically Wait-Free

Rachid Guerraoui, Tudor Alexandru David

We argue that there is virtually no practical situation in which one should seek a "theoretically wait-free" algorithm at the expense of a state-of-the-art blocking algorithm in the case of search data structures: blocking algorithms are simple, fast, and ...

ACM2016

Deductive Synthesis and Repair

Etienne Kneuss

In this thesis, we explore techniques for the development of recursive functional programs over unbounded domains that are proved correct according to their high-level specifications. We present algorithms for automatically synthesizing executable code, st ...

EPFL2016

Asynchronous memory access chaining

Babak Falsafi, Boris Robert Grot, Yusuf Onur Koçberber

In-memory databases rely on pointer-intensive data structures to quickly locate data in memory. A single lookup operation in such data structures often exhibits long-latency memory stalls due to dependent pointer dereferences. Hiding the memory latency by ...

2015