LSF-Join：局部敏感的偏置下分布所有对集相似性过滤

2998→→（）下一页（）下一页（）（）(3)≤ ≤LSF-Join：局部敏感的偏置下分布所有对集相似性过滤赛勒斯·拉什奇安UCSDcrashtchian@eng.ucsd.eduAneeshSharmaGoogleaneesh@google.comDavid P. 伍德拉夫CMUdwoodruf@cs.cmu.edu摘要全对集相似性是一个广泛使用的数据挖掘任务，即使是大型和高维数据集。传统上，相似性搜索集中在发现非常相似的对，其中各种有效的算法是已知的。然而，最近的工作已经强调了发现具有相对较小的交叉尺寸的集合对的重要性。例如，在推荐系统中，两个用户可能是相似的，即使他们的兴趣只在一小部分项目上重叠。在这样的系统中，一些维度是高度偏斜的也是常见的，因为它们非常流行。 这两个属性一起使得以前的方法对于大输入大小是不可行的。 为了解决这个问题，我们提出了一个新的分布式算法，LSF-Join，近似所有对集相似性。算法的核心是基于局部敏感过滤的随机选择过程特别是，我们的方法偏离了以前的近似算法，这是基于局部敏感哈希。理论上，我们表明，LSF连接有效地找到最接近的对，即使是小的相似性阈值和倾斜的输入集。 我们证明了LSF-Join的通信，工作和最大负载的保证，我们还通过实验证明了它在多个图上的准确性。CCS概念• 信息系统最近邻搜索;协同过滤;社交网络;·计算理论MapReduce算法。关键词相似性搜索，分布式算法，社交网络ACM参考格式：Cyrus Rashtchian，Aneesh Sharma，and David P.伍德拉夫2020年。LSF-Join：局部敏感过滤，用于偏斜下的分布式所有对集相似性。在网络会议2020（WWW '20）的会议记录，2020年4月20日至24日，台北，台湾。ACM，美国纽约州纽约市，7页。https://doi.org/10。1145/3366423.33800691引言相似性搜索是数据挖掘应用中广泛使用的原语，特别是所有对相似性是常见的数据挖掘操作[1，5，18，29]。受推荐系统和社交网络的启发，我们设计了用于计算所有对集合相似性（也称为，集合相似性连接）。特别是，我们认为本文在知识共享署名4.0国际（CC-BY 4.0）许可下发布。作者保留在其个人和公司网站上以适当的署名传播作品的权利WWW©2020 IW 3C 2（国际万维网大会委员会），在知识共享CC-BY 4.0许可下发布。ACM ISBN 978-1-4503-7023-3/20/04。https://doi.org/10.1145/3366423.3380069二分图中节点的相似性我们希望从图的一侧确定相似的节点对对于右边的每个节点v，我们考虑它左边的邻域Γv等价地，我们可以把Γv看作是图中v的邻居的集合 使用这种表示，许多基于图的相似性问题可以被公式化为寻找具有显著重叠邻域的节点对。我们关注于表示为高维向量的对Γ v和Γ u之间的余弦相似性。尽管集合相似性搜索在过去的几年中受到了广泛的关注，在文献中，现代系统有三个方面尚未得到充分解决。具体地说，我们的目标是开发具有可证明保证的算法，并处理以下三个标准：(1) 分布式和可扩展性。 该算法应该在MapReduce这样的分布式环境中工作得很好，并且应该使用大量处理器扩展到大型图形。(2) 相似度低该算法应该输出具有相对低的归一化集合相似性的大多数集合对，例如取值0的余弦相似性τ的设置。1 τ0。五、极端倾斜。 即使维度（左边的度数）高度不规则和倾斜，该算法也应该可以很好地工作。这些标准的动机来自推荐系统和社交网络。对于第一个标准，我们考虑具有大量顶点的图。对于第二种情况，我们希望找到语义相似但余弦值不大的节点对。这种情况在协同过滤和用户相似性中很常见[ 23 ]，其中两个用户可能是相似的，即使他们在少量项目上重叠（例如，歌曲、电影或引文）。以前的工作未能处理所有上述三个crite- ria。当发现低相似性项目时（例如，余弦相似度0.5），像局部敏感哈希[13，24，31]这样的标准技术不再有效（因为哈希迭代的次数太大）。最近，有几个解决这个问题的建议，最接近我们的是来自[23]的楔形采样然而，[23]中的方法有一个严重的缺点：它要求每个维度具有相对较低的频率（即，二分图具有小的左度）。在这项工作中，我们通过提出一种新的分布式算法LSF-Join近似所有对相似性，可以扩展到具有高偏斜度的大型图作为一个主要的贡献，我们提供了理论上的保证，我们的算法，表明它达到了非常高的精度。 我们还提供了通信，工作，并在分布式环境中的最大负载与大量的处理器的保证。我们的方法使用局部敏感过滤（LSF）[9]。这是一局部敏感哈希（Locality Sensitive Hashing，LSH）。LSF和LSH之间的主要区别在于LSF构建了一个2999（）下一页≤（）|（）下一页|（）∈{}{（）|∈ }≤ ≤[详细][客户端]| |（）下一页||[][]≈i=1/（）下一页（）下一页∈[]∈（/）WWW基于散列函数的单个存活元素组（对于每次迭代）。相比之下，LSH每次都构造一个完整的哈希表，进行大量的迭代。虽然散列和采样的思想是相似的，但LSF的好处在于它的计算和通信成本。具体来说，我们的LSF方案将具有这样的性质：如果元素v在k个哈希函数中的k ′中存活，那么计算将以k ′而不是k为尺度。 对于低相似性元素，k ′通常远小于k，从而导致较低的总成本（例如，k ′在输入大小上将是次线性的，而k是线性的）。我们还提供了一种有效的方法来执行每个节点的基础上的过滤步骤。问题设置。 输入由一个二分图G组成，该二分图G在左侧具有M个顶点，在右侧具有N个顶点。我们将该图记为G=U，V，E，并将U称为维数集，将V称为节点集。给定参数τ>0，我们我想从V中输出所有相似的节点对（v，v′），使得偏态数据[20]。他们的数据相关方法导致了基于维度频率的序列算法，改进了先前的基于LSF的算法[9]。不幸的是，似乎不可能使他们的方法适应单轮分布式设置。另一个相关结果是[23]中的楔形抽样方法。然而，他们的算法假设数据集没有偏斜。在并行计算模型[6，7]中，已经开发了多轮算法，该算法建立在LSH的基础上，用于近似相似性连接，从而实现最大负载的输出最优保证[14，21]。然而，在具有大量处理器的现代无共享集群中使用多轮可能会非常昂贵。 使用LSH的算法在τ足够大时工作良好，例如0。6 τ<1。0.然而，对于较小的τ，由于大量的重复，基于LSH的分布式算法需要太多的计算和/或通信[10，23，26，30]。以前的工作也研究了寻找前-|Γ(v) ∩Γ(v′)||·|Γ（v ′）|Γ(v′)| ≥τ。 这个问题还包含了其他目标，[1，2，8]或寻找具有常数大小交集的集合对[11]。这些结果不适用于我们的设置，因为例如找到每个节点的前k个结果注意，我们可以等价地用其邻居的集合Γ v U来标识每个节点v，因此，该问题与具有输入Γv vV和余弦相似性阈值τ的集合相似性连接问题相同。我们在类似MapReduce的框架中描述了我们的算法，并且我们在大规模并行计算模型中分析了它[6，16]，该模型捕获了MapReduce启发模型的理论属性（例如，[15、22]）。我们有p个处理器，在一个无共享的分布式环境中。输入数据开始任意parti-之间的处理器。与右侧的每个节点v相关联的是向量V0， 1M，其是左侧v的V邻居的指示符向量我们希望实现负载平衡服务器和低通信成本的双重属性。我们的贡献。我们的工作的主要贡献是一个新的随机化，分布式算法，LSF-Join，可证明发现几乎所有的集合对余弦相似性高于给定的阈值。我们的目标是找到余弦相似性τ在0范围内的大基数集对。1τ 0。5，我们允许交叉点的大小在幅度上很大。2LSF-JOIN算法我们首先从一个高层次的概述我们的集合相似性连接算法，LSF-Join，这是基于一个新颖的和有效的LSF计划。设G=U，V，E为输入图，其左侧为U=M维，右侧为V=N个节点 为了方便起见，我们可互换地引用顶点V和它们的索引N，其中我们使用N来表示集合1，2，. . .、N.LSF-Join算法使用k个独立的重复，滤波方案（其中k N实现最佳折衷）。在第i次重复中，我们创建右侧顶点集N的幸存者集SiN。 我们将很快定义LSF过程，其将以数据无关的方式确定子集{Si}k 。老τ 我们的算法将满足上述所有三个标准（可扩展性，低相似性和偏度）。LSF-Join的一个关键组成部分是一个新的随机LSF方案，我们称之为生存过程。此过程的目标是找到可能包含相似对的数据集子集。换句话说，它充当过滤步骤。我们的LSF过程具有许多有利的经验和理论性质。首先，我们可以在接近线性的时间内执行它，这允许它扩展到非常大的数据集。其次，我们展示了一个有效的方法来实现它在一个分布式的设置与大量的处理器，只使用一个单一的一轮通信的整个LSF-Join算法。第三，生存过程导致次二次局部工作，即使当维度高度偏斜并且相似性阈值相对较低时。 为了实现这些属性，我们演示了如何使用高效的，成对独立的哈希函数实现过滤，我们表明，即使在这种设置中，该算法具有良好的可证明的保证的准确性和运行时间。相关工作。 许多基于过滤的相似性连接算法提供了精确的算法，并依赖于算法来改善运行时间[3，4，12，19，25，27- 29 ]。我们主要回顾与我们的设置相关的先前工作，并提供理论保证。一个相关的工作是使用LSF进行集合相似性搜索和连接时尚. 在通信阶段，生存集将被它们全部分布在处理器上。特别是，如果有p个处理器，那么每个处理器将处理大约kp个不同的重复。在本地计算期间，处理器将在本地计算Si for i k中的所有相似对，并且以聚合的方式（以分布式方式）输出这些对。作为理论分析的一部分，我们表明，每个S i的大小集中在其平均值，因此，我们的算法在处理器之间的 为了实现相似对的高召回率，我们需要独立地执行LSF-Join算法O log N次，这样失败概率将是多项式小的。幸运的是，这只会增加通信和计算的OlogN因子。我们并行执行迭代，LSF-Join只需要一轮通信。2.1构造生存集Si我们现在描述我们的LSF方案，其归结为描述如何构造Si生存集。我们有两个主要参数：α 0，1 2表示单个维度的生存概率（左侧），k表示重复次数。描述我们的LSF生存过程的最简单方法是通过均匀随机抽样。我们把这个简单的方案√3000联系我们{∈}{∈}[]≥（）下一页/∈[]（）⊆∈∈[]∈[]{∈}| （）下一页|·（/）∈（）下一页| （）下一页|·（/）×（）|（）下一页|| （）下一页|| ()|| （）下一页||( )|| （）（）||( ) ∪ ()|′∈（）|（）下一页|·（/）[||]的情况下，||]≫{∈}|{∈}|||LSF-Join：Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew WWW算法1单个节点的高效LSF1：函数FAST-FIlter（G，v，α，k）2：使用共享随机种子计算Av和bv3：确定Avi+bv=0的解空间4：设Ivi：Avi+bv=05：return Return Iv//Iv= i：vSi6：结束功能算法2近似余弦相似连接1：并行重复以下过程O（logN）次2：函数LSF-JoIN（G=（U，V，E），τ，α，k）3：对于每个顶点v∈V，并行地2.2快速过滤法我们的快速过滤方法背后的关键思想是开发一个成对独立的过滤方案，近似于生存集的均匀采样然后，我们设计了一种方法来有效地计算每个节点的基础上，通过使用快速矩阵运算的生存集。更准确地说，对于右边的每个节点v，快速过滤器将确定v生存的生存集的索引Ivk（即，我们有Iv=i：v Si）。我们开发了一种方法来计算I-V独立的每个顶点V通过使用高斯消元的二进制矩阵。快速过滤方法只需要处理器之间的少量共享随机性。为了描述快速过滤器方法，以下将是方便的：证明log2（ 1/α）和log2k都是整数。我们现在解释两两独立的过滤方案。对于每个节点u∈U4：FAST-FI lter（G，v，α，k）确定包含v的集合在左边，我们对随机log2（ 1/α）× log2k二进制矩阵进行采样5：划分集合S1，. . . ，Sk跨处理器6：局部计算每个Si中具有相似性τ的所有对7：以分布式方式输出所有闭合对8：结束功能简单过滤器方法，我们首先描述它然后，我们说明了如何改进这种方法，使用一个两两独立的过滤方案，这将是更有效的在实践中。我们把改进的LSF方案称为快速滤波器方法。后来，Au′和一个log21α长度的位串bu′。 我们用GF 2上的log 2 k维向量空间中的二进制向量来识别k次重复i k中的每一次，GF 2是具有两个元素的有限域。换句话说，我们使用i的二进制表示将i与长度为log 2k的位串相关联，并且我们执行矩阵和向量运算。模2的运算 我们滥用符号，并使用i表示整数和位串，其中上下文将区分两者。为了确定节点v∈ [N]是否在Si中存活，我们执行我们还表明，快速过滤器享有许多相同的理论这是一个错误的操作。我们首先将矩阵Au′堆叠在顶部简单过滤器的保证，具有更低的计算成本。2.1.1朴素过滤器。 对于我们的过滤方案的朴素版本，考虑重复次数i k。我们通过独立地选择每个节点u U以概率α在Ui中来选择左侧顶点的一致随机集合UiU。然后，我们根据它们的邻域是否完全包含在Ui中或不完全包含在U i中（也就是说，不管Γ（v）是否<$Ui或v的每个邻居u r v的相互关系这就形成了一个rv对数21αlog2k矩阵Av. 我们还将向量bu′堆叠在彼此之上，形成长度为Γvlog2 1α 的 位 串 bv 。 最 后 ， 我 们 通 过 设 置 vSi 当 且 仅 当Avi+bv=0来定义Si，其中0表示全零向量。我们说，如果Avi+bv=0，则v在第i次重复中存活则Iv=i：vSi是指数Ivk的集合，其中v生存。在单轮分布式设置中，处理器可以有效地不）。第i个生存集Si将是顶点v∈V的集合，使用a预先计算子矩阵Au′和子向量bu′所以v乌岛我们对每个i = 1，2，.独立地重复这个过程。. . ，k，以导出k个经滤波的顶点集合S1，. . . ，Sk. 请注意，对于每个i，v在Si中满足v的概率是exvα。|Γ（v）|其中，rv是v在左边的邻居的数量。使用这种过滤方法进行集合相似性的直观性搜索的一个重要特征是，相似的配对相对可能在同一集合中存活实际上，v和v ′在Si中 存活 的机 会等于α|Γ（v）<$Γ（v′）|. 当余弦相似性较大时，我们必须使ΓvΓv′较大，且ΓvΓv′远小于Γv+Γv′.换句话说，如果v和v′相似，它们更有可能共存，如果它们非常不同，则不太可能共存。例如，考虑d=Γv=Γv′的情况是一个很大的常数。然后，余弦相似度至少为τ的对将生存概率为α（2-τ）d。在另一个极端，不相交的对只以概率α2d生存在一起。Naive-Filter方法的主要缺点是它需要太多的时间，需要花费大量的时间来确定所有的指数i，使得v∈Si。考虑v的近邻集我们需要确定是否Γ（v）<$U分享种子特别地，与预先存储相反，这些可以通过使用共享随机种子并且通过使用高效散列函数来计算Au′和bu′的元素而在运行中计算，仅当预处理v使得uv. 通过这样做，作者将使用与另一个相同的Au和bu′值，从而导致一致的生存集，而不会引起任何额外的通信回合。为了直观地了解这个滤波过程，令d=Γv表示v的邻居的数目如果i满足Avi+bv=0，则节点v将在Si中存活这是由dlog2 1α线性方程组组成的，我必须满足这些方程组。 由于矩阵Av和向量bv是随机一致选择的，因此很容易检验v在Si中以概率α生存|Γ（v）|=αd，和hence，它们的e× p ed大小满足在随机A v和b v上ESi=αdN和EIv=αdk.从理论上讲，快速过滤器的主要吸引力在于它是成对的在以下意义上独立对于任何两个不同的重复i和i ′，i和i ′的比特串至少有一个比特不同。因此，我们看到Avi+bv 满足或不满足，独立于每我i∈[k]。 因此，它至少需要O（α|Γ（v）|k）工作，Av i ′ + bv = 0，在Av和bv的随机选择上。虽然这是只有对重复，这种程度的独立性将计算v生存的索引，即集合i：vSi。我们将需要设置k N，因此，朴素过滤器的工作对于每个节点v都是N线性的或更糟。为了改进这一点，我们的快速滤波器方法将具有与i：vSi成比例的功，并且我们表明这通常远小于k。我们的理论分析就足够了此外，我们表明，我们可以确定的生存集包含v在时间成正比的数量Iv这样的集合，这往往是远远小于总数k的可能的集合。3001（）下一页∈[]（）下一页∈[]（（））{∈}（）（）下一页|（）下一页|/（）下一页（/）（）下一页（/）（/）（/）/|（）下一页|（）下一页0[||]/{∈}||≤（）∈[]∈[]（）∈（）（）∈（）（）（（））. .Σ| （）下一页|∈（||）|（）下 一 页|( ){|（）下一页||（）下一页|}计算|Γ（v）<$Γ（v′）|如果它至少是τ，则检查ck|·|Γ（v ′）|.|.|2· d i ·k|2·di·k让我们来看看3.2.每个处理器的预期负载为αdNk/p，WWW我们现在解释如何在每个节点的基础上有效地计算生存集。对于一个固定的节点vN，快速过滤方法确定v在其中存活的重复i，或者换句话说，集合Iv=i：vSi。这相当于找到所有长度log2k位串i是Avi+bv=0的解处理器可以在O d时间内形成Av和bv，其中d=Γv，假设单位成本RAM模型为Olog2N位。然后，我们可以使用高斯消元法来快速找到所有满足Av i +bv = 0的i k。要理解这一点的复杂性，首先要注意Av有log2k列。此外，在不损失generality的情况下，我们看到Av最多有log 2k行，否则不存在解。因此，高斯消元法需要O log 3 k时间来将Av写成上三角形形式（并相应地重写bv），以便可以在与该方程的解的数量成比例的时间内枚举A u i = b u的所有解。预计总工作为O N log 3 k +αd kN。这可以针对每个节点v独立地并行化。我们在定理3.5中证明了关于快速滤波器的保证。 的快速过滤器的伪代码显示为算法1。 这两种过滤方法的主要区别在于如何选择随机生存集。为了便于讨论，我们设置k=N，这在实际中是合理的，并且我们继续让d= N。|Γ（v）|.或者换句话说，α = 2 k 1/（（2−τ）d<$），其中2可以用更大的常数来代替，以提高召回率。 如果log 21 α是整数，则可以近似地满足（1），然后用这些参数运行该算法的O log N次独立迭代将工作得很好。例如，当1 2d<$= 1Nc时，c为常数然而，对于大的平均值，greend<$，参数α可能超过1/2。为了近似α>12，我们可以对矩阵Av和向量bv进行二次采样以增加有效的碰撞概率。更准确地说，考虑d= Γv。如果我们希望在概率为αd的重复中生存，那么我们可以在等式αd=1 2d中求解d，并且我们对Av和bv中的d行进行子采样，直到d。 这有效地构建了生存集Si，如在朴素过滤器中，每个邻居生存的α概率。在理论结果中，我们假设α和k满足（1）。 在实验中，我们将α设置为1/2，或者使用矩阵子采样方法;我们还改变独立迭代以提高召回率（我们将其表示为β）。3理论保证为了简单起见，我们假设图G = U，V，E是右正则的，V中的节点具有度d。在实践中，我们可以对不同的小范围的d重复该算法。首先，请注意，在快速过滤方法中，我们使用了一个随机的线性映射在GF2具有足够的独立随机性来决定每次重复，节点是否存活。利用高斯消去法，Pr[v∈Si]=Pr[Avi+bv1个d= ]=2dlog21/α =α（二更）我们可以计算Iv=i：vSI 在时间上正比于Iv N。特别地，v的工作量在期望中是Olog3N +αdN，因为当k = N时，EIV=αdN。LSF-Join的伪代码显示为算法2。我们假设顶点v开始在p个处理器上任意划分对于平行的每个顶点v，我们使用快速过滤器确定v生存的集合的指数Iv如上所述，我们可以通过为快速过滤器使用共享的随机种子来始终如一地做到这一点在通信阶段，我们随机地分布集合S1，. . . ，Sk，使得每个处理器在预期中处理k p个集合。然后，在局部计算期间，我们并行地比较每个i k的Si中的所有对。我们并行使用该算法的OlogN次独立迭代来找到具有高概率的所有闭合对（例如，近一点的回忆最后，我们以分布式方式输出余弦相似度至少为τ的所有对处理每个Si集合的一种方式是比较这一套。对于所有的nodesv，v′，∈Si，e，x，y，（）（）现在考虑两个节点u，vN. 则u和v都在Si中，如果并且仅当以下事件发生时。设Au，v是把Au叠加在Av上得到的矩阵，bu，v是把bu叠加在bv上得到的向量.注意，对于每个wrurv，Aw的行在Au，v中出现两次，bw的坐标在bu，v中出现两次。因此，对于每个wΓuΓv，在Au，v中仅保留Aw和bw的一个副本就足够了，并且通过这样做，我们将Au，v的行数和bu，v的条目数减少到至多|·d log 2 1 / α。|·dlog 21/α. 缺点是，Pr [u∈Siandv∈Si]=Pr [Au，vi+bu，v=0]=α|Γ（u）<$Γ（v）|（三）注意，在一个极端，如果Γ（u）和Γ（v）不相交，则（3）e的值为0α2d。 另一方面如果|Γ（u）<$Γ（v）|≥τ·d，则|≤（2 − τ）d，则（3）e的值为α（2 − τ）d。|≤(2−τ)d,andthen(3)evaluatestoα(2−τ)d.（2）和（3）中的差异正是我们在LSF方案中所利用的;即，我们使用相似对更多的事实我们可以假设列表Γv和Γv′是d′的有序数组整数，其中d′=maxΓv，Γv′。因此，可以通过在O d′时间内合并这些排序列表来计算ΓuΓv，假设长度为Olog2N的字可以在单位成本RAM模型中在恒定时间内被操作设di是vSi上的最大值，则局部比较集合Si中所有对的时间为OSi2di。我们也可以绑定p个处理器处理所有集合的平均工作量我们首先证明（1）中α的设置。让我们来看看3.1. 设u，vbe使得|Γ（u）<$Γ（v）|≥τd。Expected重复次数i，其中u ∈ Si和v ∈ Si都至少为2。ProoF. 如（3）所示，u和v在一次竞争中生存的概率为α|Γ（u ）<$Γ（v）|≥α（2-τ）d，并且r表示u ∈ Si和v ∈ Si都至少为k·α（2-τ）d的期望重复次数，其通过（1）至少为2。□p2.2.1设置参数。 令d<$表示输入图中右侧的平均度。理想情况下，这些参数应满足α（2−τ）d<$·k=2，（1）预期总通信量为αd kN。ProoF. 有k个重复，每个重复涉及一个Si生存集。 每个节点v∈ [N]在Si中以概率αd独立地存活。Si的扩展大小为E|SI|=αdN。每一位首席执行官比不同的对更有可能在重复中生存在一起S1，. . . ，Sk. 这可以通过O来限制ki=1.3002i=1（）下一页2−τ·−2[客户端]（）下一页（）下一页∈∈∈[]（||）[客户端]∈[]·（（））（）下一页∈[]（）（·）≥（）下一页·（||）全面沟通是ki=1|，它具有e ∈ α dkN.|, whichhasexpectationαdkN.□yf x=Ax+b mod 2，其中A和b分别在所有可能的二元矩阵和向量上是u和v都满足的重复次数i=1生存通过LSF-Join：Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew WWW处理k/N个重新配置。s，导致αdNk/pex pectd载荷。的引理3.1，E[X] ≥2。众所周知，散列函数fam-（）下一页让我们来看看3.3.使用暴力所有对本地，预期的工作登特家族。因此，X1，X2，. . . ，Xk是成对独立的每台机器的平均速度为（αdN）2k/p。随机变量，并且相应地Va r[X]=。KVar[Xi]. AsProoF. 每次重复都有期望的大小αdN，导致工作α2dN2. 每个处理器处理k/p次重复，这意味着α2dN2k/pXi ∈ {0，1}，我们有Var[Xi] ≤ E[Xi]，因此，Var[X] ≤ E[X]。利用Chebysh ev's的性质，Pr[X=0]≤Var[X]2≤1≤1.□每个处理器的工作量符合预期。□（E[X]）E[X]2结合引理和插入α得到以下结果。定理3.4. 设α=（2/k）1/（（2−τ）d），生存过程的总通信时间为O（Nk1−1/（2−τ）），局部工作时间为O（N2k1−2/（2−τ）/p）.作为一个例子，当p=N时，我们将其与总通信量为N3/2，局部工作量为N的散列连接进行比较。设k=N2−2τ，为了扩大召回率，我们并行运行β = O log N个LSF-Join副本。我们强调，这是实现高概率结果的更有效的方法，优于简单地增加单个LSF-Join执行中的重复次数k。直觉上，这是因为重复只能保证是成对独立的。理论上，O（log（ 1/δ））独立拷贝导致1−δ的失效概率，由一个Besloff界确定。但是，如果我们根据定理3.4，预期的总通信量为Nk−τ/（2−2τ）=N3/ 2。每个处理器的本地工作是Nk−τ/（2−τ）=N1−2ττ。 由于τ> 0，工作总是次线性的，因此在使用相同的总通信量的同时，比散列连接有所改进。 正如我们将在下面的定理中看到的，使用上面的成对独立哈希函数族来生成随机性是至关重要的。定 理 3.5. N 中 的 节 点 生 成 Si 所 需 的 期 望 总 时 间 为 ONlog3k+αdkN+E，并且N中的节点对每个i发送每个v ∈ Si的集合Γ（v）所需的期望总时间和通信量为O（N log3 k + αdkN·d log N + |E|）的。ProoF.每个节点uN需要计算出它生存的重复i采用单位成本RAM模型，在Olog2N位字上，可以在O d时间内形成Au和bu注意，u需要计算出哪个i N满足Aui+bu=0。要做到这一点，可以使用高斯消去法来求解这个方程 注意，Au最多有log 2k行，并且有log 2k列。因此高斯消去法最多需要Olog3k时间来写入Au，上三角形形式和相应的bu，使得方程Aux=bu的所有解可以在时间上与该方程的解的数量成比例地被枚举因此，每个处理器的预期时间是O log 3 N + αd N，其中我们使用（2）来限制u存活的预期重复次数k αd。因此，对于i = 1，2，. . . ，k，是O N log3 k + αd kN。 注意，O αd kN d log N是预期的通信总量。□虽然在预期中是正确的，但由于在重复中使用的随机性不是独立的，即，我们对每个节点w M使用相同的矩阵Aw和向量bw，因此重要的是要表明重复次数i的方差对于uSi和vSi都很小。这使得人们能够显示存在至少一个重复i的概率，对于该重复i，u和v都存活是足够大的常数，其可以通过独立地重复恒定次数而放大到任何更大的常数。让我们来看看3.6. 设u，vbe使得|Γ（u）<$Γ（v）|≥τd。 概率至少为1/2时，存在重复i，u ∈ Si，v ∈ Si。ProoF. 设Xi是指示随机变量，如果u和增加了重复次数，那么根据切比雪夫不等式，我们需要使用O（k/δ）次重复来获得相同的成功概率1−δ。 后者需要O（1/δ）倍的通信/计算量，而前者仅为O（log（1/δ））因子。设δ=1/N3，则在O（N2）个可能对上取并界后，失败概率为1− 1/N4实验结果在本节中，我们通过实验来补充前面提出的理论分析，这些实验在SNAP存储库[17]的三个真实世界图上测量LSF-Join的召回率和效率：WikiVote，PhysicsCitation和Epperium。 根据我们的动机，我们还在一个极度倾斜的合成图上运行LSF-Join，WHIMP算法失败了。实验设置。我们将LSF-Join与[23]中最先进的WHIMP算法进行比较，因此我们的设置接近WHIMP的设置在这种情况下，我们将我们的图转化为二分图，或者通过从左到右定向边（对于有向图），或者通过在任意一侧复制节点（对于未定向图）。这与在引言中描述的左侧表示集合和右侧表示节点的设置一致。此外，我们预过滤每个二分图，使其右侧的度范围很窄（左侧的度仍然可以是O n），以最大限度地减少由于度不匹配而导致的余弦相似度值的方差。这使得实验更清晰，算法本身可以以加倍的方式运行所有度在计算每个桶i的幸存者集Si之后，我们使用稀疏矩阵乘法来计算所有对的相似度，因为它在实践中非常快，并且在每个服务器上消耗d O Si内存。最后，即使我们在前面计算了理论上的最佳α值，但在实践中，较小的α选择通常足以结合对β1独立迭代重复快速过滤方法对于每个图，我们在Google内部的分布式MapReduce平台上对图运行LSF-Join输出相对于从所述数据的样本生成的地面真值集的相似对地面真值集是通过对选择的一小部分节点进行精确的全对计算而生成的，v满足第i个条件，并且是其他条件。 设X=.KXi随机使用这个基本事实，我们可以测量算法，我们专注于评估的措施是3003| |/（）\||·|| ≪//WWW数据集NM通信成本召回.LSF-加入 *WHIMP†LSF连接WHIMPWikiVote7K104K710 MB（i|SI|=7 1M，β=30）410MB（.我|SI|=4 1M，β=1）6GB（.我|SI|=57 3M，β=1）160GB（.我|SI|=8B，β=50）60MB百分百百分百引文34K四二一千50MB百分百百分百Epinions60K500K60MB百分百百分百合成10M200M作业失败百分之九十-表1：LSF-Join和WHIMP在四个数据集上的相对性能总结，包括通信成本和召回率（WHIMP的精确度也很高）。我们注意到LSF-Join以最小独立迭代次数β运行，以实现τ = 0的高召回率。1 .一、* LSF-Join的通信成本取决于幸存者的数量，我们将其与β的值一起记录。[2]WHIMP的通信成本主要是由打乱SimHash草图所决定的。 我们为SimHash使用8K位，如[23]中所建议的。相似对的回忆1.具体来说，让相似度至少为τ的真相似对的集合由S表示。此外，让同一组节点上的相似对的集合由算法返回的值是S。然后，召回R =|SS|.正被消费的内容经历幂律分布（例如，一些视频比其他视频更受欢迎以下是同一现象的简化设置随机二部图构造：我们构造一个N×N二部图，对于τ的固定值，numberS，我们可以测量回忆的变化，图G（U，V，E），其中每个右节点的度为d。每项权利节点v∈V选择连接到左节点如下：独立迭代的β变化（α固定且k = N）。我们在实现高召回率的β值下运行我们的实验（这是一种跨数据集的策略），结果总结在表1中以便于比较。表中包括一个综合数据集，稍后将对其进行描述。LSF-Join的通信成本取决于幸存者的数量，而幸存者的数量又取决于β的选择。这里我们忽略了一个微妙之处，即通信成本实际上通常远小于幸存者的数量，因为多次独立重复将产生同一节点的许多副本，因此我们只能将其中一个副本发送给处理器。我们重申，我们的实验比较仅针对WHIMP算法作为WHIMP论文证明了通常使用的基于LSH的技术可证明是更差的。由于WHIMP仅适用于没有高度数左节点的场景，因此我们的三个公共图是为了能够进行比较而假设成立的图 由于WHIMP 算法 具有输出 最优的通 信复杂度 ，我们期望WHIMP具有比LSF- Join更低的通信成本，因为WHIMP的通信成本由图中的边的数量决定。从表1中确实可以看出这一点。然而，LSF-Join权衡了更高的通信成本和跨单个服务器的负载平衡的好处。WHIMP在最坏的情况下不做任何负载平衡，这可能使它不适用于广泛的图表类别，正如我们将在下一节中看到的那样。实际上，WHIMP任务在我们的合成图中失败了具有极端偏斜的合成图 为了说明WHIMP未能解决的情况下，我们提出了一个合成图的结果，包含的核心元素偏度，我们着手解决这项工作。我们预计，相同的结果将适用于几个现实世界的设置，但合成图是足够的比较与WHIMP。事实上，这种随机生成的合成图的动机来自用户行为，即使用户在线消费几乎相同数量的内容（例如视频），1精度取决于用于计算桶中所有对相似性的方法，并且由于我们使用稀疏矩阵乘法，因此对我们来说这是100%。d2个节点随机（不替换）从一小组热节点H U，并随机挑选d2个节点（再次，不替换）从其余的U H。 如果H = γ d，且H N，则这导致右节点具有以1 γ缩放的成对余弦相似性，而热维度对于常数γ具有度O n。在这种情况下，我们预计基于楔形采样的方法会失败，因为热维度有很大的邻域。我们构造了这样一个合成的随机二部图，以下参数：N=1000万，d=20，γ=10。然后，我们重复了与上面描述的真实世界图形相同的实验这一次，我们注意到WHIMP失败了，因为左节点的最大度大约是500K。我们能够运行我们的程序，快速过滤程序的召回和通信成本如表1所示。我们甚至在这个具有严重倾斜度分布的图上实现了高召回率，并且具有合理的通信成本。5结论提出了一种新的分布式近似全对集合相似性搜索算法LSF-Join。该算法的核心思想是使用一种新的LSF方案。 我们展示了一个有效的版本，该计划运行在近线性时间，利用成对独立的散列函数。我们证明了LSF-Join可以有效地在具有极端偏斜的高维数据集中找到低相似性对从理论上讲，我们对LSF-Join的准确性、通信和工作提供了保证。我们的算法改进了哈希连接和基于LSH的方法。 实验表明，LSF-Join在真实和合成图上实现了高精度，即使相似度阈值较低。此外，我们的算法成功的极端倾斜的图，而以前的方法失败。致谢部分工作是在D.Woodruff正在访问GoogleMountain View。D.伍德拉夫还感谢国家科学基金会的支持。CCF-1815840。3004LSF-Join：Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew WWW引用[1] FotoNAfrati ， AnishDasSarma ， DavidMenestrina ， AdityaParameswaran，andJeffrey D Ullman.2012年。使用MapReduce的FuzzyJoins在ICDE。美国电气与电子工程师协会。[2] 照 片 N.Afrati， Anish Das Sarma ， Anand Rajaraman ， Pokey Rule ， SemihSalihoglu，and Jeffrey D. 厄尔曼2014年。使用MapReduce的Hamming和编辑距离的锚点算法。在ICDT。[3] Maha Ahmed Abduljalil，Xun Tang，and Tao Yang. 2013.优化所有对相似性搜索的并行算法。第六届ACM Web搜索和数据挖掘国际会议论文集。203-212[4] 拉涅利·巴拉格利亚，吉安马尔科·德·弗朗西斯·莫拉莱斯，克劳迪奥·卢切斯。2010 年 。 用 mapreduce 实 现 文 档 相 似 性 自 连 接 2010年 IEEE InternationalConferenceon Data Mining。IEEE，731[5] Roberto J Bayardo，Yiming Ma，and Ramakrishnan Srikant.2007年 扩展所有对相似性搜索。在WWW上。ACM。[6] Paul Beame，Par