2019年最快正版通天报

基于正向扫描的并行区间连接平面扫描算法(I

作者:admin 时间:2019-09-18

  区间连接是在时间,空间和不确定数据库中查找应用程序的基本操作。尽管已经提出了许多用于区间连接的有效评估的集中式和分布式算法,但是经典平面扫描方法尚未被充分考虑。最近的一项相关工作提出了一种针对现代硬件的优化的基于平面扫描(PS)的方法,表明它大大优于以前的工作。然而,这种方法取决于复杂数据结构的发展,并且其并行化尚未得到充分研究。在本文中,我们探讨了一种基本上被忽略的前向扫描(FS)平面扫描算法的适用性,该算法非常简单。我们提出了两种FS优化方法,可以大大降低其成本,使其与最先进的单线程PS算法相比具有竞争力,同时实现更低的内存占用。此外,我们展示了先前提出的用于并行连接处理的基于散列的分区方法的缺点,并提出了一种不会产生重复结果的基于域的分区方法。在我们的方法中,我们建议将分区连接作业的新颖细分分解为少量独立的小型连接作业,这些作业具有不同的成本并且可以避免冗余的比较。最后,我们将展示如何在多个CPU内核中调度这些迷你连接,并提出自适应域分区,旨在实现负载平衡。我们包括一项实验研究,该研究证明了我们优化的FS的效率和我们的并行化框架的可扩展性。

  给定1D离散或连续空间,定义间隔这个空间的起点和终点。 例如,给定空间所有非负整数N,两个整数start,endN,在startend的情况下,我们将一个区间i = [start,end]定为N的子集,其中包括所有整数x,其中startxend。设R,S为两个区间集合。 间隔连接R 1 S.由相互的所有间隔rR,sS定义,即r.starts.startr.end或s.startr.starts.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按起点的递增顺序扫描所有间隔。对于遇到每个间隔(例如,rR),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节总结了论文。

  在本节中,我们将回顾有关间隔连接的相关工作。 我们根据数据结构对先前工作的算法进行分类他们使用并基于底层架构。嵌套循环和合并连接。 早期的工作al加入[11,研究了时间连接问题,其中两个关系是等价的加入了非时间属性和时间重叠加入元组对也应该被识别。 Ť基于的技术嵌套循环(用于无序输入)和排序合并连接(用于或 -提出了dered输入专门的数据结构仅限附加数据库。 与平面扫描类似,合并连接但是,gorithms需要对两个输入集合进行排序,与FS相比,连接计算是次优的,这保证了至多 R + S 不产生结果的端点比较。基于索引的算法。 Enderle等人。 [8]提出间隔连接算法,在两个RI树[15]上运行,索引输入集合。 张等人。 [24]专注于发现成对的记录一个时间数据库,在(键)中相交,时间)空间(即a类似于[11,21]中研究的问题,提出了一个扩展多版本B树[2]。基于分区的算法。 一种基于分区的方法区间连接在[23]中提出。域被分成不相交的范围。 每个间隔都分配给对应的分区它重叠的最后一个域范围。域范围已处理顺序从最后到第一; 在最后一对分区之后已处理,与先前域范围重叠的间隔被迁移到下一个加入。这样就避免了数据复制。基于直方图的技术,用于定义良好的分区边界在[22]中提出。 更复杂的分区方法,称为重叠间隔分区(OIP)加入[7],划分了主要成为相同大小的颗粒和连续的颗粒分区的范围。 每个环节al被分配给分区对应于含有它的最小颗粒序列。在连接阶段,一个集合的分区与它们连接来自其他集合的重叠分区。OIP被证明与基于指数的方法相比更优越[8]和排序 -合并加入。这些结果与比较研究一致[9],表明基于分区的方法优于嵌套循环和合并连接方法。最近提出了不相交间隔分区(DIP)[4]时间连接和间隔数据的其他基于排序的操作(例如,时间聚合)。DIP背后的主要思想是划分每个将两个输入关系分成分区,例如每个分区仅包含不相交的间隔。然后是一个输入的每个分区加入了所有其他人。由于同一分区中的间隔可以不重叠,排序合并计算无需后退跟踪。 在此之前ork,时间聚合研究[17]。给定大间隔(可能与...相关)值),目标是计算聚合(例如,计算有效间隔)在所有时间点。 算法w如建议在[17]中将域划分为分区(桶),分配他们的第一个和最后一个桶的间隔verlap并结构间隔时间。然后可以处理聚合独立地为每个桶(例如,使用基于排序合并的ap-proach)并且算法可以在无共享中并行化建筑。 我们还提出了一种域分区方法然而,并行处(节同时间连接和聚合的不同性质。基于平面扫描的方法。 基于端点的间隔(EBI )加入(详见3.1节)及其懒惰版本LEBI 显示出明显优于OIP [7]并且也是如此优于另一个平面扫描实[1]。 一种方法类似于EBI用于SAP HANA [13]。 据我们所知,没有之前的工作与FS [3] 进行了比较(详见3.2节)。在第4节,我们提出两种新的优化为FS大大提高其性能,使其与LEBI竞争。并行算法。 基于域的分区策略在[16]中提出了多处理器机器上的terval连接。每个分区都分配给处理器并复制间隔到它们重叠的分区,以确保连接结果可以在每个处理器上独立生产。

  然而一个重复消除的合并阶段是需要的,因为相同的连接结果可以由不同的处理器产生。 我们的并行加入处理方法(第5节)也适用基于域的分区但不会产生重复。另外,我们提出了一个每个分区的细分连接到一组迷你连接作业,其中在以前的工作中从未考虑过。

  分布式算法。 DISTRIB区间连接评估是在[14]中学习。 目标是计算以下各组之间的连接 - tervals位于不同的客户。客户迭代地交换与服务器统计,帮助后者计算粗略的水平近似连接; 通过与客户的按需通信来改进确切的结果。Chawda等人 [5]实施在MapReduce框架中扩展了[16]的算法它用于其他(非重叠)连接谓词。分布式算法的主要目的是最小化通信成本在保存数据和计算连接的计算机之间。

  本节介绍平面扫描的必要背景基于区间连接的计算。 首先,我们详细介绍了EBI 算法[18]。 然后,我们重新开始查看基于前向扫描的算法从[3]中可以忽略以前的工作。两种方法作为输入两个间隔集合R 和S并计算所有(R,S )对(r R,s S ),其相交。 我们用r.start(r.end)表示间隔r的起始(结束)点。

  EBI [18]基于内存平面扫描技术[20],适合现代硬件。 算法1 说明了EBI的伪代码。EBI代表每个输入间隔,例如,r R ,通过形式 endpoint,type, id的两个元组,其中端点等于r.start或者r.end。结束,type 标志是否endpoint 是起始端点或结束端点,id 是r的标识符。这些元组存储在端点索引EIR和EIS,主要按其端点排序,其次按类型排序。 为了计算连接,EBI同时扫描端点索引,以增加排序键的全局顺序访问它们的元组,模拟从R的每个端点停止的“扫描线”或小号。 在扫描线的每个位置,EBI 跟踪扫描线已开始但尚未完成的间隔,即索引元组这是起始端点,其索引元组具有cor-响应结束端点尚未访问。这样的间隔被称为活动的,它们存储在集合A R和A S中 ; EBI根据当前的类型输入更新这些活动集dex元组(集合R的第10行和第14 行以及第19行和第23行)S )。 最后,对于ST ART 类型的当前索引元组(例如,e R ),该算法迭代相反的有效间隔 - 把收集(例如,一个小号 11-12线)产生下一个一堆结果(例如,间隔小号与加入 ř 。ID)。

  通过记录每个集合的活动间隔,EBI可以直接报告连接结果,而无需进行任何端点比较。为实现此目的,算法需要存储和扫描端点索引,这些索引包含与输入集合相比的两倍条目数。因此,排除EI R和EIS的分类成本,EBI总共进行2( R + S )端点比较以推进扫描线。但是,EBI的关键开销是在每个环路上维护和扫描有源集;即,第10行和第19行(添加),第11-12行和第20-21行(扫描),第14行和第23行(删除)。这个开销可能很高;例如,典型的哈希映射数据结构支持有效的O(1)更新,但扫描它们的内容很慢。为了解决这个问题,Piatov等人。设计了一个特殊的哈希表,称为无间隙哈希映射,它有效地支持所有三个insert,remove和getNext操作。最后,作者通过提出一种惰性评估技术进一步优化了连接计算,该技术缓冲了START类型的连续索引元组(因此,它们的相应间隔),只要它们源自相同的输入(例如,R)。当产生连接结果时,对整个缓冲器执行对相对集合的有效集合(例如,A S)的单次扫描。这个想法是由基于懒惰端点的间隔(LEBI)连接算法捕获的。通过将缓冲区大小保持足够小以适应L1高速缓存或甚至高速缓存寄存器,LEBI大大减少了主存储器高速缓存未命中,因此甚至更优于EBI。

  [18]中的实验表明LEBI 不仅表现优异EBI ,也是[1]的平面扫描算法,它直接扫描由起始端点排序的输入并跟踪活动链表中的间隔。 直观地说,两种方法都执行了向后扫描,即已经遇到的间隔的扫描,orga-由支持扫描和更新的数据结构确定。 在实践中然而,实施特殊结构的需要可能会受到限制适用性和采用这些评估方法同时还增加了对内存空间的要求。在[3]中,Brinkhoff等人。 提出了不同的实现平面扫描,直接在输入上执行正向扫描集合,因此,(i)没有必要跟踪活动设置一个特殊的数据结构和(ii)进行数据扫描quentially。3 算法2说明了这种方法的伪代码,由FS表示。 首先,两个输入集合都按开始排序每个区间的终点。 然后,FS 扫描一条线,停在那条线上按顺序排列R 和S的所有间隔的起始端点。 对于每一个3 该算法最初是为交叉连接而提出的。

  对于每一个扫描线的位置,对应于间隔的开始,比如rR,算法通过将r与来自相对集合的所有区间组合来产生连接结果,开始(i)在扫描线之后和(ii)在r.end之前,即所有s0S,其中r.starts0.startr.end(第7-10和13-16行的内部while循环))。 排除R和S的分类成本,FS进行 R + S + RXS 端点比较,总计。具体地,将每个间隔rR(S的情况是对称的)与仅仅一个s0S进行比较,其在第8-10行的循环中不与r相交。

  其中端点等于r。开始或者r。结束,typendpoint端点是起始或结束端点,id是标的[R。这些元组存储在端点索引中E内EIS,主要按其端点排序,其次按类型排序为了计算连接,同时扫描端点索引,EBI以增加排序键的全局顺序访问它们的元组模拟从每个端点停止的“扫描线”R的或小号。在扫描线的每个位置,EBI跟已开始但尚未完成的间隔,即索引元组这是起始端点,其索引元组具有cor-响应结束端点尚未访问。这样的间隔被称为活动的,它们存储在集合AR和A根据的更新这些活动集当前类型输入dex元组(集合第10行和第14行以及R的S)。最后,对于START类型的当前该算法迭代相反的有效间隔-把收集(例如,11-12线)产生一个小号结果(例如,间隔与加入)。小号ř。ID通过记录每个集合的活动间隔,可EBI直接报告连接结果,无需进行任何端点比要实现在此,算法需要存储和扫描端点索引包含两倍的条目数量

  从R)开始,相应的间隔从相应的间隔中移除 有效集(例如,A R )。 [18]的工作重点是最小化随机记忆 由于活动集的更新和扫描而进行的访问。 然而, 另一种实现可以总体上避免随机访问 PS中的PS,在[3]中在MBR(即空间)连接的背景下呈现。 我们称此版本为基于PS的前向扫描(FS)。 简而言之,FS 按起点的递增顺序扫描所有间隔。 对于 遇到每个间隔(例如,rR),FS向前扫描列表 来自另一组的间隔(例如,S)。 所有这些间隔都有 r表格连接结束点r之前的起始点。 它可以 很容易证明FS(不包括排序)的成本是O( R + S + K),其中K是连接结果的数量。 本文的贡献是双重的。 在第4节,我们提出 两个新的FS优化,大大减少了数量 连接计算期间的比较。 特别是优化 FS以单个为代价批量生成多个连接元组 比较。 因此,我们实现了(i)竞争力的表现 最先进的PS算法(EBI [18]),不使用任何特殊的 硬件优化和(ii)更低的内存占用。 我们的第二个贡献(第5节)是一个优化的框架 用于并行处理基于平面扫描的算法。 我们先 显示[18]中建议的基于散列的分区框架 没有充分利用并行性。 我们的框架, 改为使用基于域的分区。 我们首先证明了 虽然间隔应该在域分区中复制到 确保正确性,可以避免重复的结果,因此 分区连接作业可以完全独立。 然后我们 展示如何将每个分区连接分解成五个独立的 迷你连接工作,成本各异。 更重要的是,只有 其中一个迷你连接具有原始连接问题的复杂性 lem,而其他人的成本要低得多。 我们展示如何 将这些迷你连接安排到较少数量的CPU核心。 此外,我们建议对数据采用自适应分裂方法 领域,导致改善成本之间的平衡 因此改进了小型的负载平衡 连接。 我们进行的实验表明我们基于域名 分区框架通过数量实现理想的加速 CPU核心,大大优于基于散列的分区 [18]的框架。 虽然我们的框架是独立的 用于迷你连接的算法,我们展示了我们的优化版本 与EBI相比,FS的sion更好地利用了它。 本文的其余部分安排如下。 第2节讨论 相关工作,而第3节更详细地审查平面扫描 方法; EBI [18]和原始FS [3]。 在第4节中,我们支持 为FS提出了两个新颖的优化,大大减少了 算法的实际成本在实践中。 第5节介绍了我们的 用于并行间隔连接的基于域的分区框架。 仲- 第6部分包括我们的实验评估,它展示了 我们的优化对FS和我们的并行效率的影响 区间连接框架。 最后,第7节总结了论文。 2.相关工作 在本节中,我们将回顾有关间隔连接的相关工作。 我们 根据数据结构对先前工作的算法进行分类 他们使用并基于底层架构。 嵌套循环和合并连接。 关于区间连接的早期工作[11, 研究了一个时间连接问题,其中两个关系是等价的 加入了非时间属性和时间重叠 加入元组对也应该被识别出来。 基于的技术 嵌套循环(用于无序输入)和排序合并连接(用于或 - 提出了dered输入)以及专门的数据结构 仅限附加数据库。 与平面扫描类似,合并连接 gorithms要求对两个输入集合进行排序,但是, 与FS相比,连接计算是次优的,这保证了 最多 R + S 不产生结果的端点比较。 基于索引的算法。 Enderle等人。 [8]提出间隔连接 算法,在两个RI树[15]上运行,索引输入 集合。 张等人。 [24]专注于寻找成对的记录 在(密钥,时间)空间中交叉的时间数据库(即,a 类似于[11,21]中研究的问题,提出了一个扩展 多版本B树[2]。 基于分区的算法。 一种基于分区的方法 区间连接在[23]中提出。 域被分成不相交的 范围。 每个间隔都分配给对应的分区 它重叠的最后一个域范围。 域范围已处理 顺序从最后到第一; 在最后一对分区之后 已处理,与先前域范围重叠的间隔 迁移到下一个联接。 这样就避免了数据复制。 用于定义良好分区边界的基于直方图的技术 在[22]中提出。 更复杂的分区方法, 称为重叠间隔分区(OIP)加入[7],划分了 主要成为相同大小的颗粒和连续的颗粒定义 分区的范围。 每个间隔都分配给分区 对应于含有它的最小颗粒序列。 在连接阶段,一个集合的分区与它们连接 来自其他集合的重叠分区。 展示了OIP 与基于指数的方法相比更优越[8]和排序 - 合并加入。 这些结果与比较研究一致 [9],表明基于分区的方法优于 嵌套循环和合并连接方法。 最近提出了不相交间隔分区(DIP)[4] 时间连接和间隔数据的其他基于排序的操作(例如, 时间聚合)。 DIP背后的主要思想是划分每个 将两个输入关系分成分区,例如每个分区 仅包含不相交的间隔。 然后是一个输入的每个分区 加入了所有其他人。 由于同一分区中的间隔可以 不重叠,排序合并计算无需后退 跟踪。 在这项工作之前,研究了时间聚合 [17]。 给定大量间隔(可能与...相关) 值),目标是计算聚合(例如,计算 有效间隔)在所有时间点。 提出了一种算法 在[17]中将域划分为分区(桶),分配 它们重叠和保持的第一个和最后一个桶的间隔 用于桶的聚合的元数组结构 间隔时间。 然后可以处理聚合 独立地为每个桶(例如,使用基于排序合并的ap- proach)并且算法可以在无共享中并行化 建筑。 我们还提出了一种域分区方法 然而,并行处理(第5节)的细节因不同而不同 时间连接和聚合的不同性质。 基于平面扫描的方法。 基于端点的间隔 (EBI)加入(详见3.1节)及其懒惰版本 LEBI显示出明显优于OIP [7]并且也是如此 优于另一个平面扫描实现[1]。 一种方法 类似于EBI用于SAP HANA [13]。 据我们所知,没有 之前的工作与FS [3]进行了比较(详见3.2节)。 在 第4节,我们提出了两个对FS的新颖优化 提高其性能,使其与LEBI竞争。 并行算法。 基于域的分区策略 在[16]中提出了多处理器机器上的terval连接。 每个分区都分配给处理器并复制间隔 到它们重叠的分区,以确保连接结果可以 在每个处理器上独立生产。 但是,合并 1347

  算法1:基于端点的间隔(EBI)加入 输入 :间隔R和S的集合 产量 :设置所有交叉区间对的J(r,s)R×S 变量 :端点索引EI R和EI S ,活动间隔设置A R和A S. 1 J,A R ,A S ; 2 构建EI R 和EI S ; 3 首先按端点 排序EI R 和EI S ,然后按类型 排序 ; 4 e R EI R中的第一个索引元组 ; 5 E S EI S中的第一个索引元组 ; 6 虽然EI R 和EI S 没有耗尽 7 如果e R e S则 8 如果e R .type = ST ART那么 9 R中的区间,标识符为e R .id; 10 将r加到A R ; ⊳r是开放的 11 的foreach小号A S做 12 JJ⋃{(r,s)}; ⊳更新结果 13 其他 14 从A R中 删除r ; ⊳不再开放 15 e R EI R中的下一个索引元组; 16 其他 17 如果e S .type = ST ART那么 18 S中的s区间,标识符为e S .id; 19 将s添加到A S ; ⊳是开放的 20 的foreachřA R DO 21 JJ⋃{(r,s)}; ⊳更新结果 22 其他 23 从A S中 移除s ; 不再开放了 24 e S EI S中的下一个索引元组; 25 返回J. 需要重复消除的阶段,因为相同的连接 结果可以由不同的处理器产生。 我们的并行加入 处理方法(第5节)也适用基于域的分区 但不会产生重复。 另外,我们提出了一个 每个分区的细分连接到一组迷你连接作业,其中 在以前的工作中从未考虑过。 分布式算法。 分布式区间连接评估是 在[14]中学习。 目标是计算以下各组之间的连接 - tervals位于不同的客户。 客户迭代地交换 与服务器统计,帮助后者计算粗略的 水平近似连接; 按需提供的精确结果 与客户沟通。 Chawda等人。 [5]实施 在MapReduce框架中扩展了[16]的算法 它用于其他(非重叠)连接谓词。 主要目标 分布式算法的目的是最小化通信成本 在保存数据和计算连接的计算机之间。 3.间隔加入的平面扫描 本节介绍平面扫描的必要背景 基于区间连接的计算。 首先,我们详细说明了EBI gorithm [18]。 然后,我们回顾了基于前向扫描的算法 从[3]中可以忽略以前的工作。 两种方法 ods作为输入两个间隔集合R和S并计算所有 (r,s)对(rR,sS),它们相交。 我们用r.start表示 (r.end)间隔r的起始(结束)点。 3.1基于端点的间隔连接 EBI [18]基于内存平面扫描技术 - [20],适合现代硬件。 算法1 illus- 记录EBI的伪代码。 EBI代表每个输入间隔, 例如,rR,由endpoint,type,id形式的两个元组组成, 其中endpoint等于r.start或r.end,键入flags是否 endpoint是起始端点或结束端点,id是标识符 的 这些元组存储在端点索引EI R和 EI S ,主要按其端点排序,其次按类型排序。 为了计算连接,EBI同时扫描端点索引, 以增加排序键的全局顺序访问它们的元组, 模拟从R的每个端点停止的“扫描线” 在扫描线的每个位置,EBI跟踪扫描线 已经开始但尚未完成的间隔,即索引元组 这是起始端点,其索引元组具有cor- 尚未访问响应端点。 这样的间隔 被称为活动的,它们存储在集合A R和A S中 ; EBI 根据当前的类型输入更新这些活动集 dex元组(集合R的第10行和第14行以及第19行和第23行) S)。 最后,对于 START类型的当前索引元组(例如,e R ), 该算法迭代相反的有效间隔 - 把收集(例如,11-12线A S)产生下一个一堆 结果(例如,与e R .id 连接的S的间隔 )。 通过记录每个集合的活动间隔,EBI可以 直接报告连接结果,无需进行任何端点比较。 为此,算法需要存储和扫描端点 索引包含两倍的条目数量 输入集合。 因此排除了EI R和E的分拣成本 EI S ,EBI进行2( R + S )端点比较以推进 扫描线,总计。 但是,EBI的关键开销是 在每个循环中维护和扫描活动集; 即 第10行和第19行(添加),第11-12行和第20-21行(扫描),第14行和第14行 23(删除)。 这个开销可能很高; 例如,典型的 哈希映射数据结构支持有效的O(1)更新,但扫描 - 他们的内容很慢。 为了解决这个问题,Piatov等人。 去 签署了一个特殊的哈希表,称为无间隙哈希映射,其中ef- 非常支持所有三个插入,删除和getNext oper- ations。 最后,作者进一步优化了连接计算 通过提出一种懒惰的评估技术来缓冲 START类型的索引元组(因此,它们对应的 间隔)只要它们来自相同的输入(例如,R)。 生成连接结果时,对活动集进行单次扫描 对整个缓冲区执行相反的集合(例如,A S )。 基于懒惰端点的间隔(LEBI)捕获了这个想法 加入算法。 通过保持缓冲区大小足够小以适应 L1缓存甚至在缓存寄存器中,LEBI大大降低了主要功能 内存缓存未命中,因此,甚至超过EBI。 3.2基于正向扫描的平面扫描 [18]中的实验表明LEBI不仅表现优异 EBI,也是[1]的平面扫描算法,它直接扫描 由起始端点排序的输入并跟踪活动 链表中的间隔。 直观地说,两种方法都执行了 向后扫描,即已经遇到的间隔的扫描,orga- 由支持扫描和更新的数据结构确定。 在实践中 然而,实施特殊结构的需要可能会受到限制 适用性和采用这些评估方法 同时还增加了对内存空间的要求。 在[3]中,Brinkhoff等人。 提出了不同的实现 平面扫描,直接在输入上执行正向扫描 集合,因此,(i)没有必要跟踪活动 设置一个特殊的数据结构和(ii)进行数据扫描 quentially。 3算法2说明了这种方法的伪代码, 由FS表示。 首先,两个输入集合都按开始排序 每个区间的终点。 然后,FS扫描一条线,停在那条线上 按顺序排列R和S的所有间隔的起始端点。 对于每一个 3 该算法最初是为交叉连接而提出的 2D矩形,但应用间隔连接很简单。 1348

  PARADIGM 1:基于散列的分区 输入 :间隔R和S的集合,分区数k,散列 功能h 产量 :设置所有交叉区间对的J(r,s)R×S 1 J; 2 foreach intervalrRdo ⊳分区R. 3 vh(r); ⊳应用哈希函数 4 将r添加到分区R v ; 5 foreach intervalsSdo ⊳分区S. 6 vh(s); ⊳应用哈希函数 7 将s添加到分区S v ; R do的 8个 foreach分区R i 9 S的foreach分区S j 10 ĴĴ⋃{R I⊳⊲ 单元 S j}; ⊳使用LEBI,FS,gFS,bgFS 11 返回J. 算法4说明了增强的bgFS伪代码 带有桶索引的gFS。 从本质上讲,bgFS的运作方式类似于 导gFS。 他们的主要区别在于每个人的前向扫描 当前组内的terval。 12-20行实现了该范围 上一段讨论的查询。 该算法首先确定 tifies铲斗BBI S的覆盖R I .END。 然后,它迭代 通过当前s之后的sS间隔,源于所有 B之前的桶直接在第13-16行产生连接结果 没有任何端点比较,最后在第17-20行, 扫描B的间隔,并与gFS进行比较。 讨论和实施细节。 在我们的实施中, 我们选择不实现索引桶,即没有间隔 复制到专用数据结构。 相比之下,我们为每个人存储 将指针指向其中的最后一个间隔; 这允许bgFS有效 有效地执行正向扫描。 有了这个设计,我们保证 因为没有必要,我们方法的主要内存占用很小 实际上存储数据的第二个副本。 5.并行处理 我们现在将重点转移到区间连接的并行执行 这可以从系统中存在多个CPU核心中获益。 我们首先重新审视并批评基于散列的分区方法 在[18]中提出,然后讨论我们基于域的分区。 5.1基于散列的分区 在[18]中,Piatov等人。 主要侧重于优化EBI 最小化现代硬件中的内存访问成本。 怎么样- 作者还描述了EBI(及其懒惰的LEBI版本) sion)可以并行化。 本着这种精神,基于哈希的分区 提出了范式,由范式1描述。评估 加入涉及两个阶段。 首先,输入集合是分开的 使用散列函数h进入k个不相交的分区。 在这期间 在ond阶段,在所有{R 1 ,...,R k } 之间执行成对连接 集合R的分区和S的所有{S 1 ,...,S k }; 在实践中, 任何单线程间隔连接算法都可以用来连接 两个分区。 由于分区是不相交的,因此成对连接 彼此独立地运行,因此产生结果 无需重复消除(即合并)步骤。 在[18]中,输入集合中的间隔按其排序 在分区之前启动端点,然后分配给分区 以循环方式,即第i个区间被分配给parti- h(i)=(i mod k)。 这导致活动元组设置A R ,A S. 在每个EBI加入的实例变小,因为邻居 - 将间隔分配给不同的分区。 作为基数 A R ,A S影响EBI的运行时间,第10行的每个联接都是 廉价。 另一方面,每个分区中的间隔跨越 PARADIGM 2:基于域的分区 输入 :间隔R和S的集合,分区数k 产量 :设置所有交叉区间对的J(r,s)R×S 1 J; 2 将域拆分为k块; 3 foreach intervalrRdo ⊳分区R. 4 t 开始 域瓦覆盖r.start; 五 t end domain tiles cover r.end; 6 将r添加到分区R start ; 7 foreach tile t j inside(t start ,t end )do 8 将r复制到分区R j ; 9 foreach intervalsSdo ⊳分区S. 10 t 开始 域瓦覆盖s.start; 11 t end domain tiles cover s.end; 12 将s添加到分区S start ; 13 foreach tile t j inside(t start ,t end )do 14 将s复制到分区S j ; 15 foreach domain tile t j do 16 ĴĴ⋃{RĴ⊳⊲ 单元 S j}; ⊳使用LEBI,FS,gFS,bgFS 17 返回J 整个域,意味着每个分区中的数据都很多 与整个数据集相比较稀疏。 这导致了范式1 与a相比,比较总数增加 随着k的增加,单线程算法。 特别是,回想一下 FS和EBI的基本成本是整个空间的席卷, 招致 R + S 和2 R +2 S 比较,分别。 联合国- 基于散列的分区,k 2个连接并行执行,和 每个分区带有 R / k + S / k间隔。 因此,总ba- sic成本分别为k( R + S )和2k( R + S )(即 增加k倍。 此外,尽管负载均匀分布,但哈希 - 基于分区范式并没有充分利用 可用的硬件。 为了充分利用并行性, 每个k 2连接应该由一个单独的线程运行计算 - 在专用处理器(即核心)上。 因此,如果有一个限制 如果是CPU核心数n,我们应该设置k =n来实现 这个,即分区的数量远小于数量 核心。 在下一节中,我们将介绍一个基于域的分区 - 范例,为每个输入集合创建n个分区 通过分割区间域,能够实现更高的 与基于散列的范例相比,并行度水平 与底层连接算法相关。 5.2基于域的分区 与Paradigm 1类似,我们基于域的分区范例 对于并行间隔连接(范例2)涉及两个阶段。 该 第一阶段(第2-14行)将域均匀分割为k非 重叠瓷砖; 为每个do-创建一个分区R j (相应的S j ) 主瓷砖t j 。 设t 开始 ,t end表示覆盖r.start,r.end的图块 间隔rR分别为。 区间r首先分配给par- t t R start为tile t start创建。 然后,r被复制到瓷砖上 t 开始+ 1 ... t 结束 。 r的复制品带有一个特殊标志(例如,r)。 杜尔 第二阶段(第15-16行),基于域的范例 计算řĴ⊳⊲ 单元 S j针对每一个域瓷砖T J,独立。 至 避免产生重复结果,如果报告了连接结果(r,s) 所涉及的间隔中的至少一个是原始的(即,其复制标志 没有设定)。 我们可以很容易地证明,如果对于r和s两者的起始结束 - 点不在t j中 ,那么r和s也应该在前面相交 tile t j-1 ,因此(r,s)将由另一个分区连接报告。 我们用两种范式说明了两种范式之间的区别 图1中的间隔; 不失一般性,假设有4个 可用于计算R⊳⊲S的CPU内核。基于散列的范例 将首先为每个输入创建4= 2个分区,即R 1 = {r 1 }, 1351

  r 2 s 2 s 1 第 3条 s 4 r 1 域 t 1 t 2 t 3 t 4 第 5条 图3:图中间隔的基于域的分区 1; 4个可用CPU核心的情况。 收集R的R 2 = {r 2 },S 1 = {s 1 ,s 3 ,s 5 },S 2 = {s 2 ,s 4 } 对于S,然后评估成对连接的R 1⊳⊲S1 中 ,R 1⊳⊲S 2的,R 2⊳⊲ S 1与R 2⊳⊲S2。 相比之下,基于域的范式将首先出现 将域拆分为图3中所示的4个不相交的区块,并且 然后将间隔分配并复制(如果需要)到4个分区 每个系列; R 1 = {r 1 },R 2 = {r 1 ,r 2 },R 3 = {r 1 ,r 2 }, 对于R, R 4 = {r 2 },并且S 1 = {s 1 },S 2 = {s 2 ,s 3 },S 3 = {s 3 }, 对于S,S 4 = {s 3 ,s 4 ,s 5 },其中r j (相应的s j )表示复制品 的间隔R IR(分别的IS)瓦片T J内。 最后,范式 将计算分区连接的R 1⊳⊲S1 中 ,R 2⊳⊲S 2的,R 3⊳⊲S3 中和 ,R 4⊳⊲S4中 。 需要注意的是,R 3⊳⊲S3 中不会产生任何结果,因为 ,R 3和S 3 中的所有内容的复制品,而,R 4⊳⊲S4中只会 农产品(R 2,S 4),而不是(R 2,S 4),其将R 2中⊳⊲S 2的被发现。 我们基于域的分区范例达到了更高的水平 并行性与Paradigm 1相比,因为对于相同的数量 它需要两个更少的连接。 另外,作为op- 提出了以前的工作,也适用于基于域的分区 (例如,[5,16]),我们避免重复的产生和消除 美食加入结果。 另一方面,跨越的长寿间隔 大量的磁贴和起始端点的偏斜分布 创造不平衡成本的联接。 在下文中,我们提出两个 处理负载平衡的正交技术。 5.2.1迷你连接和贪婪调度 我们对Paradigm 2的第一次优化是基于分解 分区联接为一个域瓷砖T JřĴ⊳⊲的Sj成若干 迷你连接。 迷你连接可以独立执行(即,通过 一个不同的线程)并承担不同的成本。 因此,他们形成了任务 可根据其成本估算贪婪地安排,或 - der实现负载均衡。 具体来说,考虑tile t j和let t j .start和t j .end为其 端点。 我们区分以下情况 tervalrR(resp.sS)在分区R j (resp.S j )中: (ⅰ)R T J 内部启动的,即,T J。开始r.start T J .END, (ii)r在前一个瓦片内部开始但在t j 内部结束 ,即r.start t j .start和r.end t j .end,或 (iii)r在前一个瓦片内开始并在t j 之后结束 ,即r.start T J。开始和r.endT J .END。 注意,在情况(ii)和(iii)中,r被分配给分区R j 复制(范例2的第7-8和13-14行)。 我们用R (i) j , R (ii) Ĵ 和R (iii) Ĵ (分别为S (i) Ĵ ,S (ii) Ĵ 和S (iii) Ĵ )表示迷你 R j (相应的S j )的分区对应于上述3种情况。 在此,我们可以打破分区加入[RĴ⊳⊲单元S j下降到9解散 小型连接; 这9个中只有5个需要进行评估 简化了对这5个迷你连接中的4个的评估。 特别: R (i) Ĵ ⊳⊲S (i) Ĵ 被评估为正常; 即,正如在 第3和第4阶段。 对于R (i) Ĵ ⊳⊲S (ii) Ĵ 和R (ii) Ĵ ⊳⊲S (i) Ĵ ,加入算法只访问 S (ii)中的 终点 Ĵ 和R (ii) Ĵ , 分别; S (ii) Ĵ 和R (ii) Ĵ 仅包含来自先前图块的复制间隔 正确标记为在t j 内开始的所有间隔之前 ,和 所以,他们组成了S (ii) 的唯一集团 Ĵ 和R (ii) Ĵ 在gFS / bgFS。 R (i) Ĵ ⊳⊲S (iii) Ĵ 和R (iii) Ĵ ⊳⊲S (i) Ĵ 减少交叉产品, 导致迷你分区S (iii) 内的复制品 Ĵ 和R (iii) Ĵ 跨越 整个瓷砖t j ; 因此,所有区间对都直接输出为 没有任何终点比较的结果。 R (ii) Ĵ ⊳⊲S (ii) Ĵ ,R (iii) Ĵ ⊳⊲S (ii) Ĵ ,R (iii) Ĵ ⊳⊲S (ii) Ĵ ,R (iii) Ĵ ⊳⊲S (iii) Ĵ 完全没有执行,因为来自两个输入的间隔都是从预先开始的 vious tile,所以这些迷你连接的结果将是重复的。 给定固定数量n的可用CPU核心,即分区 将域转换为k = n个tile,我们的目标是分配每个 1 + 5(k - 1)总微型连接 5到一个核心,以均匀地分离 在所有核心之间加载负载,或者最小化最大化 每核心负载。 这是一个众所周知的NP难题,我们选择 解决使用经典(4/3 - 1 / 3n) - 近似算法[10] 在实践中有很好的表现。 算法贪婪 使用当前最小负载分配给CPU内核 第二大工作。 详细而言,我们首先估算每个迷你的成本 加入; 一个直截了当的方法就是考虑产品 所涉及的迷你分区的基数。 接下来,每个 可用核心p,我们定义其包含迷你连接的包b p 通过累加估计的成本来执行它的负载l p b p中的 迷你连接 ; 最初,b p为空,l p = 0.我们组织了 根据负载在最小优先级队列Q中进行包。 最后,我们考试 - 所有迷你连接按估计成本的降序排列。 对于 每个迷你连接说R (i) Ĵ ⊳⊲S (i) Ĵ ,我们删除 Q顶部的包b p 对应于负载最小的核心p,我们附加R (i) Ĵ ⊳⊲S (i) Ĵ 到b p并将包重新插入Q.这种贪婪的调度算法 在将所有迷你连接附加到包后,终止。 讨论和实施细节。 在实践中,贪心 调度算法取代了原子分配方法 (Paradigm 2的第15-16行)将安排每个分区 - 作为一个整体加入同一个核心。 每个分区的细分 - 将任务连接到可以在不同CPU核心上执行的迷你连接 在原始任务的情况下极大地改善了负载平衡 有很大的成本差异。 5.2.2自适应分区 我们的第二种自适应分区技术用于负载均衡 重新定位{t 1 ,...,t k }瓷砖的端点 ,针对mak- 在范例2中的第16行的所有分区连接的成本 ILAR。 假设将1-1分区连接分配给核心,请加载 通过找到最佳的k分区可以实现平衡 最小化最大分区连接成本。 这可以建模 作为用最小值定义k-bins直方图的问题 每个箱子的最大误差。 6这个问题可以完全解决 关于域大小的PTIME,在动态的帮助下 编程[12]; 但是,在我们的案例中, vals是巨大的,所以我们采用启发式方法,提供了一个很好的解决方案 非常快。 分区所用的时间不应该占主导地位 连接的成本(否则,良好分区的目的是 击败)。 我们的启发式方法让人联想到本地搜索启发式方法 5 第一个瓷砖唯一可能的迷你连接是R (i) Ĵ ⊳⊲S (i) Ĵ ,因为它 它不可能包含任何副本。 6 我们假设有一个可以计算/更新的函数 每个分区的成本 - 在恒定时间内加入; 这个功能应该是 关于相关所涵盖的子域的单调性 在我们的案例中持有的贴瓷砖。 1352

  在没有质量保证的大型域中创建直方图 虽然在短时间内在实践中计算出一个好的解决方案 [19]。 注意,在实践中,总体执行时间占主导地位 通过最昂贵的分区连接。 因此,作为输入提供ini 一组瓷砖和分区(下一段更多细节), 我们执行以下步骤。 首先,CPU核心或等效 确定了承载最高负荷的瓷砖t j 。 然后, 我们通过连续移动来减少t j的负载(表示为l j ) 从R j和S j到其邻居的相应分区的val 具有最高负载的瓦片,即t j-1或t j + 1 ,直到l j-1 l j 或者l j + 1 l j分别成立。 直观地说,这个程序是 响应推进端点t j .start或retreating t j .end。 持续, 我们不断检查核心,负载最高,直到没有 可以进一步移动负载。 这种启发式的实现提出了两个重要的挑战 - lenges; (a)我们如何快速估算每一个的负荷 n = k可用CPU核心和(b)最小负载单位是多少 (换句话说,最小的间隔数)要移入 核心/瓷砖之间。 为了解决这两个问题,我们建立了直方图 统计数据H R和H S在线输入集合,没有ex- 交通扫描费用。 特别是,我们创建了更精细的分区 通过将其分成预定数量的的颗粒来进行结构域分析 是k的大倍数,即= ck,其中c 1。 对于每个颗粒g,我们计算间隔数H R [g]和 来自R和S的H S [g]分别以g开始。 我们定义每一个 初始瓷砖t j作为一组连续的c颗粒; 在实践中,这个 将输入集合定义为与原始宽度相等的平铺 框架。 此外,我们选择一个颗粒作为最小单位(数量 - 在瓷砖之间移动的间隔)。 每个核心的负载 取决于相应分区连接的成本。 这个成本是 如果我们将其分解为迷你连接,则进行优化,如 5.2.1,因为节省了大量的比较。 根据经验, 我们观察到5个迷你连接的整个捆绑的成本 对应于区块t j的区域由第一个迷你连接支配,即, R (i) Ĵ ⊳⊲S (i) Ĵ ,其成本可由 R (i) 估算 j S (i) Ĵ 。 因此,为了计算 R (i) j (分别为 S (i) Ĵ ),我们可以简单地说 累加所有颗粒克吨j 的计数ħ - [R [G](分别为H 2 S并[g])。 当启发式通过移动gran- 改变tile t j 的边界时 到/从t j ,基数 R (i) j , S (i) Ĵ 和加入成本估算 对于t j,可以非常快速地逐步更新。 最后,我们实现了减少tile t j 的负载的过程 通过移动位于t j .start 之后的连续颗粒 或恰好在t j .end 之前 。 移动磁贴的端点不会 涉及任何实际操作,因为我们只保留seg- 应分配给其他par-的初始分区的 titions; 这是可能的,因为H R (H S )保留了确切数 每个移动的颗粒内的间隔。 讨论。 我们可以很容易地将自适应分区与dy-结合起来 namic调度作为两种技术改进的不同部分 范例2,即其第一阶段和第二阶段。 6.实验分析 我们最后介绍了区间连接的实验分析 在单线程和并行处理环境下。 6.1设置 我们的分析是在具有128 GB RAM的机器上进行的 和双10核英特尔(R)Xeon(R)CPU E5-2687W v3主频 3.10 GHz运行Linux; 通过超线程,我们能够运行 最多40个线程。 所有方法都是用C ++实现的,经过优化 通过强制循环展开和使用gcc(v5.2.1)编译 flags -O3,-mavx和-march = native。 对于多线程, 我们使用OpenMP。 我们导入了EBI / LEBI的实现 [18],OIP [7]和DIP [4],由cor-的作者友情提供 回复论文,我们的源代码。 我们的基准设置 类似于[18],即每个间隔包含两个64位端 - 当工作负载累积XOR的总和时指向属性 在每个结果对的起始端点之间。 请注意所有数据 (输入集合,索引结构等)驻留在主存储器中。 关于bgFS,我们将桶的数量设置为等于1000 每次测试,经过调整。 最后,对于并行连接评估,我们作为 - sume固定数量的n个可用的CPU核心,每个核心运行一个sin- gle线节讨论后,两者都有 基于散列和基于域的范例完全使用可用的 核心分别创建n和n分区。 数据集。 我们尝试了两个真实世界的数据集(WE- BKIT和BOOKS)和一些合成的。 WEBKIT 记录2001年至2016年的git存储库中的文件历史记录 Webkit项目(),粒度为毫秒级 - 一次哔声; 有效时间表示文件未更改的时间段。 BOOKS记录了2013年奥胡斯公共图书馆的交易 在几天的粒度(); 有效时间表示 借书的时期。 表1总结了 WEBKIT和BOOKS的特征,而图4显示了他们的 时间分布,即总结持续时间的直方图 间隔和每个间隔的开放(即有效)间隔的数量 时间戳; 后者是一个选择性的指标 val加入。 请注意,持续时间遵循指数分布。 虽然间隔可以从随机域点开始,但有 也是在集中爆发的领域 间隔; 我们将这些时间点称为峰值。 基于这个观察 对于我们的合成数据集,我们生成一小部分间隔 具有均匀分布的起始端点,而其余的 在数字周围的正态分布之后生成一个 随机峰的ber,偏差等于域的10%。 所有生成的时间间隔的持续时间遵循指数 tribution。 表2总结了合成的特征 数据集。 我们生成的集合改变了它们的基数,即 域大小,平均间隔持续时间作为do-的一小部分 主要大小,不同时间戳与域大小的比率, 所涉及峰的数量和峰值基数比(即, 峰值周围产生的间隔百分比)。 试验。 我们在真实世界的数据集上运行了两种类型的测试:(1) 使用每个数据集的统一采样子集的间隔连接 作为外部输入R和整个数据集作为内部S(比率 R / S 在{0.25,0.5,0.75,1}} 7内变化 ,和(2)平行自我 join(即, R = S )改变可用CPU的数量 从4到36的核心(和线程)。关于合成数据集, 我们只执行一系列非自连接; 在每次测试中,我们都有所不同 表2中的一个参数,同时将其余部分固定在其中 故障值。 此外,我们还再次运行并行非自连接 将可用CPU核心数从4改为36.进行评估 方法的表现,我们测量他们的总执行 时间,包括排序,索引和分区成本,以及 端点比较的总数; 对于FS,gFS,bgFS这个 包括推进扫描线和前向扫描,但是 对于LEBI,它只涉及推进扫描线。 注意每个 分区,排序和索引完全并行化; 他们的成本 与扫描和扫描的成本相比,可以忽略不计 产生结果,这决定了整个执行时间。 关于自适应分区,我们进行了一系列测试 定义乘法因子c。 避免显着增加 7 我们还尝试了观察类似的不相交子集 havior; 由于空间不足,省略了结果。 1353

  蘸 000 000 蘸 OIP bgFS LEBI OIP 000 000 蘸 OIP bgFS LEBI bgFS bgFS LEBI LEBI bgFS LEBI 1 10 100 1000 10000 0.25 0.5 0.75 1 执行时间[秒] 1 10 100 1000 10000 0.25 0.5 0.75 1 执行时间[秒] (a) R / S [1核心] (b) R / S [1核心] WEBKIT 图书 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.25 0.5 0.75 1 执行时间[秒] 1 10 100 1000 10000 0.25 0.5 0.75 1 执行时间[秒] (c) R / S [1核心] (d) R / S [1核心] 感染[4] GREEND [4] 图6:单线程处理的比较 将其相应的5个迷你连接捆绑到同一个核心,并且 uniform表示(非自适应)统一初始分区 域名。 我们测试了以下设置: 8 (1)atomic / uniform是基于域的基于分区的 第5.2节,所有优化均已停用; (2)mj + atomic / uniform分割基线的每个分区连接 基于域的范例分为5个迷你连接,这些连接都是exe- 同一个CPU核心; (3)原子/自适应仅采用自适应分区; (4)mj + greedy / uniform拆分基线的每个分区连接 - 主要范式分为5个迷你连接,这些连接是贪婪的 分配给可用的CPU核心; (5)mj + greedy / adaptive采用所有提出的优化。 图7(a)和(b)报告了每个bgFS的总执行时间 优化组合(1) - (5),而图7(c)和(d)报告 平均空闲时间与总执行时间的比率。 我们观察以下内容。首先,设置(2) - (5)都设置为 然后是并行计算的连接。他们的执行时间是 低于基线原子/均匀时间; 出现例外情况 对于4个可用核心下的mj +原子/均匀。效率最高 设置总是包括mj +贪婪的组合,无论ac- 是否适应自适应分区。在实践中,分裂每一个 partition-join到5个迷你连接创建了不同成本的迷你作业 (其中2个是交叉产品,其他2个也很便宜), 这有助于将总连接成本均匀划分为 处理器用以。例如,如果一个分区整体比较重 对其他人来说,一个核心将致力于其最昂贵的 迷你连接和其他迷你连接将由较少的负载处理 CPU核心。另外,请注意mj优化甚至是有益的 当5个定义的迷你连接都在同一个CPU上执行时 核心(即mj +​​原子/均匀)。这是因为打破了 分区连接成5个迷你连接大大降低了整体成本 分区连接(再次回想起4个迷你连接很便宜)。 与之相比,自适应分区似乎影响较小 到另外两个优化。在没有em-的设置中 贪婪的调度,原子/自适应排名首先(两者都在 8 根据我们在第6.1节中的假设,贪婪/制服或 贪婪/自适应设置没有意义,因为 titions等于可用CPU核心数。 原子/均匀 (a) R / S [1核心 静态/固定 静态/固定 IC /自适应 米 MJ +克 MJ +原子/均匀 静态/固定 静态/固定 IC /自适应 米 MJ +克 原子/自适应 静态/固定 静态/固定 IC /自适应 米 MJ +克 MJ +贪婪/均匀 芦苇/固定 Y /自适应 MJ +贪婪/自适应 芦苇/固定 Y /自适应 0 五 10 15 20 25 三十 0.25 0.5 0.75 1 执行时间[秒] 0 10 20 三十 40 50 60 70 80 4 9 16 25 HT 36 HT 执行时间[秒] (a) R / S [16核心] (b)#core [ R = S ] 0 10 20 三十 40 50 60 70 80 0.25 0.5 0.75 1 平均闲置时间比例[%] 0 10 20 三十 40 50 60 70 80 4 9 16 25 HT 36 HT 平均闲置时间比例[%] (c) R / S [16核心] (d)#core [ R = S ] 图7:优化基于域的分区:bgFS on WEBKIT 执行时间的条件,平均空闲时间比率)但是 在mj +贪婪/均匀设置之上激活,自适应部分 当核心数量增加时,可以增强连接评估 低,例如4或9; 请注意mj +贪婪/自适应设置的速度有多快 与4个可用CPU核心的mj +贪婪/制服相比。 总体而言,(i)mj优化大大降低了参与者的成本 加入并增加负载平衡的灵活性,(ii) mj +贪婪/制服和mj +贪婪/自适应方案很好 在负载平衡方面,通过减少平均空闲时间 几乎没有任何核心占总执行时间的20% 所有情况( R / S = 0.25是唯一的例外)。要采取完整的广告 - 所有提议的优化的优势,我们设置基于域 范式为mj +贪婪/适应其余的分析。 6.5比较:并行处理 在本节中,我们首先比较基于域的分区 反对基于哈希的[18]中提出的; 这项研究是独立的 我们可能用来计算分区或迷你的连接算法 连接。 此外,我们比较了我们提出的FS实施方案 所有优化(即bgFS)到最新技术(如图所示) 在6.3节中)LEBI用于区间连接的并行计算。 因此,我们实现了基于域和基于哈希的 第5节的范例加上LEBI和我们最好的方法 bgFS,由h-LEBI,d-LEBI和h-bgFS,d-bgFS表示; 注意 上一节评估的mj +贪婪/自适应优化 这些都是在LEBI供电的实施中激活的 基于域的范式。正如第5.1节[18]中所讨论的那样 分区前的每个输入集合。我们也进行了实验 使用基于散列的范例的变体,它不执行 这个预分拣步骤并证明总是更快。因此,为了 本小节的其余部分我们运行基于散列的parti的变体 tioning。图8(a) - (d)和图9(a) - (d)首先报告 WEBKIT和BOOKS数据集的比较

返回列表

RELATED CASE

相关案例

仪器仪表

逆向扫描、正向扫描

主要承接手板模型制作,面向所有工业模...

仪器仪表

基于正向扫描的并行区间连接平面扫描算

区间连接是在时间,空间和不确定数据库...

仪器仪表

正向密勒扫描电路的设计

正 电子示波器扫描电路要求扫描速度变化...

仪器仪表

正向扫描 电子邮件

Thermo Scientific Evolution 201/220/260紫外可见光...

仪器仪表

玻璃生产工艺

玻璃生产工艺_材料科学_工程科技_专业资...

2019年最快正版通天报

感兴趣吗?

2019年最快正版通天报

2019年最快正版通天报【客服:扣扣764802430】会员即送28,会员了解更多优惠。唯一安全购彩入口【官方权威认证:热彩彩票www.a9892.com】彩票行业领导者,提供最顶尖的游戏体验,最安全的游戏娱乐。