矩阵相似性搜索的渐进式方法

### 矩阵相似性搜索的渐进式方法 #### 1. 渐进搜索算法 在矩阵的最近邻（NN）搜索中，采用了一种渐进搜索算法。该算法使用最小堆 `H` 来按条目下界距离的升序处理条目。`H` 包含两种类型的条目：候选条目和候选组。初始时，`H` 包含一个覆盖整个数据矩阵 `D` 的候选组条目。 搜索流程如下： 1. 从 `H` 中取出一个条目，检查它是候选组还是候选条目。 2. **如果是候选组 `G`**：将其均匀划分为 4 个候选组 `G1, G2, G3, G4`，计算每个 `Gi` 的组下界 `LB(q, Gi)`，然后将 `Gi` 重新加入 `H`。 3. **如果是候选条目 `c`**：计算下一级 `ℓ` 的候选下界 `LBlevel,ℓ(q, c)`，然后将 `c` 重新加入 `H`。 4. 当候选组只覆盖一个候选条目时，它会退化为候选条目；当候选条目达到最深级别时，直接应用精确距离函数 `dist(q, c)` 并更新到目前为止找到的最佳 NN 距离 `τbest`。 5. 当取出条目的下界超过 `τbest` 时，搜索终止。 以下是该搜索方法的流程图： ```mermaid graph TD; A[min - heap H] --> B[deheap an entry]; B --> C{Is it a group?}; C -- Yes --> D[Divide it into 4 groups]; D --> E[Apply LBgroup to these groups]; E --> F[Enheap them to H]; C -- No --> G[Apply LBlevel to it]; G --> H[Increment level]; H --> I[Enheap it to H]; I --> J{Reach the deepest level?}; J -- Yes --> K[Compute exact distance]; J -- No --> I; K --> L[Update τbest]; ``` 该算法使用的下界函数类型如下表所示： | 函数 | 应用对象 | 成本 | | ---- | ---- | ---- | | `LBbasic` (e.g., `LBΔ`, `LB⊕`) | 候选条目 | O(1) | | `LBlevel,ℓ` | 候选条目 | O(4ℓ) | | `LBgroup` | 候选组 | O(α) | #### 2. 候选条目的渐进过滤 为了节省昂贵的距离计算，提出了使用 `LBbasic` 作为构建块来构造参数化下界函数 `LBlevel,ℓ` 的通用思想。级别参数 `ℓ` 控制着 `LBlevel,ℓ` 中边界紧密度和计算时间之间的权衡。较小的 `ℓ` 计算时间短，而较大的 `ℓ` 提供更紧密的边界。 构建 `LBlevel,ℓ` 的方法是分治法，将空间 `[1..Lq, 1..Wq]` 划分为 `4ℓ` 个不相交的矩形 `{Rv : 1 ≤ v ≤ 4ℓ}`，在每个矩形 `Rv` 中应用 `LBbasic`，然后将这些 `4ℓ` 个下界距离组合成 `LBlevel,ℓ`： \[LB_{level,\ell}(q, c) = \sqrt[p]{\sum_{v = 1}^{4^{\ell}} LB_{basic}(q[R_v], c[R_v])^p}\] 最大可能级别 `ℓmax` 为： \[\ell_{max} = \lceil\log_2(\max\{L_q, W_q\})\rceil\] 可以证明 `LBlevel,ℓ` 满足下界属性，即对于任何候选条目 `c`，有 `LBlevel,ℓ(q, c) ≤ distp(q, c)`。 在搜索过程中，按 `ℓ` 的升序对候选条目应用 `LBlevel,ℓ`。如果在级别 `ℓ` 不能过滤 `c`，则尝试在级别 `ℓ + 1` 进行过滤。升序 `ℓ` 顺序的成本 `costorder` 满足 `costorder ≤ 4/3 · costopt`，其中 `costopt` 是最优成本。 #### 3. 候选组的渐进过滤 候选组 `G` 表示连续的候选条目区域，包含大小属性 `Lg` 和 `Wg` 以及起始位置 `(xstart, ystart)`。为了覆盖组中的所有候选条目，定义扩展区域 `G.Rext`。 引入了最小/最大 `Nq` 值的概念，定义了 `Nq min(G.Rext)`、`φmin(G.Rext)`、`φp min(G.Rext)` 及其最大值版本。 基于这些概念，提出了候选组的下界函数 `LB⊕ group` 和 `LBΔ group`： \[LB_{\oplus_{group}}(q, G) = \begin{cases} \sqrt[p]{N_q}(\varphi_{min}(G.R_{ext}) - \sum^*q) & \text{if } \varphi_{min}(G.R_{ext}) > \sum^*q \\ \sqrt[p]{N_q}(\sum^*q - \varphi_{max}(G.R_{ext})) & \text{if } \varphi_{max}(G.R_{ext}) < \sum^*q \\ 0 & \text{otherwise} \end{cases} \] \[LB_{\Delta_{group}}(q, G) = \begin{cases} \sqrt[p]{\varphi_{p_{min}}(G.R_{ext}) - \sum^*|q[i, j]|^p} & \text{if } \varphi_{p_{min}}(G.R_{ext}) > \sum^*|q[i, j]|^p \\ \sqrt[p]{\sum^*|q[i, j]|^p - \varphi_{p_{max}