Data Management Data Structures
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.
Details
| Code | 63112 |
| Type | Course |
| ECTS | 5 |
| Site | Fribourg |
| Track(s) |
T6 – Data Science |
| Semester | S2024 |
Teaching
| Learning Outcomes | Upon successful completion of this class, a student will be able to:
|
| Lecturer(s) |
Alberto Lerner |
| Language | english |
| Course Page | The course page in ILIAS can be found at https://ilias.unibe.ch/goto_ilias3_unibe_crs_2793415.html. |
Schedules and Rooms
| Period | Weekly |
| Schedule | Thursday, 14:15 - 17:00 |
| Location | UniFR, PER21 |
| Room | E230 |
Additional information
| Comment | First Lecture Pre-requisites Grading
|