Array (data structure) | EPFL Graph Search

In computer science, an array is a data structure consisting of a collection of elements (values or variables), of same memory size, each identified by at least one array index or key. An array is stored such that the position of each element can be computed from its index tuple by a mathematical formula. The simplest type of data structure is a linear array, also called one-dimensional array. For example, an array of ten 32-bit (4-byte) integer variables, with indices 0 through 9, may be stored as ten words at memory addresses 2000, 2004, 2008, ..., 2036, (in hexadecimal: 0x7D0, 0x7D4, 0x7D8, ..., 0x7F4) so that the element with index i has the address 2000 + (i × 4). The memory address of the first element of an array is called first address, foundation address, or base address. Because the mathematical concept of a matrix can be represented as a two-dimensional grid, two-dimensional arrays are also sometimes called "matrices". In some cases the term "vector" is used in computing

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has become extremely costly and inefficient, which motivates the study of sublinear algorithms. This thesis focuses on studying two fundamental graph problems in the sublinear regime. Furthermore, it presents a fast kernel density estimation algorithm and data structure. The first part of this thesis focuses on graph spectral sparsification in dynamic streams. Our algorithm achieves almost optimal runtime and space simultaneously in a single pass. Our method is based on a novel bucketing scheme that enables us to recover high effective resistance edges faster. This contribution presents a novel approach to the effective resistance embedding of the graph, using locality-sensitive hash functions, with possible further future applications.The second part of this thesis presents spanner construction results in the dynamic streams and the simultaneous communication models. First, we show how one can construct a

\tilde{O}(n^{2/3})

-spanner using the above-mentioned almost-optimal single-pass spectral sparsifier, resulting in the first single-pass algorithm for non-trivial spanner construction in the literature. Then, we generalize this result to constructing

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

, providing a smooth trade-off between distortion and memory complexity. Moreover, we study the simultaneous communication model and propose a novel protocol with low per player information. Also, we show how one can leverage more rounds of communication in this setting to achieve better distortion guarantees. Finally, in the third part of this thesis, we study the kernel density estimation problem. In this problem, given a kernel function, an input dataset imposes a kernel density on the space. The goal is to design fast and memory-efficient data structures that can output approximations to the kernel density at queried points. This thesis presents a data structure based on the classical near neighbor search and locality-sensitive hashing techniques that improves or matches the query time and space complexity for radial kernels considered in the literature. The approach is based on an implementation of (approximate) importance sampling for each distance range and then using near neighbor search algorithms to recover points from these distance ranges. Later, we show how to improve the runtime, using recent advances in the data-dependent near neighbor search data structures, for a class of radial kernels that includes the Gaussian kernel.

EPFL2022

Modélisation mécanique de fils pour la simulation chirurgicale

Lindo Robert Duratti

Minimally Invasive Surgery (MIS) represents one of the major progresses in surgery in the last decade. In general, it is based on the application of small body-cuts through which instruments are inserted into the patient's body allowing the surgeon to carry out their job. The advantages are numerous, mainly related to the patient's health, and economic advantages. The rather small size of the necessary cuts means a decreased risk of trauma and a faster recovery. It follows that hospitalization time and costs are reduced significantly. The conditions in which such surgery takes place are considerably different from traditional surgery. First of all, the extent to which the surgical instruments may be moved freely is reduced, as they have to pass through a fixed point. Then, visualisation of the surgery site takes place on a computer screen. In laparoscopy, the screen is connected to a micro-camera whereas in interventional radiology, an image created by x-rays is displayed on the screen. As more new surgical techniques are continuously invented, it is expected that these techniques can be practiced by the surgeons and, more importantly, preferred by patients. Amongst these surgical techniques, the suturing during laparoscopic surgery requires a certain skill in instrument handling to realize the required knots. In interventional radiology, during an angiography, the manipulation of the catheter requires a highly trained hand as the catheter has to pass through a complex, 3-dimensional network of blood vessels. The catheter is only visible when a radio-opaque marker is injected while the patient is under the emission of x-rays. Furthermore, such pictures are 2D. To help the surgeons to improve their abilities, we propose a haptic simulator to learn how to realize the knots for the suturing and a virtual environment for the angiography. For both training modules, we developed a model of filament based on the Cosserat theory applied to one-dimensional structures, which can describe the behaviour of a string as well as the behaviour of a rigid and flexible rod (catheter). This model starts from the energetic formulation of the filament considering the Hook laws of continuum mechanics. The Lagrange equations provide us with the equations of motion which describe the model deformation. This model takes collisions and auto-collisions into account and it is revealed to be very efficient for interactive applications. The training module dedicated to angiography permits to carry out the most usual gesture: beside the catheter navigation, a marker can be injected to visualize the vessels, to drive the balloon angioplasty towards the pathology and to set stents. Moreover, the visual rendering is very realistic and the heart beatings as well as breathing are also simulated.

EPFL2008

Replica Bit-Line Technique for Internal Refresh in Logic-Compatible Gain-Cell Embedded DRAM

Robert Giterman, Odem Harel

Embedded memories, mostly implemented with static random access memory (SRAM), dominate the area and power of integrated circuits. Gain-cell embedded DRAM (GC-eDRAM) is an alternative to SRAM due to its high density, low power consumption, and two-ported functionality. However, GC-eDRAM requires periodic refresh cycles to maintain its data due to its dynamic storage mechanism. The refresh operation is typically handled at a memory controller level, resulting in an energy overhead and limited memory availability. In this paper, we propose a new approach for the realization of the refresh operation using an internal refresh mechanism, which supports an efficient row-wise refresh operation within a single clock cycle, providing 100% write access availability at a reduced refresh latency and power. An 8 kbit GC-eDRAM array with integrated internal refresh and replica bit-line was implemented, demonstrating up-to 30% reduced refresh latency and 65% reduced read energy at a low cost of 2.4% array area overhead, compared to a conventional GC-eDRAM array without internal refresh capabilities.

ELSEVIER SCI LTD2020

Sketches, metrics and fast algorithms

Navid Nouri

\tilde{O}(n^{2/3})

\tilde{O}(n^{2/3(1-\alpha)})

-spanners using

\tilde{O}(n^{1+\alpha})

space for any

\alpha \in [0,1]

EPFL2022