17. Succinct Structures I
Channel:MIT OpenCourseWare · Length:1:20:11 · Published:2013-12-18 · Views:16860
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
- Rails World 2024 Opening Keynote - David Heinemeier Hansson · Ruby on Rails · 1:05:46
- Collapse of Complex Societies by Dr. Joseph Tainter · vlada888 · 1:33:25
- I Was SCARED To Say This To NASA... (But I said it anyway) - Smarter Every Day 293 · SmarterEveryDay · 1:05:19
- The Banach–Tarski Paradox · Vsauce · 24:13
- Salman Khan TED Talk 2011 (from ted.com) · Khan Academy · 20:27
- Lec 1 | MIT 6.042J Mathematics for Computer Science, Fall 2010 · MIT OpenCourseWare · 44:09
- Reading Silicon: How to Reverse Engineer Integrated Circuits · HACKADAY · 31:51
- Meaningful Play: Getting Gamification Right · Google TechTalks · 49:57
- Alan Kay - Programming and Scaling · Colin McDonnell · 56:38
- Times Tables, Mandelbrot and the Heart of Mathematics · Mathologer · 13:36
- Stanford Seminar: Beyond Floating Point: Next Generation Computer Arithmetic · Stanford Online · 1:31:28
- Your Brain at Work · Google TechTalks · 55:02
- Essence of linear algebra preview · 3Blue1Brown · 5:09
- Lower Latency Graph Queries in Cypher with Redis GraphRoi Lipman, Redis LabsTim Davis, Texas A&M U · Redis · 46:05
- How to Speak · MIT OpenCourseWare · 1:03:42
- 1. Introduction to Human Behavioral Biology · Stanford · 57:14