17. Succinct Structures I

Channel:MIT OpenCourseWare · Length:1:20:11 · Published:2013-12-18 · Views:16860

Watch on YouTube

Summary

Erik Demaine's MIT 6.851 Advanced Data Structures lecture introducing succinct data structures, covering rank, select and tries. It is part of the Spring 2012 course.

Why HN recommends it

HN recommends it as a clear, high-quality introduction to succinct data structures from a leading authority.

Erik Demaine [1] gave two good lectures on succinct data structures [2] in the 2012 MIT 6.851 Advanced Data Structures course — HN, 2018

Algorithms & data structures · University lectures & courses

Subtitles (excerpt)

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at osw.mit.edu. ERIK DEMAINE: All right. Today we start a new section of data structures. This is going to be two lectures long, so this week succinct data structures, where the goal is to get really small space. And first thing to do is to define what "small" means. Most succinct data structures are also static, although there are a few that are dynamic. We'll be focusing here on static data structures. And so in general, the name of the game is taking a data structure that you're familiar with-- we're going to talk about essentially two today. One is binary tries, which has the killer application of doing binary suffix trees in particular. So it could be a compressed try, whatever. But we'll assume hear the alphabet is binary. A lot of this has been generalized to larger alphabets. I'll tell you a little bit about that. But to keep it simple in lecture, I'm going to stick to a binary alphabet. And another data structure we're going to look at

On Hacker News

I'm most definitely not an expert in this area, but I have recently taken interest in learning about "succinct data structures", which from what I understand have their place in bioinformatics. It's been a challenging topic to learn about, because most of the information comes from Computer Science papers and articles where the information is presented in a very formal, mathematical way, which I … — denvaar, 2022-11
Is there a good applied overview of succinct data structures for programmers (non CS researchers)? Also I just started researching succinct dynamic graph data structures a few days ago and ended up on a very interesting paper if anyone is interested: [LINK] Will also add this, lecture introducing succinct data structures: [VIDEO] Ok last edit to this comment but I’m sure someone else will find th… — faizshah, 2021-09
Erik Demaine [1] gave two good lectures on succinct data structures [2] in the 2012 MIT 6.851 Advanced Data Structures course, and Rajeev Raman [3] just gave a tutorial on succinct data structures [4] at SIGMOD 2018. NB: SDSL Cheatsheet [LINK] [1] [LINK] [2] MIT 6.851 Succinct Structures I [VIDEO] II [LINK] [3] [LINK] [4] SIGMOD 2018 Tutorial: In-memory Representations of Databases via Succinct D… — espeed, 2018-10

Related videos