作者：
Panagiotis Bouros ∗
Department of Computer Science
Aarhus University, Denmark
pbour@cs.au.dk
Nikos Mamoulis †
Dept. of Computer Science & Engineering
University of Ioannina, Greece
nikos@cs.uoi.gr
翻译：陈祥春
摘要
区间连接是在时间，空间和不确定数据库中查找应用程序的基本操作。尽管已经提出了许多用于区间连接的有效评估的集中式和分布式算法，但是经典平面扫描方法尚未被充分考虑。最近的一项相关工作提出了一种针对现代硬件的优化的基于平面扫描（PS）的方法，表明它大大优于以前的工作。然而，这种方法取决于复杂数据结构的发展，并且其并行化尚未得到充分研究。在本文中，我们探讨了一种基本上被忽略的前向扫描（FS）平面扫描算法的适用性，该算法非常简单。我们提出了两种FS优化方法，可以大大降低其成本，使其与最先进的单线程PS算法相比具有竞争力，同时实现更低的内存占用。此外，我们展示了先前提出的用于并行连接处理的基于散列的分区方法的缺点，并提出了一种不会产生重复结果的基于域的分区方法。在我们的方法中，我们建议将分区连接作业的新颖细分分解为少量独立的小型连接作业，这些作业具有不同的成本并且可以避免冗余的比较。最后，我们将展示如何在多个CPU内核中调度这些迷你连接，并提出自适应域分区，旨在实现负载平衡。我们包括一项实验研究，该研究证明了我们优化的FS的效率和我们的并行化框架的可扩展性。
1.介绍（INTRODUCTION）
给定1D离散或连续空间，定义间隔这个空间的起点和终点。 例如，给定空间所有非负整数N，两个整数start，end∈N，在start≤end的情况下，我们将一个区间i = [start，end]定为N的子集，其中包括所有整数x，其中start≤x≤end。设R，S为两个区间集合。 间隔连接R 1 S.由相互的所有间隔r∈R，s∈S定义，即r.start≤s.start≤r.end或s.start≤r.start≤s.end。区间连接是时态数据库中使用最广泛的运算符之一。一般而言，时态数据库存储符合模式的显式属性的关系，并且每个元组携带有效性间隔。在此上下文中，区间连接将从两个具有相交有效性的关系中找到元组对。例如，假设公司的员工可能在不同的时间段内在不同的部门工作。鉴于在A和B部门工作过的员工，间隔连接将识别成对的雇员，其在A和B中的工作时段分别受到关注。间隔连接也适用于其他域。在多维空间中，对象可以表示为空间填充曲线中的一组间隔。间隔对应于包含在对象中的曲线上的点的子序列。然后可以将空间连接减少到空间填充曲线表示中的间隔连接。通过在一个维度中找到交叉对（即，间隔连接）并在运行中验证另一维度中的交叉点，也可以处理由最小边界矩形（MBR）近似的对象集之间的空间连接的过滤步骤。 [1,3]。另一个应用是不确定的数据管理不确定值表示为间隔（可与置信度值配对）。因此，两个关系的不确定属性的等连接转换为区间连接。由于其广泛的适用性，已有相当多的关于区间连接的有效评估的研究。出奇，使用经典的平面扫描（PS）算法[20]还没有在之前的大部分时间里被认为是一种竞争方法工作。 2最近的一篇论文[18]实施并优化了一个版本PS（取自[1]），称为基于端点的间隔（EBI）加入。EBI对所有间隔（来自R和S）的端点进行排序然后扫描一条在每个已排序的端点处停止的线。如线扫描时，算法保持有效的间隔集从R和S开始，与线的当前停止点相交。当线路处于起始点（例如，从R）时的当前间隔被添加到相应的有效集（例如，A R）和有效集扫描另一个关系（例如，S的S）以形成连接对与当前间隔。当线路处于终点（例如，从R）时，相应的间隔从相应的间隔移除有效集（例如，A R）。[18]的工作集中在最小化由于活动集的更新和扫描引起的随机存储器访问。但是，另一种实现可以全面避免随机访问在[3]中在MBR（即空间）连接的背景下呈现的PS。我们称此版本为基于PS的前向扫描（FS）。简而言之，FS按起点的递增顺序扫描所有间隔。对于遇到每个间隔（例如，r∈R），FS向前扫描列表来自另一组的间隔（例如，S）。所有这些间隔都有r表格连接结束点r之前的起始点。它可以很容易证明FS（不包括排序）的成本是O（| R | +| S | + K），其中K是连接结果的数量。本文的贡献是双重的。在第4节，我们现在两个新的FS优化，大大减少了数量连接计算期间的比较。特别是优化FS以单个为代价批量生成多个连接元组比较。因此，我们实现了（i）竞争力的表现最先进的PS算法（EBI [18]），不使用任何特殊的硬件优化和（ii）更低的内存占用。我们的第二个贡献（第5节）是一个优化的框架用于并行处理基于平面扫描的算法。我们先显示[18]中建议的基于散列的分区框架没有充分利用并行性。我们的框架改为应用基于域的分区。我们首先表明，虽然应该在域分区中复制间隔以确保正确性，但是可以避免重复的结果，因此分区连接作业可以变得完全独立。然后，我们将展示如何将每个分区连接分解为五个具有不同成本的独立迷你连接作业。更重要的是，这些迷你连接中只有一个具有原始连接问题的复杂性，而其他连接具有明显更低的成本。我们展示如何将这些迷你连接安排到较少数量的CPU核心。此外，我们建议对数据采用自适应分裂方法领域，导致改善成本之间的平衡因此改进了小型的负载平衡连接。我们进行的实验表明我们基于域名分区框架通过数量实现理想的加速CPU核心，大大优于基于散列的分区[18]的框架。虽然我们的框架是独立的用于迷你连接的算法，我们展示了我们的优化版本与EBI相比，FS的sion更好地利用了它。本文的其余部分安排如下。第2节讨论相关工作，而第3节更详细地审查平面扫描方法; EBI [18]和原始FS [3]。在第4节中，我们支持为FS提出了两个新颖的优化，大大减少了算法的实际成本在实践中。第5节介绍了我们基于域的分区框架的并行间隔连接第6部分包括我们的实验评估，它展示了我们的优化对FS和我们的并行效率的影响区间连接框架。最后，第7节总结了论文。
原文：https://www.cnblogs.com/chenxiangchun/p/10860744.html