Data structure

Summary

In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficient access to data. More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data, i.e., it is an algebraic structure about data. Usage Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type. Different types of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, relational databases commonly use B-tree indexes for data retrieval, while compiler implementations usually use hash tables to look up identifiers. Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually,

Official source

https://en.wikipedia.org/wiki/Data_structure

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (100)

Related publications

Related people (97)

Related people

Related units (56)

Related units

Related concepts (104)

Related concepts

Related courses (100)

Related courses

Related lectures (357)

Related lectures

Related publications (100)

Efficient Data Structures for Decision Diagrams

Nacereddine Ouaret

Dynamic Programming OPtimization (DPOP) is an algorithm proposed for solving distributed constraint optimization problems. In this algorithm, Hypercubes are used as the format of the messages exchanged between the agents. Then, Hybrid-DPOP (H-DPOP), a hybrid algorithm based on DPOP was proposed as an improved solution. Its main advantage over DPOP lies under the use of Multi-valued Decision Diagrams (MDDs) instead of Hypercubes. Furthermore, MDDs give a more compact representation of the messages. The MDDs were implemented and presented in by Kumar even though it was presented as Constrained Decision Diagrams (CDD) which is a generalization of MDDs. The first part of this project aims at implementing Hypercubes. An Implementation already exists. Therefore, the goal is to propose an implementation which is more efficient in term of speed and memory usage for the already implemented functions (join, project and slice). The solution implemented during this project should also provide new functions (split and re-order) and the possibility of saving Hypercubes in the XML format. The second part of the project consists in proposing and implementing a data structure that is more efficient than the MDDs implemented in H-DPOP. This data structure should also provide more functions, and also provide the possibility of saving data in the XML format.

2008

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

Dynamic Programming Optimization (DPOP) is an algorithm proposed to solve distributed constraint optimization problems. In order to represent the multi-values functions manipulated in this algorithm, a data structure called Hypercube was implemented. A more efficient data structure, the Utility Diagram, was then proposed as an alternative to the Hypercube. DPOP also required the implementation of several operations (such as join, project, slice, split and reorder) on these two data structures. This project is a follow-up of Nacereddine Ouaret’s master thesis, which consisted in implementing all of these data structures and theirs associated operations. As DPOP may have to work on very large decision diagrams, and perform a lot of successive operations on them, having implementations which are efficient in term of speed and memory is critical. The aim of this project was therefore to seek for new ways to improve the already implemented functions for hypercubes and utility diagrams, both in term of execution time and memory consumption. This report will thus first present a quick overview of hypercubes, utility diagrams, and their associated operations (a more complete description of these objects, as well as the details about their original implementation, can be found in Nacereddine Ouaret’s report on Efficient Data Structures for Decision Diagrams). The second part will then cover various improvements made to their implementation during the course of this project. Finally, a variant for the methods used by hypercube, more economical in term of memory as it reuses existing hypercubes rather than creating new ones, will be presented.

2009

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