COMP5270 Week 7 总结：Nearest Neighbours and Dimensionality Reduction（题解 + 知识点）

Posted on 2026-06-13 Edited on 2026-10-02 In Course Notes , COMP5270 Word count in article: 8.7k Reading time ≈ 32 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms 学期: S1 2026 来源: Week 7 Lecture Notes & Tutorial 7 Solutions

Part 1: Tutorial 7 详细题解

如果 metric space / ANN / LSH / JL Lemma 这些词还不熟，先看 Part 2 的名词速查，再回来读题解。

本部分按官方 Solutions PDF（Week 7 - Tutorial 7 (Solutions)）整理，每题先给完整题目，再逐步展开；所有结论与官方一致，比官方更细的推导步骤会标注【展开】。

Tutorial 难度总览

题目	所属部分	难度	复习时怎么安排
Problem 1	Warm-up	需读讲义，应该 doable	基础题：exact NN 线性扫描 baseline
Problem 2	Warm-up	需读讲义，应该 doable	基础题：Hamming cube 上空间换查询
Problem 3	Warm-up	需读讲义，应该 doable	概念题：Bloom filter 能否替代 hash table
Problem 4	Problem Solving	；important；tutorial 会讲	重点：baby ANN 推广到 general ANN
Problem 5	Problem Solving	recommended；最后的 bound 技术性强	推荐：Euclidean SimHash LSH 分析
Problem 6	Problem Solving	；quite technical and long	长难题：Jaccard 距离 / MinHash LSH
Problem 7	Advanced	有时间再做；not necessary	扩展：kd-tree

Problem 1: Exact NN 的链表实现，空间与查询

题目: 给出一个针对 Nearest Neighbour 问题的数据结构，使用的空间，并且 Query 运行时间为。同时说明它如何动态维护集合，Insert 和 Remove 各需要多少时间。

题解:

数据结构：简单链表

维护一个包含所有元素的简单链表（linked list），存储中的个元素，每个元素占空间，共空间。

各操作的时间复杂度

Insert(): 把新元素插入链表头，（拷贝/存储维向量）。

Remove(): 线性扫描整条链表找到然后删除，（也可先 Lookup 再删，）。

Query()（Nearest Neighbour 查询）:

初始化，
逐一扫描链表中每个，计算（每次）
若，更新和
扫描完后返回

共扫描个元素，每次，总计。

【展开】为什么这是一种 offline 的 baseline：讲义说"有两种基线方案，每种只满足空间或查询时间其中一项要求"。此方案实现的是"空间，查询 "——空间最优，但查询是线性时间，随增大查询会越来越慢。对应于讲义中 §Baseline 的第一个方案（Part 2 §2）。

Problem 2: Hamming Cube 上的位数组，空间与查询

题目: 给出一个针对上 Nearest Neighbour 问题的数据结构，使用空间，Query 运行时间为（与无关）。同时 Insert 和 Remove 各运行在。

题解:

数据结构：位数组（bit array）

用一个大小为的位数组，数组的每个位置对应中的一个字符串。初始所有位置置为。

Insert(): 令，。
Remove(): 令，。
空间: bits，即。

Query()：BFS 搜索

把看成一个超立方体图（hypercube），两个节点之间有边当且仅当它们的 Hamming 距离为（恰好一位不同）。从出发做BFS：

第层：本身（Hamming 距离）
第层：与相差一位的节点，共个
第层：与相差位的节点，共个

每次展开一层，检查该层所有节点中的节点。第一次找到则返回。

【展开】为什么 BFS 更好：朴素遍历整个数组需（每次要算距离）。BFS 的好处是：BFS 的层数对应 Hamming 距离，无需重复计算距离，只需次对数组的查询（最坏情况遍历所有节点），因此查询时间是。

【展开】权衡：这个方案是讲义中 §Baseline 的第二个方案（Part 2 §2）：空间，与无关，查询时间，也与无关。当非常大时空间会指数爆炸；当很小时非常好用。与 Problem 1 形成互补：Problem 1 是"空间依赖，查询依赖 "；Problem 2 是"空间/查询依赖，与无关"。

Problem 3: Bloom Filter 能否替代 Hash Table？

题目: 检查你的理解：既然我们想要高效查询并且愿意接受小概率失败，可以在 LSH 的"baby version"中用 Bloom filter 替代 hash table 吗？会出什么问题？

题解:

不能。原因是：

LSH 数据结构的 Query 操作不仅要回答" 中是否存在 -近邻"这个 yes/no 问题，还需要实际返回那个近邻元素（即一个具体的）。

但 Bloom filter 根本不存储元素本身——它只记录"某元素是否在集合中"的 membership bit。即使 Bloom filter 回答"有近邻"，我们也无法从它那里取出那个近邻是谁。

因此 Bloom filter 对于这里的查询语义是不够的，我们必须用能真正存储并返回元素的 hash table。这与 Week 6 中 Bloom filter vs hash table 的对比（Part 2 §12）完全一致：Bloom filter 用来做 membership，不能做 retrieval。

Problem 4: 从 baby ANN 到 general ANN（倍增搜索）

题目（标）: 证明一个简化版的 Theorem 39：利用"baby version"的 ANN 数据结构（只对固定参数工作）来解决"general" ANN 问题，代价是 aspect ratio

中的一个对数因子。

题解:

符号定义

设

设查询点的最优近邻为，最优距离。

算法

第一步：构造 threshold 列表

，因为从开始，每次翻倍，直到，共需步。

第二步：对每个，构建 baby ANN 数据结构。共构建个数据结构。

第三步：查询时对做二分搜索，找到合适的，用对应的 baby 数据结构回答。

为什么下界是？

命题: 对于任意查询点，中至多有一个点满足，且该点就是的最优近邻。

证明: 反设有两个不同的点满足且。由三角不等式：

矛盾。所以范围内至多只有一个点，且它就是最优近邻。

当时，用阈值的 baby 数据结构，会返回距至多的点，而该点正好是最优近邻。

为什么上界是？

命题: 若，则返回中任意一点，都满足（即 -近似仍然成立）。

证明: 设为任意点，为最优近邻，。由的定义，。因此：

中间情况的处理

若，则由的构造，存在使得。

用阈值的 baby 数据结构，会返回某个满足。

总结

无论落在哪里，算法总是返回一个 -近似的近邻。空间和查询时间各多出的因子（对应 Theorem 39 中和的开销，视参数而定）。

Problem 5: Euclidean SimHash 的 LSH 分析

题目: 分析讲义中针对 Euclidean 空间的 LSH family——对，，通过随机高斯向量定义：

证明对任意，这构成一个 -LSH family，且。

题解:

第一步：碰撞概率的几何解释

设均为单位向量，。

当且仅当和符号相反，即和在超平面两侧。

由于是高斯随机向量，这等价于：在由和张成的二维平面上，超平面的法向量的投影落在和之间的角（和它的补角）范围内。概率恰好是。

设为和之间的夹角，则：

第二步：从推出

由于，利用余弦定理：

所以，即。

利用三角恒等式（其中）：

第三步：确定

对于两点距离为（近）：

$碰撞不碰撞$

对于两点距离为（远）：

第四步：证明

【展开】当时，（Taylor 展开），所以：

因此。精确证明见下：

其中最后一步用到了函数在上非负递增且，所以，即。

这说明是 -LSH family，且。这就是 SimHash 方案。

Problem 6: Jaccard 距离与 MinHash LSH

题目: 设 universe 是的所有个子集，Jaccard 距离为：

对每个排列，定义为

以及（所有个排列对应的函数）。

(a) 验证 Jaccard 距离是度量。其范围是什么？

(b) 的大小是多少？

(c) 证明对任意和，是 -LSH family，其中，；计算。

题解:

(a) Jaccard 距离是度量

范围: 。因为，所以，即（对特别定义）。

验证三条公理：

自反性: 。反之，。

对称性: 和都是对称的，所以。

三角不等式: 需证，即

等价于：

【展开】证明使用以下三个辅助不等式（可由"画 Venn 图"验证）：

由：

再由：。

从而：

这正是我们要证的。

(b)

中每个函数对应的一个排列，共个。即，或者。

(c) MinHash 的 LSH 性质及

对任意，计算：

当且仅当，即在上取最小值的那个元素落在中（若落在或则两个最小值不同）。

对均匀随机排列，中哪个元素被映射到最小值是均匀随机的：

由此，对任意和：

若，则碰撞概率；
若，则碰撞概率。

所以是 -LSH family。

灵敏度参数 ：

【展开】当时，，，所以。

精确界：，其中单调递增，，所以。

因此这个 MinHash 方案的。

Problem 7: kd-Tree（Advanced，了解即可）

题目: 给出基于 kd-tree 的 Nearest Neighbour 数据结构，分析空间复杂度和查询时间。

简要说明:

kd-tree 是一种将递归二分的树形数据结构：每次选择一个坐标轴，用中位数将数据分成两半。空间复杂度（存个维点）。查询时间在最坏情况下是（高维时会退化），在低维时（固定）可以做到级别，但当很大时（高维诅咒）效果不好。这也是为什么讲义强调我们需要 ANN 而不是 exact NN——高维下 exact NN 本质上没有好的算法。

Part 2: 讲义知识点详解

按讲义（Week 7 - Nearest Neighbours and dimensionality reduction.pdf）结构整理，涵盖所有 Definition、Theorem、Lemma、Corollary 及其证明。

§0 名词与符号速查

符号	含义
	度量空间（metric space）
	数据集，
	宇宙（universe）的维数
	Nearest Neighbour（精确最近邻）
	Approximate Nearest Neighbour（近似最近邻），参数
	Johnson–Lindenstrauss，降维引理
	hash function family
-LSH	Locality-Sensitive Hash family，参数见 Definition 37.1
	LSH 灵敏度参数（sensitivity parameter），
	LSH 数据结构的两个关键参数（哈希表个数，每个 LSH 函数的复合层数）

§1 问题设定

1.1 度量空间与距离

以下是课程中常见的三种距离：

Manhattan 距离 ：，适用于。
Euclidean 距离 ：，适用于。
Hamming 距离：，适用于（两个位字符串不同位数的个数）。

度量（metric）需满足：

非负性: ，且
对称性:
三角不等式:

1.2 最近邻问题（NN Problem）

定义: 给定度量空间中的数据集，以及查询元素，输出

复杂度目标：

空间复杂度：理想目标（个维元素）。
查询时间：理想目标（次线性），或类的组合。

注意维度起的作用类似于 Week 6 中的角色——存储一个元素需要空间。

1.3 近似最近邻问题（ANN Problem）

定义: 参数。Query(x) 返回满足

当时退化为精确 NN。ANN 是"放松版"的 NN——接受比最优差不超过倍的答案。

Quiz 知识点： - 原题问 "对于这类应用，我们关心大维度和大数据集，其中通常_"，答案是 Much smaller than。ANN 场景中远小于，但精确 NN 在高维下有指数级下界。 - 原题问 "ANN 放宽 NN 的方式是_"，答案是 Allowing to return a point that might not be the closest to the query（允许返回可能不是最近的点）。这是 ANN 的核心思想：用近似换取查询效率。

§2 Baseline 数据结构

讲义给出两种朴素 baseline，各自满足空间/查询时间中的一项：

方案	空间	查询时间	关键思路
链表			线性扫描所有元素
位数组（Hamming）		（与无关）	BFS on hypercube

Quiz 知识点：原题问 " 维空间中精确最近邻查询的查询时间_，空间_"，答案是。链表方案同时满足这两个界，但都是线性的。

Quiz 知识点：原题问 "若点数是维度的指数级，精确最近邻算法的查询时间或空间复杂度随 ____"，答案是 Exponentially（指数级增长）。这是"维度诅咒"（curse of dimensionality）的直接体现。

坏消息：讲义指出，这两种 baseline 是目前已知的（甚至包括概率算法）所能做到的最好的——任何 NN 数据结构的空间或查询时间都至少是。这正是我们需要 ANN 的原因。

§3 Johnson–Lindenstrauss 降维引理

Theorem 37 (Distributional JL Lemma)

定理: 设，令

设随机矩阵，每个元素独立同分布。则对任意固定的：

直觉: 随机高斯矩阵把维向量映射到维，且以高概率几乎保持其长度（最多缩放）。只和与有关，完全不依赖原始维度 。

计算成本: 可在时间内生成（假设采样为常数时间）；计算需要时间。

Corollary 37.1 (JL Lemma)

推论: 设，，令

设如上。则对任意固定集合，：

证明思路: 对中所有对使用 union bound，对每对令，然后对 Theorem 37 取，从而，合并所有对的失败概率至多。

含义: 把个维点投影到维（为常数时就是维），所有对点之间的 Euclidean 距离都被保留，误差至多，以高概率成立。这是一个"免费的午餐"：原始维度不管多大，都可以压缩到！

Lemma 37.1: JL 对 ANN 的应用

引理: 对任意，存在一个（概率性的）ANN 数据结构（参数），空间，查询时间，每次查询正确概率至少。

证明思路: 对集合（注意是查询点，但我们在预处理阶段就把固定了，因为即使不知道也可以对所有可能的取 union bound）应用 Corollary 37.1，把投影到，。然后在中用 Problem 1 的链表做 baseline NN——查询时间变成，空间。距离被保留在内，所以链表找到的最近邻也是近似最近邻，。

局限: 查询时间仍然是，对仍然是近线性的，没有达到次线性的目标。LSH 才是真正获得次线性查询的方法。

JL 相关 Quiz 知识点： - 原题问 "JL 引理可精确保持个点的欧氏距离，只需维"（T/F），答案是 False。JL 引理是近似保持（失真），不是精确保持。 - 原题问 "JL 引理可近似保持距离，只需维"（T/F），答案是 False。目标维度是（与点数相关），不是。 - 原题问 "JL 引理可近似保持距离，只需维"（T/F），答案是 True。 - 原题问 "JL 引理可近似保持 Hamming 距离，只需维"（T/F），答案是 False。标准 JL 引理针对欧氏距离，适用于 Hamming 空间需要额外的技巧（如 embedding）。

§4 Locality-Sensitive Hashing（LSH）

Definition 37.1: LSH Family

定义: 设，，，为度量空间。函数族（从到）是 -Locality Sensitive Hash family（LSH），若对任意：

若（近），则；
若（远），则。

定义灵敏度参数（sensitivity parameter）：

直觉: 越大越好（近的元素更容易碰撞），越小越好（远的元素不容易碰撞）。是 LSH 能被利用的关键——它意味着近邻碰撞概率比远邻大得多。越小，数据结构的空间和查询时间越好。

Quiz 知识点：原题问 "LSH 使用一类使相近元素更可能碰撞的哈希函数"（T/F），答案是 True。这正是 LSH 的核心理念：碰撞概率随距离单调递减，使得相似的元素以更高概率被哈希到同一个桶。

Lemma 37.2: LSH Family 的复合

引理: 设是的 -LSH family，。对，定义

则由所有这样的组成的族是 -LSH family（灵敏度参数不变）。

证明: "写下来即得。" 对近点，个函数都碰撞的概率；对远点，至少一个函数碰撞的概率（等等，不对……其实是全部碰撞的概率，因为各独立）。

作用: 通过 -fold 复合，可以让变得任意小（减少"远点"的虚假碰撞），代价是也变小（"近点"发现率下降）。后面会用另一个参数（哈希表的个数）来弥补下降的问题。

§5 LSH 数据结构

数据结构描述

给定 -LSH family ，以及两个整数参数和：

预处理 Preprocess(S):

从中独立选取个函数
建立个 hash table ，使用 separate chaining，其中是普通的（好的）hash function
对所有，对所有：

查询 Query_r(x):

对所有：
- （与碰撞的元素列表）
对所有：
- 若，返回
返回（未找到）

为什么用两层 hash？

第一层 （LSH 函数）：locality-sensitive，让近邻碰撞，远邻不碰撞。但哈希的输出空间很大，直接存储不省空间。
第二层 （普通 hash 函数）：把的输出映射到合理大小的数组，保证空间效率（Week 6 的 universal hashing 保证）。

§6 LSH 数据结构的性能分析

Theorem 38: 数据结构保证

定理: 上述数据结构（设每个 LSH 函数计算耗时，每个 hash table 用空间）：

空间复杂度:
期望查询时间:
正确性: 若存在满足，则失败概率（Query_r(x) 返回）至多

证明要点:

空间: 个 hash table，每个；个 LSH 函数，每个存储 bits，共。

查询时间: - 计算个 LSH hash 值： - 对每个 hash table 中的元素检查距离（假设）：期望虚假碰撞次数为（每个远点在某个 hash table 中碰撞的期望次数），共个 hash table，总计 - 加上普通 hash table 的碰撞开销

正确性: - 若存在且，则对每个，的概率 - 所有个都没有碰撞的概率（只要足够大） - 第二个正确性条件（若所有点都则返回）由第 4 行的距离检查保证

参数设置

设定 : 令，即

则期望查询时间中的，虚假碰撞项消失。

此时（因为）。

Quiz 知识点：原题问 "用 LSH 可在 Hamming 和欧氏空间中解决 ANN，期望查询时间关于为_，空间为_"，答案是 sublinear / nearly linear。查询时间是次线性的（，），空间是近线性的。这是 LSH 相比 JL-ANN 方案的核心优势。

设定 : 正确性条件要求，即，取

Corollary 38.1: 最终性能

推论: 取上述参数（假设），数据结构性能为：

$空间期望查询时间$

这是次线性查询！因为，所以，查询时间次线性于，这正是我们的目标。代价只是空间比最优的多出因子，可以接受。

§7 从 baby ANN 到 general ANN

Theorem 39

定理: 若对每个，都有针对"baby version"的 ANN 数据结构（固定参数，近似参数），空间，查询时间，每次查询失败概率。则存在针对 general ANN 的数据结构（近似参数），空间，期望查询时间，每次查询失败概率。

简化版本（Tutorial Problem 4 给出）: 代价是 aspect ratio 的对数因子，近似参数变为。具体参见 Problem 4 题解的倍增搜索方案。

§8 Hamming 空间的 LSH Family

构造: 设 universe （Hamming 空间）。定义

即每个 hash 函数就是"取第位"，。

LSH 参数: 对任意，：

验证:

若（即最多位不同），则的概率（均匀随机位恰好命中不同的那位之一的概率是）
若，则碰撞概率

灵敏度参数:

（在的情形下近似。精确值已被证明是 Hamming 空间的最优值。）

§9 Euclidean 空间的 LSH Family（SimHash）

构造: 限制到单位向量，，。取随机高斯向量，定义：

LSH 参数 及 : 见 Problem 5 的详细推导。关键公式：

碰撞概率为。是 -LSH family，。

注: 对 Euclidean 空间，更复杂的构造可以达到，比更好。

§10 核心记忆卡片

名称	结论
NN Baseline 1（链表）	空间，查询
NN Baseline 2（位数组）	空间，查询，无关
NN 下界	任何 NN 方案：空间或查询
JL Lemma（Corollary 37.1）	个点投影到维，所有对距离误差，概率
JL 应用到 ANN	ANN，，空间和查询时间都是
LSH 定义（Def 37.1）	：近点碰撞概率，远点；
LSH 复合（Lemma 37.2）	-fold 复合得，不变
LSH 数据结构（Theorem 38）	空间，查询；正确性
参数设置	（令），
LSH 最终性能（Corollary 38.1）	空间，次线性查询
Hamming LSH	，，，
Euclidean SimHash	，
MinHash（Jaccard）	， $碰撞$ ，

Part 3: Week 7 Quiz 回顾

来源：Canvas Quiz，整理自 5270-questions-organized.md。每题含中英文题目、正确答案及知识点解析。

Question 1

[EN] We know how to solve the (exact) Nearest Neighbour question over a -dimensional space with query time ____ and space ____.

[CN] 维空间中的精确最近邻查询，查询时间_，空间_。

选项	答案
	❌
	✅
	❌
	❌

知识点：链表方案同时满足这两个界——线性扫描所有个维元素。

Question 2

[EN] Typically, for this type of applications we care about large dimension and large dataset , where is _____

[CN] 对于这类应用，我们关心大维度和大数据集，其中通常____。

选项	答案
Much larger than	❌
Equal to	❌
Much smaller than	✅
Comparable to	❌

知识点：ANN 场景中，但维度诅咒仍然让精确 NN 不可行。

Question 3

[EN] Suppose the number of points is huge: exponential in the dimension . The known algorithms for the (exact) Nearest Neighbour problem have query time or space complexity that scales ____ with the dimension .

[CN] 若点数是维度的指数级，精确最近邻算法的查询时间或空间复杂度随

选项	答案
Exponentially	✅
Logarithmically	❌
Linearly	❌

知识点：精确最近邻在高维下遭遇"维度诅咒"（curse of dimensionality），复杂度指数级增长。

Question 4

[EN] The Approximate Nearest Neighbour problem relaxes the Nearest Neighbour problem by...

[CN] 近似最近邻（ANN）放宽 NN 的方式是……

选项	答案
Allowing exponential space	❌
Allowing a probability of failure	❌
Allowing to return a point that might not be the closest to the query	✅

知识点：ANN 的核心妥协：允许返回不是最近邻的点，换取查询效率。

Question 5

[EN] The Johnson-Linderstrauss Lemma allows us to preserve exactly the Euclidean distances between points, but on a much smaller space of dimension only .

[CN] Johnson-Linderstrauss 引理可精确保持个点之间的欧氏距离，但只需维。

选项	答案
True	❌
False	✅

知识点：JL 引理是近似保持距离（失真），不是精确保持。

Question 6

[EN] The Johnson-Linderstrauss Lemma allows us to preserve approximately the Euclidean distances between points, but on a much smaller space of dimension only .

[CN] JL 引理可近似保持欧氏距离，只需维。

选项	答案
True	❌
False	✅

知识点：目标维度是（与点数相关），不是。这个是最常见的混淆点。

Question 7

[EN] The Johnson-Linderstrauss Lemma allows us to preserve approximately the Euclidean distances between points, but on a much smaller space of dimension only .

[CN] JL 引理可近似保持欧氏距离，只需维。

选项	答案
True	✅
False	❌

Question 8

[EN] The Johnson-Linderstrauss Lemma allows us to preserve approximately the Hamming distances between points, but on a much smaller space of dimension only .

[CN] JL 引理可近似保持 Hamming 距离，只需维。

选项	答案
False	✅
True	❌

知识点：标准 JL 引理针对欧氏距离。Hamming 距离需要在 Hamming cube 上嵌入到欧氏空间，或使用其他方法。

Question 9

[EN] Locality-Sensitive Hashing uses a type of hash functions which makes collisions more likely when hashing elements close to each other.

[CN] 局部敏感哈希（LSH）使用一类使相近元素更可能碰撞的哈希函数。

选项	答案
False	❌
True	✅

知识点：LSH 的核心理念——碰撞概率随距离单调递减。

Question 10

[EN] Using LSH, one can solve the ANN question in Hamming and Euclidean space with expected query time _____ in the number of points , and space _____ in .

[CN] 用 LSH 可在 Hamming 和欧氏空间中解决 ANN，期望查询时间关于为_，空间为_。

选项	答案
exponential/sublinear	❌
exponential/sublinear	❌
sublinear/sublinear	❌
sublinear/nearly linear	✅

知识点：LSH 实现次线性查询（，）加近线性空间（），这是它相较 JL-ANN 方案的核心优势。

Week 7 Quiz 速查表

题号	核心概念	正确答案
1	Exact NN 时间/空间
2	与的关系	Much smaller than
3	维度诅咒	Exponentially
4	ANN 放宽方式	Allows approximate answer
5	JL 精确保持	False（近似保持）
6	JL 只需	False（是）
7	JL 只需	True
8	JL 对 Hamming	False（仅欧氏距离）
9	LSH 碰撞性质	True（近邻更易碰撞）
10	LSH 查询/空间	sublinear / nearly linear

高频混淆点： - JL 维度是不是 （Q6 vs Q7） - JL 是近似保持不是精确保持（Q5） - JL 针对欧氏距离不是 Hamming（Q8） - ANN 用近似答案换查询效率（Q4），LSH 实现次线性查询（Q10）

Part 1: Tutorial 7 详细题解

Tutorial 难度总览

Problem 1: Exact NN 的链表实现， 空间与查询

数据结构：简单链表

各操作的时间复杂度

Problem 2: Hamming Cube 上的位数组， 空间与查询

数据结构：位数组（bit array）

Query()：BFS 搜索

Problem 3: Bloom Filter 能否替代 Hash Table？

Problem 4: 从 baby ANN 到 general ANN（倍增搜索）

符号定义

算法

为什么下界是 ？

为什么上界是 ？

中间情况的处理

总结

Problem 5: Euclidean SimHash 的 LSH 分析

第一步：碰撞概率的几何解释

第二步：从 推出

第三步：确定

第四步：证明

Problem 6: Jaccard 距离与 MinHash LSH

(a) Jaccard 距离是度量

(b)

(c) MinHash 的 LSH 性质及

Problem 7: kd-Tree（Advanced，了解即可）

Part 2: 讲义知识点详解

§0 名词与符号速查

§1 问题设定

1.1 度量空间与距离

1.2 最近邻问题（NN Problem）

1.3 近似最近邻问题（ANN Problem）

§2 Baseline 数据结构

§3 Johnson–Lindenstrauss 降维引理

Theorem 37 (Distributional JL Lemma)

Corollary 37.1 (JL Lemma)

Lemma 37.1: JL 对 ANN 的应用

§4 Locality-Sensitive Hashing（LSH）

Definition 37.1: LSH Family

Lemma 37.2: LSH Family 的复合

§5 LSH 数据结构

数据结构描述

§6 LSH 数据结构的性能分析

Theorem 38: 数据结构保证

参数设置

Corollary 38.1: 最终性能

§7 从 baby ANN 到 general ANN

Theorem 39

§8 Hamming 空间的 LSH Family

§9 Euclidean 空间的 LSH Family（SimHash）

§10 核心记忆卡片

Part 3: Week 7 Quiz 回顾

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Week 7 Quiz 速查表

Problem 1: Exact NN 的链表实现，空间与查询

Problem 2: Hamming Cube 上的位数组，空间与查询

为什么下界是？

为什么上界是？

第二步：从推出