MIT OpenCourseWare
3 HN recommenders · recommended in 3 months, 2018–2022
1:20:11 · 17K views · Dec 18, 2013
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.
HN recommends it as a clear, high-quality introduction to succinct data structures from a leading authority.
3 comments from 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 am just not used to. Normally when thinking about data structures and algorithms, we're mostly concerned with optimizing for speed. Space complexity is not usually as big of a consideration. Succinct data structures are all about creating ways to achieve good runtime performance while representing the data in a "compressed" format. I think this comes in handy when doing things like DNA sequencing since data sets are so large. I'm excited to check out some of links in the post, and in case any one else is interested in learning more about succinct data structures, here's a few resources I'd recommend: Prof. Ben Langmead's YouTube channel: [LINK] Alex Bowe's blog has some good content: [LINK] Prof. Erik Demaine's "succinct" lectures from his adv. data structures course at MIT on YouTube: this video Edward Kmett's Haskell live coding session going into some details about succinct: [LINK] There's also a lot of research papers, which you should be able to find by searching for "succinct data structures" (Jacobson, Munro, Brodnik, Raman, Rao, Navaro, Sadakane just to name a few). I at least ha
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: this video Ok last edit to this comment but I’m sure someone else will find this useful. I also found a good book (haven’t read it yet, but it doesn't seem to have much code examples if any) that covers Succinct Graph data structures and also Succinct Dyanmic Data structures: [LINK]
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 this video II [LINK] [3] [LINK] [4] SIGMOD 2018 Tutorial: In-memory Representations of Databases via Succinct Data Structures [LINK]