6.5230 高级数据结构

课程：MIT 6.5230 / 6.851 Advanced Data Structures · 讲师：Erik Demaine · 资料依据：官方讲义与课程录像

TL;DR

• 课程系统探讨超越传统比较模型的高级数据结构与计算复杂度下界理论，涵盖时序、几何、动态最优、存储层级、整数模型与简洁数据结构等前沿方向。
• 核心分析工具聚焦指针机模型、势函数摊还分析、信息论下界、单元探测下界（Cell Probe）以及跨多存储层级几何等价性。
• 系统建立从理论最优性（如动态最优性猜想、Tango 树、vEB 树、Jacobson 简洁表示）到工业存储感知的坚实理论桥梁。

先行条件

• 算法设计与分析（MIT 6.1210 / 6.046）：熟练掌握基础数据结构（平衡二叉树、堆、哈希表）、渐近复杂度分析、分治策略与图遍历。
• 离散数学与概率论：掌握基础组合数学、生成函数、期望与马尔可夫不等式。

课程简介与核心主题

数据结构在现代计算机科学与工程中扮演着决定性角色。面对海量数据和现代复杂硬件，简单的“对数时间”与“线性空间”已无法满足需求。本课程系统涵盖数据结构领域的经典成果与前沿研究：

1. 时序数据结构（Temporal Data Structures）：
   • 持久化（Persistence）：高效“记住过去”，在保留全部历史版本的同时以 $O(1)$ 额外开销支持跨版本查询与更新。
   • 回溯性（Retroactivity）：允许在历史时间线中插入或删除操作，并将因果影响传播至当前或未来。
2. 几何数据结构（Geometric Data Structures）：
   • 处理高维空间中的点定位与正交范围查询，运用扫描线（Line Sweep）降维与分数级联（Fractional Cascading）技术消除对数因子。
   • 运动数据结构（Kinetic Data Structures）：为连续运动物体建立基于“证书（Certificate）”的离散事件驱动维护机制。
3. 动态最优性（Dynamic Optimality）：
   • 探寻是否存在在任意访问序列上均能在常数因子内匹敌离线最优 BST 的在线算法。
   • 建立几何树形满足点集（ASSP）对偶模型，分析 Wilber 下界与首个 $O(\log\log n)$-竞争比的 Tango 树。
4. 存储层级与缓存无关模型（Memory Hierarchy & Cache-Oblivious）：
   • 摆脱平坦 RAM 假设，面向包含多级 Cache、主存与外存的物理现实。
   • 在无需硬编码硬件参数 $M$ 和 $B$ 的前提下，通过 van Emde Boas 空间填充递归布局、有序文件维护（OFM）和漏斗排序（Funnelsort），在所有存储层级之间同时达到最优 I/O 复杂度。
5. 整数数据结构（Integer Data Structures）：
   • 在 Transdichotomous Word RAM 模型下突破比较模型的 $\Omega(\log n)$ 下界。
   • 运用宇宙规模开方递归构建 van Emde Boas 树，结合两级间接寻址构建 x-fast 与 y-fast 树，实现 $O(\log w)$ 的前驱后继查询。
6. 简洁数据结构（Succinct Data Structures）：
   • 将存储空间压缩至信息论最优极限 $\text{OPT} + o(\text{OPT})$ 比特。
   • 运用 Jacobson 分块与四俄国人查表实现常数时间的 $\text{Rank}$ 与 $\text{Select}$，用 LOUDS 仅需 $2n + o(n)$ 比特即可编码并高效导航静态树。

课程大纲与讲义目录

模块一：时序数据结构（Temporal Data Structures）

• Lec 1 时序数据结构：持久化
  • 指针机模型、持久化的四个层级、修改日志与回指针、势函数摊还分析、版本树括号化与顺序维护、函数式路径复制
• Lec 2 回溯性数据结构
  • 部分回溯与完全回溯、可交换与可逆操作、可分解搜索问题与线段树、代数与单元探测下界、桥定理与倒 L 形几何图、非遗忘回溯性与射线射击

模块二：几何数据结构（Geometric Data Structures）

• Lec 3 几何数据结构：点定位、范围树与分数级联
  • 平面点定位、垂直射线射击、扫描线降维与部分持久化树、多维嵌套范围树、分数级联常数级传播、权重平衡树（$\text{BB}[\alpha]$）动态化重构
• Lec 4 三维范围搜索与运动数据结构
  • 射线刺穿查询、单侧到双侧区间分叉技术、三维正交范围搜索极限、KDS 四大评估准则（响应性、局部性、紧凑性、效率）、运动排序与运动二叉堆势函数分析

模块三：动态最优性（Dynamic Optimality）

• Lec 5 动态最优性：二叉搜索树的几何视角
  • BST 计算模型、解析性质谱系（顺序访问、静态最优性、工作集、动态手指、统一性质）、伸展树双旋机制、二维时空点集映射与树形满足性（ASSP）、贪心算法
• Lec 6 动态最优性：Wilber 下界与 Tango 树
  • 独立矩形下界、Wilber 1（交错下界 / Interleave Bound）与 Wilber 2（漏斗下界）、参考树拓扑、偏好路径划分、辅助红黑树、首个 $O(\log\log n)$-竞争比证明

模块四：存储层级与缓存无关算法（Memory Hierarchy & Cache-Oblivious）

• Lec 7 存储层级与缓存无关 B 树
  • 外存模型（DAM）与缓存无关模型、理想与高瘦缓存假定、经典 B 树与扫描/排序下界、静态 van Emde Boas 空间填充布局、OFM 与间接寻址结合
• Lec 8 有序文件维护、列表标号与缓存无关优先队列
  • 概念二叉树、深度相关的浮动密度阈值窗口、交错扫描重排、Dietz-Sleator 列表顺序维护两级间接寻址、缓存无关优先队列双指数多层双缓冲架构
• Lec 9 惰性漏斗排序与缓存无关正交二维范围搜索
  • $K$-漏斗缓冲区递归合并器、惰性驱动排序下界达成、分发扫描（Distribution Sweeping）批量几何检索、在线二侧查询密集/稀疏几何剥离、三侧与四侧范围树
• Lec 22 内存模型的历史演进
  • Floyd 两级模型与块概念、Hong & Kung 红蓝卵石游戏与矩阵乘法 I/O 下界、Aggarwal-Vitter DAM 模型确立、HMM/UMH 多级层级模型、Frigo 等人缓存无关模型思想革命

模块五：整数数据结构与前驱搜索（Integer Data Structures）

• Lec 11 整数数据结构：模型、前驱、vEB 树、x-fast 树与 y-fast 树
  • Transdichotomous Word RAM 模型、前驱问题定义、van Emde Boas 树宇宙规模开方递归与 Min/Max 隔离机制、x-fast 树层级哈希与树高二分查找、y-fast 树两级间接寻址达成最优时空

模块六：简洁数据结构（Succinct Data Structures）

• Lec 17 简洁数据结构：Rank、Select 与 LOUDS 树表示
  • 隐式、简洁与紧凑空间层次对比、位向量 $\text{Rank}$ 与 $\text{Select}$ 原语、Jacobson 大块/小块/四俄国人全局查表法、卡特兰数信息论下界、LOUDS 层序一元度数编码与常数时间无指针树导航

参考书目与经典文献

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms (4th Edition). MIT Press, 2022.
• Gonzalo Navarro. Compact Data Structures: A Practical Approach. Cambridge University Press, 2016.
• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry: Algorithms and Applications (3rd Edition). Springer, 2008.
• Robert Tarjan. Data Structures and Network Algorithms. SIAM, 1983.