算法专场。
1.sigmod2024：Closest Pairs Search Over Data Stream
解决$KCP问题$：一个点集中，找到前k个NN（nearest neighbor）对。
bg：
术语。
| o | 对象 |
|---|---|
| S | 一个包含n个对象的d维流式数据集 |
| N(𝑜) | 对象𝑜的最近邻 |
| RNN(𝑜) | 对象𝑜的反向最近邻 |
| D(𝑜) | 𝑜与其最近邻的距离，也称对象𝑜的得分 |
| q(𝑜, 𝑟, 𝑆′) | 范围搜索，定位𝑆′中与𝑜距离在𝑟内的对象 |
| (𝑜, 𝑜′) | 由对象𝑜和𝑜′组成的对 |
传统kcp
大多数只支持1CP！
树形：
- c-box：首个确定性数据结构。维护MNN（相互的最近距离）。其他基本只处理1CP问题，并且包含较大的常数时间项。
- sota：R树（维护空间对象，不维护数据对象），M树（维护top-2k NN对），
区域分割：
- Random：对于1CP。随机选择pivot对象o，以D(o)递归分割直到只有两个成员，插入时通过算法评估。平均Ologn,最差On。很依赖pivot选择。
其他：
- 缓冲算法：使用滑动窗口支配关系支持KCP，在不能滑动的数据集（数据不会被自动淘汰，而是持续累积或静态存在的场景：静态数据集、累计数据流、批处理）受限。
- 倒排索引：基于TA（top-k问题）算法。成本高。
- “参照点”模型：随机选择参照点，计算普通点与参照点的距离，用三角形不等式来减小搜索范围。但很多情况不能找到参照点，最差On.
阈值驱动的连续空间查询
通过安全区域阈值过滤远端数据点。该方法利用时空相关性（相邻时刻位置变化微小）减少计算量。
例如：考虑移动方向的RIS-kNN、利用查询点知识的V*-diagram、多查询矩形安全区SRB，以及通过保护对象隐式计算安全区的算法。
这种查询关注查询点邻近数据，而KCP搜索聚焦小距离数据对。并且没考虑插入/过期对象时空关联。不适合KCP
insight
观察：
如果一个对象o的NN对不属于KCP,包含o所有的所有对也都不在考虑范围内.
对每个对象，找到它的k-NN，放入一个集合。则最终结果集必定是这个集合的子集。
这样就把搜索空间由$O(n^2)$ 降到 $O(k^2)$。
通过NNS空间限制搜索的示例
技术组建
QC-树
类似四叉树（quad-tree），但高度固定为𝑂(log 𝑛)，与数据分布无关。
叶节点存储对象与其最近邻的距离上界，支持基于预知搜索范围的高效最近邻查询。
局限：维护NNS的增量更新成本高，最坏情况下每次插入/删除需𝑂(𝑛)时间，难以适应数据流场景。
τ-DLBP分区策略
观察到：实际场景中，KCP查询的𝑘值通常远小于𝑛（即𝑘 << 𝑛），仅需维护少量高质量NN对（即距离最短的对）即可满足需求。
- 机制
- TNNS（基于阈值的最近邻对集合）：仅保留由参数𝜏控制的高质量NN对，减少维护开销。
- 动态分区：- 使用最多𝑂(log (𝑛/𝜏))个分区组织对象。
- 主分区：直接维护贡献于TNNS的对象。
- 辅助分区：基于对象与其最近邻的距离下界组织剩余对象，分区大小随距离下界增大呈指数级增长。
- 使用最多𝑂(log (𝑛/𝜏))个分区组织对象。
- TNNS（基于阈值的最近邻对集合）：仅保留由参数𝜏控制的高质量NN对，减少维护开销。
这样，单次更新成本降至$𝑂((𝑑 +3^𝑑) log (\frac{n}{𝜏}) + 𝜏)$，显著优于QC-Tree的𝑂(𝑛)。
查询时，若𝑘较小，仅需访问主分区；若𝑘较大，只需访问少数几个分区即可覆盖候选结果对。
技术路线
根据前面的insight提出的kcp搜索算法（基于nns）
nns构建方法-均等空间划分法
传统递归分割空间：在𝑑维空间0,1^𝑑中，递归将空间均分为2^𝑑个大小相等的超立方体（hypercube），构建四叉树（quad-tree）𝑇以组织对象。
每个超立方体由边长为$2^{-i}$的𝑑维立方体构成，其左下角坐标在各维度上为$2^{-i}$的整数倍。
局限性在于数据倾斜导致树不平衡：若对象密集分布于局部区域，均等划分生成的四叉树深度大，需多次分割才能分离密集对象，效率低下。
改进：基于中位数搜索的超立方体划分
思路是，对对象集，沿各维度j计算坐标中位数，根据中位数构造虚拟点，对每个对象和最近的虚拟点构建超立方体集C。
如果包含所有对象的最小超立方体的边长小于等于在C中的找到边长中位数x2，则均分空间；否则定义为密集超立方体。
这样保证了建树的平衡。
构建算法
- QC树索引结构建立
参考上图。
细节：动态分裂节点：若存在密集超立方体，创建子节点管理密集对象。构造叶节点时，若存在兄弟密集节点，调整超立方体边长为密集节点立方体的一半
与NNS结合
先最近邻搜索优化。
遍历QC-Tree，为每个对象𝑜找到其最近邻，生成所有NN对。
合并互近邻对（MNN）为单一记录。更新QC-Tree节点的𝑒.𝑚𝑎𝑥（节点对象集合最大得分）值，自底向上传播至根节点。
维护不细讲了。
- 部分最临近——维护！
在实际场景中，由于通常𝑘 ≪ 𝑛，无需维护所有最近邻对（NN pairs）即可高效回答KCP查询。本节提出一种通过维护少量高质量NN对（TNNS）并结合τ-DLBP分区策略实现高效KCP搜索的方法。
- 思路：基于阈值T的TNNS：
- 若|T| ≥ 𝑘，直接从中选取前𝑘个最小距离对作为结果。
- 若|T| < 𝑘，需借助τ-DLBP分区策略扩展搜索范围。
τ-DLBP分区策略
据集S划分为互斥分区，相邻分区的得分下界、分区规模指数递减。
再进行分数下界估计，基于得分下界重构分区。
写在后面：这篇文章写的很清楚，深入浅出，算法的提出也很自然。好评