数据流上的渐进式和近似连接算法解析

# 数据流上的渐进式和近似连接算法解析 ## 1. 高维距离 - 相似度连接 在处理高维数据时，已经提出了许多高效的距离相似度连接算法。为了实现高效的连接处理，这些算法通常依赖于空间索引，常见的有 R - 树（及其变体）、X - 树或 ε - kdb 树等。以下是一些具体的算法： - **多维空间连接（MSJ）**：基于数据的希尔伯特值对数据进行排序，并使用多路合并来获取结果。 - **Epsilon 网格顺序（EGO）**：根据网格单元的位置对数据对象进行排序。 - **K 近邻（KNN）**：Multi - page 索引（MUX）方法使用 R - 树来降低执行 KNN 连接的 CPU 和 I/O 成本。GORDER 则使用主成分分析（PCA）来识别关键维度，并使用网格对数据进行排序。 不过，传统的距离相似度连接算法存在一定的局限性，它们主要是为本地数据集设计的，因此无法逐步交付结果。 ## 2. 渐进式 XML 结构连接 有研究提出了大规模多查询连接处理（MMQJP）技术，用于处理多个 XML 数据流上的值连接。该技术包括 XPath 评估和连接处理两个阶段： 1. **XPath 评估阶段**：对 XML 数据流进行匹配，并将辅助信息作为关系存储在商业数据库管理系统（如 Microsoft SQL Server）中。 2. **连接处理阶段**：使用这些辅助信息来计算结果。 然而，MMQJP 只有在整个 XML 文档到达后才能交付结果，并且由于依赖商业 DBMS，它无法控制刷新策略。与之相比，另一种提出的技术可以在流式 XML 文档的部分内容到达时逐步交付结果。 此外，还有为 XQuery 提出的物理代数，它允许在查询计划中混合 XML 流操作符和传统的 XML 及关系操作符，便于定义流水线计划，但该工作未考虑内存管理问题。 ## 3. 通用渐进式连接框架 ### 3.1 构建模块 #### 3.1.1 数据结构 这里主要关注基于哈希的连接所使用的数据结构。虽然存在基于排序合并范式的渐进式连接算法，但它们无法快速交付初始结果，因为只有在用于排序的数据结构（如扫描区域）足够满时才能产生结果。 用于存储数据并支持连接算法的数据结构 D 必须具备以下属性： - **正确性**：确保产生的结果相对于所使用的连接谓词是正确的。 - **完整性**：确保能够产生完整的结果集。 理想情况下，数据结构应是最小化的，即确保在计算完整结果集时扫描的分区数量最少。 数据结构 D 将数据空间划分为大小相等的分区 Pi，通过分区函数 f 确定新数据对象 o 所属的分区。对于不同类型的数据，分区方式有所不同： | 数据类型 | 数据结构（DS） | 分区函数（f） | |I| | κ | | ---- | ---- | ---- | ---- | ---- | | 关系型 | 基于哈希的分区 | 取模 | 1 | 恒等 | | 空间型 | 二维网格 | 将每个对象插入与其相交的网格单元 | ≥1 | 恒等 | | 高维数据 | n 维网格 | 将每个对象插入其所在的网格单元 | 1 | 非恒等 | 此外，还引入了对应函数 κ，它将一个分区 P 映射到另一个数据流中需要扫描的分区集合。对于关系型和空间型数据，κ 通常是恒等对应，以避免冗余扫描。 #### 3.1.2 刷新策略 当内存满时，刷新策略决定将哪些元组刷新到磁盘。通用渐进式连接框架的目标是设计与数据模型无关的刷新策略，这样可以方便地将其应用于其他数据模型。而依赖输入数据分布和连接谓词类型的刷新策略则难以通用化。 ### 3.2 渐进式连接算法 考虑对通过不可预测网络从远程数据源传输的两个数据集 R 和 S 进行连接 J 的问题。目标是快速交付初始结果并确保高结果吞吐量。 通用渐进式连接算法的一般形式如下： ```plaintext Algorithm 1. Generic Progressive Join. 1: while ( !endOfStream(R) and !endOfStream(S) ) do 2: if ( isBlocked(R) and isBlocked(S) ) then 3: //Blocking Phase 4: ProcessUnJoinedData() 5: end if 6: //In-memory Phase 7: tuple t = select(R,S) 8: if ( t.src == R) then 9: DS.probe(t) 10: DR.insert(t) 11: else if (t.src == S) then 12: DR.probe(t) 13: DS.insert(t) 14: end if 15: end while 16: //Cleanup Phase 17: CleanUp() 18: return (Results tuples from t ```