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

Posted on Edited on In , Word count in article: 4.6k Reading time ≈ 17 mins.

课程: COMP5270 - Randomness, Probability, and Algorithms
学期: S1 2026
来源: Week 7 - Nearest Neighbours and dimensionality reduction, Week 7 - Tutorial 7 (Solutions)

Part 1: Tutorial 7 详细题解

Warm-up

Problem 1: 空间、 查询的 Nearest Neighbour

题目: 对 维 universe 给出一个 Nearest Neighbour data structure，空间 ，查询时间 ，并支持动态 Insert/Remove。

题解:

最直接的数据结构是：把集合 中所有点存在一个 linked list 或 array 中。

每个点需要 空间，若当前有 个点，总空间：

查询点 时，线性扫描所有 ：

  1. 计算 ；
  2. 维护当前最小距离；
  3. 返回距离最小的点。

课程假设一次距离计算需要 时间，所以扫描 个点的时间是：

Insert 可以把新点插入 list，若不检查重复，指针操作是 存储成本；如果要保持 set 语义并检查是否已存在，则需要扫描，。

Remove 要找到对应点再删除，最坏也要扫描：

本题用到的知识点:

  1. NN baseline：线性扫描。
  2. 存储一个 维点需要 。
  3. 距离计算成本乘以点数得到 query time。

Problem 2: 上 空间的 Nearest Neighbour

题目: 在 Hamming cube 上给出空间 、查询 且与 无关的数据结构，并支持 Insert/Remove。

题解:

因为 universe 是有限的：

可以开一个 bit array：

表示点 是否在 中。

Insert / Remove

把 -bit string 当作二进制下标：

  • Insert: ；
  • Remove: 。

若下标转换视为常数或 ，核心数组操作是 。

Query

朴素做法是遍历整个 array，找所有 的点并计算 Hamming distance。这样是 。

更贴合题目目标的做法：从 query 点 开始，在 Hamming cube 图上按 BFS 层搜索。

  • 第 0 层： 本身；
  • 第 1 层：与 相差 1 bit 的点；
  • 第 2 层：与 相差 2 bits 的点；
  • ...

第一次遇到 的点，它就是 nearest neighbour，因为 BFS 层数就是 Hamming distance。

总共最多访问 个点，所以查询：

空间：

本题用到的知识点:

  1. Hamming cube 可看作图，BFS 层等于 Hamming distance。
  2. Universe-indexed array 可以让 membership 操作常数时间。
  3. 与 无关，但在高维时不可承受。

Problem 3: Baby LSH 能不能用 Bloom filter 替代 hash table?

题目: 在 baby version of LSH 中，我们想要非常快的 lookup 且允许小概率失败。能否用 Bloom filter 替代 hash table？哪里失败？

题解:

不能直接替代。

原因是 baby ANN/LSH query 不只是回答“是否存在一个近邻”，而是要返回某个具体的点 ，并且保证：

Bloom filter 的问题是：它只存 bit，不存元素本身。

即使 Bloom filter 返回 yes，我们也只知道“可能有某个东西 hash 到这里”，但不知道那个候选点是谁，也没法计算距离验证：

此外 Bloom filter 还有 false positive，会让算法以为 bucket 里有候选点，但实际没有可返回的元素。

所以 baby LSH 需要 hash table 存储 colliding elements 或它们的 index，而不是只存 membership bit。

本题用到的知识点:

  1. ANN query 要返回点，而不仅是 membership。
  2. Bloom filter 不存元素本体。
  3. LSH 的 hash table bucket 需要保存候选点并做距离验证。

Problem Solving

Problem 4: 从 baby ANN 推到 general ANN

题目: 证明一个简化版 Theorem 39：若有固定半径 的 baby ANN data structure，则可用 个尺度解决 general ANN，其中

对 Hamming space，。

题解:

设：

因此：

1. 建多个尺度的数据结构

构造一组半径：

直到覆盖到 。

对每个 ，建立一个 baby ANN data structure。

2. 为什么从 开始?

若 query 的最近邻 满足：

则这样的点最多只有一个。

证明：若有两个不同点 都满足：

由 triangle inequality：

这与 是 中点对最小距离矛盾。

所以如果 baby structure 在半径 下找到距离至多 的点，它就是真实最近邻。

3. 为什么到 就够?

若最优距离：

则任取 ：

所以任意点都是 -approximate nearest neighbour。

4. 中间情况

若：

由于 是按 2 倍增长，存在相邻尺度 ：

用半径 的 baby structure，若存在点在距离 内，则返回某个 满足：

因此得到 -ANN。

5. 搜索方式

可以对尺度做 binary search / doubling search。总共 个尺度，所以空间和查询时间只多一个 因子。

本题用到的知识点:

  1. Baby ANN 是固定 scale 的 gap problem。
  2. 用 geometric grid 覆盖可能的 OPT。
  3. Triangle inequality 处理极小和极大 OPT。
  4. 从 scale reduction 损失一个常数因子。

Problem 5: Euclidean SimHash 的 LSH 分析

题目: 在单位球面上，取 ，定义

证明这是 Euclidean 情形的 LSH，并说明 sensitivity 。

题解:

假设 都是 unit vectors：

且：

随机向量 定义一个过原点的随机 hyperplane。 当且仅当 落在这个 hyperplane 两侧。

设 夹角为 。由于 Gaussian 方向旋转对称，随机 hyperplane 落在 之间的概率是：

因此碰撞概率：

由几何关系：

所以：

也可写成：

因此若距离不超过 ，碰撞概率至少：

若距离至少 ，碰撞概率最多：

于是这是一个 -LSH family。

当 很小时：

所以：

对应：

课程 solution 给出了更正式的 arcsin/log 不等式证明，结论是：

本题用到的知识点:

  1. Random hyperplane hashing。
  2. Gaussian 旋转不变性。
  3. Unit vectors 的距离与夹角关系：。
  4. LSH sensitivity 。

Problem 6: Jaccard distance 与 MinHash

题目: Universe 是 的所有子集，距离为 Jaccard distance：

对每个 permutation ，定义：

证明其为 LSH，并求参数。

题解:

a) Jaccard distance 是 metric，range 是

因为：

所以：

Reflexivity：

若 ，则 ，距离为 0。反过来，距离为 0 意味着 ，因此 。

Symmetry：

交并运算对称，所以：

Triangle inequality 的证明比较技术，核心是把目标：

化为集合大小不等式，再使用：

以及若干交并集乘积不等式。直觉上，Jaccard similarity

衡量共同部分占总出现部分的比例， 它给出合法 metric。

b) Hash family 的大小

每个 是 上的 permutation，所以：

存一个随机 permutation 需要约：

bits。

c) MinHash collision probability

对 ，考虑 中 值最小的元素。

  • 如果这个最小元素在 ，则 ；
  • 如果它在 ，则两个 hash 值不同。

由于 是 uniformly random permutation， 中每个元素等概率成为最小者。因此：

所以若：

则：

若：

则：

因此这是 -LSH，其中：

要求 才有非平凡意义。

sensitivity：

本题用到的知识点:

  1. Jaccard distance 与 Jaccard similarity。
  2. MinHash 的核心性质：collision probability 等于 Jaccard similarity。
  3. Uniform random permutation 下最小元素均匀分布。
  4. LSH 参数 。

Advanced

Problem 7: Euclidean NN 的 kd-tree

题目: 给出基于 kd-tree 的 Euclidean nearest neighbour data structure，并分析空间和 query time。

题解:

kd-tree 是一种递归空间划分结构。

构建

每个节点：

  1. 选择一个 split dimension，例如按深度轮流使用 ；
  2. 按该维坐标取 median point；
  3. 小于 median 的点放左子树，大于 median 的点放右子树；
  4. 递归构建。

每个点存一次，点本身占 ，所以空间：

若每层用 median 保持平衡，树高约 。

Query

查询点 时：

  1. 沿 split rule 走到叶子，得到一个初始 candidate；
  2. 回溯时维护当前 best distance；
  3. 对某个节点的另一侧子树，若 到 split hyperplane 的距离小于当前 best distance，则另一侧可能存在更近点，需要搜索；
  4. 否则可以剪枝。

时间复杂度

实践中，在低维或中等维数据上，kd-tree 常能显著剪枝，查询接近 。

但 worst-case 中，剪枝可能完全失效，需要访问所有节点：

这也是 high-dimensional nearest neighbour 的难点：维度变大后，空间划分结构容易退化。

本题用到的知识点:

  1. kd-tree 递归按坐标划分空间。
  2. 查询用 hyperplane distance 做 pruning。
  3. worst-case exact NN 仍可能线性扫描。
  4. 高维最近邻问题的 curse of dimensionality。

Part 2: Week 7 讲义知识点

0. 基础版导读：Nearest Neighbour 为什么难?

Week 7 的主题是 Nearest Neighbours and Dimensionality Reduction。最基本的问题是：

预处理一堆点 ，当 query point 来了，快速找出 中离 最近的点。

如果数据集中有 个点，每个点是 维，最朴素的方法是把 query 和每个点都算一次距离。一次距离计算通常是 ，所以查询时间是 。当 或 很大时，这太慢。

这周的核心思想是：为了更快，可以接受 approximation 和 随机失败概率。

Exact NN 和 ANN 的区别

Exact nearest neighbour 要求返回真正最近的点。

Approximate nearest neighbour (ANN) 放宽要求：如果真正最近距离是 ，算法返回的点距离可以不超过 ，其中 是 approximation factor。

很多讲义定义会先讨论一个 decision version：

  • near case：存在数据点 ，使得 。
  • far case：所有数据点 都满足 。

算法要能区分这两类情况，或者在 near case 找到一个足够近的点。

metric 是什么?

Nearest neighbour 依赖 distance。一个 distance function 如果是 metric，通常满足：

  1. 非负性：。
  2. 自反性： 当且仅当 。
  3. 对称性：。
  4. 三角不等式：。

这周常见距离：

  • Hamming distance：两个 bit strings 不同坐标的数量。
  • Euclidean distance： 距离。
  • Jaccard distance：。

三角不等式重要，是因为很多近邻算法都依赖“近的点在某种变换后仍然比较近”。

Johnson-Lindenstrauss Lemma 在做什么?

JL Lemma 解决的是高维问题。它说：对 个点，可以随机投影到较低维：

并且所有点对距离都近似保持：

初学时可以把它理解成：

如果只关心有限个点之间的相对距离，高维空间里很多方向是冗余的；随机投影到 维仍能保留距离结构。

ANN 中常见用法是先降维，再做近邻搜索。这样每次距离计算更便宜，数据结构也可能更小。

LSH 的核心直觉

Locality-Sensitive Hashing (LSH) 希望设计 hash function，让近点更容易 collision，远点不容易 collision。

形式上，一个 hash family 是 -sensitive，如果：

并且 。

单个 hash function 通常只给一点点区分能力。真正的算法要用 amplification。

AND/OR amplification

AND amplification 把多个 hash 拼起来：

两个点在 下 collision，必须在所有 下都 collision，所以概率变成：

这会显著降低远点 collision，也会降低近点 collision。

OR amplification 建多个独立 hash tables，只要有一个 table collision 就检查。若单个 table 成功概率是 ， 个 table 的成功概率是：

LSH 常用套路是：

  1. 用 AND 降低 false positives。
  2. 用 OR 把 near point 的成功概率拉回来。

Baby ANN 到 general ANN

Baby ANN 通常只处理一个固定尺度：区分距离 和 。真实 NN 不知道最近距离落在哪个尺度。

general ANN 的做法是建立多个尺度的数据结构：

最近距离总会落在某个相邻尺度之间，因此其中某个 baby structure 会适用。

三个常见 LSH 例子

Hamming LSH：

  • 随机选坐标 。
  • 。
  • 两个 bit strings collision 的概率等于相同坐标比例。

MinHash for Jaccard：

  • 对 universe 随机排列。
  • 是集合 在排列中最靠前的元素。
  • collision 概率为：

Euclidean random hyperplane：

  • 随机选一个过原点的 hyperplane。
  • 记录 在哪一侧。
  • 两个向量夹角越小，被分到同一侧的概率越高。

做题时怎么下手?

  • 问 NN 复杂度：先写需要存多少点，再写一次 query 计算多少个距离。
  • 问 ANN：明确 、、成功概率和返回点距离。
  • 问 JL：看是保留一个向量长度，还是保留所有 pairwise distances。
  • 问 LSH：先算 near collision，再算 far collision。
  • 问 amplification：AND 用 ，OR 用 。
  • 问 MinHash：关键事件是“排列最小的元素落在 中”。

1. Nearest Neighbour 与 Approximate Nearest Neighbour

NN 问题：

给定 metric space 和 dataset ，query 时返回：

ANN 放松为返回：

其中 是 approximation factor。

Exact NN 在高维下很难同时做到小空间和 sublinear query，所以课程转向 ANN。

2. 常见 metric

空间 距离
Euclidean :
Manhattan :
Hamming distance: 不同 bit 个数
subsets Jaccard distance

Metric 要满足：

  1. non-negative；
  2. identity of indiscernibles；
  3. symmetry；
  4. triangle inequality。

3. Johnson-Lindenstrauss Lemma

Distributional JL:

取随机 Gaussian matrix：

若：

则对固定 ：

以至少 概率成立。

对 个固定点做 union bound，可得经典 JL lemma：

即可同时保留所有 pairwise distances。

4. JL 在 ANN 中的作用

对 Euclidean data，先用 JL 把维度从 降到：

再在低维空间做 baseline NN。

得到：

  • 空间约 ；
  • 查询约 ；
  • 仍近似线性，但摆脱了原始 。

5. Locality-Sensitive Hashing (LSH)

一个 family 是 -LSH，如果：

若近：

若远：

其中 。

sensitivity:

越小越好。

6. LSH amplification

将 个 LSH 函数组成：

则：

  • 近点碰撞概率变为 ；
  • 远点碰撞概率变为 。

这样可以显著减少远点 false collisions。

再独立建 张表，提升找到近点的概率。

典型参数：

使：

而：

所以取：

7. Baby ANN data structure guarantee

在 下，baby ANN 用 LSH 可得：

指标 复杂度
Space
Expected query

因为 ，查询是 sublinear in 。

8. 从 baby ANN 到 general ANN

Baby ANN 固定一个半径 。General ANN 不知道 OPT 的距离，需要多个尺度：

在课程 theorem 中，可用 或 个尺度完成 reduction，approximation factor 多损失一个常数。

9. Hamming LSH

对 ，取：

随机选择一个 coordinate。

若 Hamming distance 是 ，碰撞概率是：

所以：

并且：

10. Euclidean LSH: random hyperplane

对 unit vectors：

其中 是 Gaussian random vector。

碰撞概率由夹角控制：

可得：

更高级构造可达到：

本周核心记忆

主题 关键结论
Exact NN baseline space/query
Hamming full array space/query
JL lemma 保留 点 pairwise distances
LSH definition 近点碰撞 ，远点碰撞
Sensitivity
LSH query expected
Hamming LSH random coordinate,
SimHash random hyperplane,
MinHash Jaccard collision probability = similarity