• Cudré-Mauroux Philippe

• Lerner Alberto

Data structures are often studied along algorithms but they are also essential for organizing data in database management and analytic systems.
In this class we look at fundamental families of data structures that aim at supporting efficient storage and retrieval tasks typical in the above systems.

The families of data structures in which we are interested, and the respective representative instances, are the following:
- Modern Hash-base Structure - This is an important class of structure for point access. We will look into open addressing (cuckoo, swiss table) and close addressing (TBD) options.
- Scalable Trees - These structures cover in addition range access and we study examples of compact/efficient trees such as radix tree (ART) and concurrent access structures such as range index (Masstree)
- Persistent Structures - There are structures that lend themselves well to be operated in-memory but that present a persistent component. We will study structures with In-place updates (B-link* tree) and append-only (Log-Structured Merge Trees)
- Probabilistic Structures - We look into the use of approximation techniques into data structures. In particular, we look into compact set membership  (Bloom Filter) and Approximate Balancing techniques (Skiplist).
- Compressed/Learned Structures - Similarly to approximation, compression also creates interesting possibilities. We look into lossless approaches in dictionary compression and lossy ones in learned Index (TBD).
Each of the five modules is comprised of two classes. There are two classes reserved for student projects presentations.

Upon successful completion of this class, a student will be able to:
- Identify and understand the criteria necessary to select the best data structure to organize a given data set
- Describe a wide array of data organization structures and enumerate their advantages and disadvantages
- Explain the different access methods that each data structure facilitates, along with their performance implications
- Write and analyze source code that implements the data structures

MSc-CS BENEFRI - (Code Ue: 63112/ Track: T6) The exact date and time of this course as well as the complete course list can be found at http://mcs.unibnf.ch/.