没有合适的资源?快使用搜索试试~ 我知道了~
17750Pixie:一个实时为2亿多用户推荐30多亿个项目的系统0Chantat Eksombatchai,Pranav Jindal,Jerry Zitao Liu,Yuchen Liu,RahulSharma,Charles Sugnet,Mark Ulrich,Jure Leskovec Pinterest{pong,pranavjindal,zitaoliu,yuchen,rsharma,sugnet,mu,jure}@pinterest.com0摘要0现代内容发现应用程序中的用户体验在很大程度上取决于高质量的个性化推荐。然而,构建提供此类推荐的系统面临着巨大的挑战,原因是项目数量庞大,用户数量众多,并且要求推荐对用户操作做出响应并实时按需生成。在这里,我们介绍了Pixie,这是一个可扩展的基于图的实时推荐系统,我们在Pinterest上开发和部署了该系统。给定一组用户特定的图钉作为查询,Pixie从数十亿个可能的图钉中实时选择与查询最相关的图钉。为了生成推荐,我们开发了Pixie随机游走算法,该算法利用了Pinterest的30亿个节点和170亿条边的对象图。实验证明,与之前基于Hadoop的生产系统相比,Pixie提供的推荐可以使用户参与度提高多达50%。此外,我们开发了一种图剪枝策略,进一步提高了58%的推荐效果。最后,我们讨论了Pixie的系统方面,其中单个服务器每秒执行1,200个推荐请求,延迟为60毫秒。如今,由Pixie支持的系统贡献了Pinterest上所有用户参与度的80%以上。0ACM参考格式:Chantat Eksombatchai,Pranav Jindal,Jerry ZitaoLiu,Yuchen Liu,Rahul Sharma,Charles Sugnet,Mark Ulrich,JureLeskovec。2018年。Pixie:一个实时为2亿多用户推荐30多亿个项目的系统。在WWW2018:2018年Web会议上,2018年4月23日至27日,法国里昂。ACM,纽约,美国,10页。https://doi.org/10.1145/3178876.318604601 引言0Pinterest是一个可视化目录,拥有数十亿个图钉,图钉是包含描述、链接、图像或视频的可视化书签。Pinterest面临的一个主要问题是从30多亿个项目中为2亿多名月活跃用户提供个性化、引人入胜和及时的推荐。Pinterest的推荐问题规模超出了文献中研究的经典推荐问题。Pinterest拥有数十亿个图钉供推荐系统选择。然而,考虑到只包含数百万个项目的经典推荐系统(电影[5,18],视频[4,7,10],要关注的好友[2,14,15]),Pinterest的情况则不同。0本文根据知识共享署名4.0国际许可(CC BY4.0)发表。作者保留在个人和公司网站上传播作品的权利,并附有适当的归属。WWW2018,2018年4月23日至27日,法国里昂 © 2018IW3C2(国际万维网会议委员会),根据知识共享CC BY 4.0许可发布。ACM ISBN978-1-4503-5639-8/18/04.. https://doi.org/10.1145/3178876.31860460来自数十亿个项目目录的推荐使得推荐问题变得更具挑战性。第二个重要的挑战是推荐必须按需和实时计算。这种实时要求(即每个推荐请求的延迟低于100毫秒)有两个关键原因:(1)用户希望推荐能够响应他们的行为,因此推荐必须按需和实时计算,以便系统能够即时响应用户行为和意图的变化;(2)实时要求还对整个系统的设计带来了巨大的变化。例如,即使推荐只需要一秒钟计算,这对于用户来说也是太长时间了。反过来,这意味着所有用户的推荐都必须在每天的时间表上预先计算和实现。此外,注册用户的总数通常远大于每天活跃用户的数量,因此为不活跃用户更新推荐将浪费大量时间和资源。0现有工作:Pixie。在这里,我们介绍了Pixie,这是一个在Pinterest上部署的可扩展的实时基于图的推荐系统。目前,Pixie推荐的引脚占Pinterest所有用户参与度的80%以上。在A/B测试中,与之前的Pinterest推荐系统相比,Pixie提供的推荐使每个引脚的参与度提高了高达50%。Pinterest的用户查看引脚并将其整理到称为画板的集合中。这样,单个引脚可以被成千上万的用户保存到成千上万个不同的画板中。例如,同一份食谱引脚可以被不同的用户保存到几个不同的画板中,如“食谱”、“快速烹饪”、“素食”或“夏季食谱”。这种手动整理机制提供了一个很好的推荐来源,因为整理捕捉到了对象之间的多方面关系。通过数亿用户将引脚分类整理到画板中,我们得到了一个包含引脚之间多方面关系的对象图。因此,我们可以将Pinterest视为一个包含70亿个引脚和画板以及1000亿条边的巨大的人工策划的二分图。我们使用这个包含引脚和画板的二分图来生成推荐。当用户与Pinterest上的引脚进行交互时,我们的方法使用这些引脚创建一个查询集Q,每个引脚都有自己的权重。查询集是用户特定的,并且动态变化-它可以包含最近与之交互的引脚以及很久以前的引脚。给定查询集Q,我们使用Pixie随机游走算法生成推荐。由于游走访问了画板和引脚,因此可以推荐两种类型的对象。01Pinterest上的所有画板中有超过1000亿个引脚,对应着我们图中的1000亿条边。引脚的唯一数量较小,因为同一个引脚通常保存在许多画板中。0Track: Industry WWW 2018, 2018年4月23日至27日,法国里昂17760对用户来说,该算法快速、可扩展,并且运行时间恒定,与输入图的大小无关。我们的新型Pixie随机游走算法包括以下创新,这对于提供高质量的推荐至关重要:(1)我们以用户特定的方式偏向Pixie随机游走,例如,基于用户的主题和语言;(2)我们允许多个具有不同重要性权重的查询引脚,这使我们能够捕捉用户先前行为的整个上下文;(3)我们的方法将多个独立随机游走的结果结合起来,以奖励与多个查询引脚相关的推荐。结合(2)可以得到更相关的推荐;(4)我们的Pixie随机游走使用特殊的收敛准则,可以进行早期停止,这对于实现实时性能和吞吐量至关重要;最后,(5)我们的Pixie算法允许推荐引脚和画板,这有助于解决冷启动问题。为了推荐新鲜的引脚,Pixie首先推荐画板(而不是引脚),然后将新引脚保存到这些画板上。此外,我们还开发了一种图形策略,通过58%提高推荐的质量。这种策略还可以将图的大小减小六倍,进一步提高Pixie的运行时性能。我们的Pixie算法具有几个重要的优点。该算法具有动态偏向游走的灵活性。例如,在Pixie中,我们偏向于推荐与用户语言相近的内容,从而提高用户参与度。Pixie允许基于多个查询引脚计算推荐。此外,我们可以改变游走长度,以在广泛和狭窄的推荐之间进行权衡。对于旨在提供意外、探索性推荐的Pinterest区域,Pixie可以在图中更远的位置进行游走,以获得更多样化的推荐。另一方面,为了生成狭义和专题推荐,Pixie可以使用较短的游走。Pixie随机游走还具有传统随机游走(或仅计算共同邻居数量)的几个优点:在经典随机游走中,度数较低的节点(边数较少)贡献较少的信号。这是不可取的,因为较小的画板(度数较低的节点)往往更加专注于主题,并且更有可能产生高度相关的推荐。在Pixie随机游走中,我们通过增强较小画板的影响来解决这个问题。最后,Pixie随机游走高效,并且运行时间恒定,与输入图的大小无关。Pixie的部署得益于大容量RAM机器的可用性。特别是,我们使用一组Amazon AWSr3.8xlarge机器,内存为244GB。我们将修剪后的Pinterest图(30亿个节点和170亿条边)适应了约120GB的主内存。这带来了几个重要的好处:(1)随机游走不需要跨机器,带来了巨大的性能优势;(2)系统可以实时回答查询,并且可以并行地在图上执行多个游走;(3)通过简单地向集群中添加更多机器,可以扩展和并行化Pixie。总体而言,Pixie生成推荐所需的时间不到60毫秒(99分位数延迟)。目前,单个Pixie服务器每秒可以处理约1200个推荐请求,整个集群每秒处理近10万个推荐请求。Pixie使用C++编写,并构建在Stanford NetworkAnalysis Platform (SNAP) [20]之上。0本文的剩余部分围绕我们工作的主要贡献进行结构化。在第2节中简要讨论相关工作后,我们在第3.1节中解释了Pixie随机游走算法。我们在第3.2节中讨论了图形修剪,第3.3节中讨论了系统实现。第4节评估了系统和推荐。第5节讨论了Pixie在Pinterest的影响和用例。最后,在第6节中进行总结。02 相关工作0推荐系统是一个广泛研究的领域。在这里,我们将相关工作分为几个方向,并重点关注大规模工业推荐系统。0Web规模的推荐系统。过去已经描述了几个Web规模的生产系统[1,7,21]。然而,与Pixie不同,这些系统不是实时的,它们的推荐是预先计算的。实际上,响应时间低于100毫秒被认为是实时的,因为这样的系统可以被纳入实时服务管道。例如,如果提供推荐只需要1秒钟,那么用户就必须等待太长时间才能生成推荐。在这种情况下,推荐必须预先计算(比如每天一次),然后从键值存储中提供。然而,旧的推荐是过时的,没有吸引力。因此,实时需求至关重要,因为它允许推荐系统立即对用户行为和意图的变化做出反应。实时响应用户可以提供高度吸引人和相关的推荐。我们的实验表明,实时响应用户意图比需要等待几天或几小时才能刷新推荐的情况下,参与度提高了30-50%。其他实时推荐系统的例子包括新闻推荐[9,26]。然而,这些系统只推荐最新的内容。这里的主要区别在于规模-Pinterest的目录比传统的推荐系统能处理的项目多1000倍。0基于随机游走的方法。许多算法使用随机游走来利用图形结构进行推荐[2, 3,28]。也许,与我们这里的工作最接近的是Twitter的“谁要关注”系统[14,15],它将整个关注图放在单台机器的内存中,并运行个性化的SALSA算法[19]。这些类型的蒙特卡罗方法衡量一个节点相对于另一个节点的重要性,并根据这些分数进行推荐[13]。相比之下,我们开发了一种更快且性能更好的新型随机游走算法。0传统的协同过滤方法。更一般地说,我们这里的方法与协同过滤(CF)有关,它通过利用用户和项目之间的交互图来进行推荐,通过匹配具有相似项目偏好的用户。CF依赖于分解用户-项目交互矩阵来生成表示用户和项目的潜在因子[16, 17, 25,30]。然而,基于分解的CF算法的时间和空间复杂度与输入用户-项目图中的节点数量(至少)成线性比例,这使得将这些算法应用于包含数十亿个项目和数百个项目的问题具有挑战性。0Track: Industry WWW 2018, April 23-27, 2018, Lyon, FranceTrack: IndustryWWW 2018, April 23-27, 2018, Lyon, France17770数以百万计的用户。相比之下,我们基于随机游走的推荐算法在时间上是恒定的,与图形/数据集大小无关。0基于内容的方法。在纯粹基于内容的推荐系统中,仅基于内容特征计算项目的表示[24]。许多最先进的Web规模推荐系统是基于内容的,通常使用深度神经网络[6, 8, 11,29]。虽然这些算法可以扩展到大规模数据集,因为参数空间的维度仅取决于特征空间的维度,但这些方法没有利用图形结构的信息(正如我们的实验所示),而这对Pinterest来说是至关重要的。03 提出的方法0Pinterest是一个用户与pin进行交互的平台。用户可以将相关的pin保存到他们选择的boards中。这些boards是相似pin的集合。例如,用户可以创建一个食谱板,并在其中收集与食物相关的pin。Pinterest可以被看作是由其用户创建的boards的集合,其中每个board是一组精选的pin,每个pin可以保存到成千上万个不同的boards中。更正式地说,Pinterest可以被组织成一个无向二分图G = (P, B,E)。这里,P表示一组pin,B表示一组boards。集合P∪B是G的节点集。如果用户将pin p保存到board b中,则pin p∈P和boardb∈B之间存在一条边e∈E。我们使用E(p)表示与pinp连接的board节点(对于与b连接的pin使用E(b))。我们假设G是连通的,在实践中也是如此。Pixie接收一个加权的查询pin集合Q = {(q,wq)}作为输入,其中q是查询pin,wq是其在查询集中的重要性。查询集Q是用户特定的,并在用户每次操作后动态生成,最近交互的pin具有较高的权重,而较久之前的pin具有较低的权重。给定查询Q,Pixie通过模拟一种带有重启的新版本的有偏随机行走来生成推荐。03.1 Pixie随机行走0为了简化对Pixie的解释,我们首先解释基本随机行走,然后讨论如何将其扩展为Pixie使用的一种新的随机行走算法。基本随机行走上的所有创新对于Pixie实现其完整性能是必不可少的。0基本随机行走。考虑一个简单的情况,当用户特定的查询Q包含一个单独的pin q时。给定输入查询pinq,可以在G上从q开始模拟许多短随机行走,并记录每个候选pinp的访问计数,该计数计算随机行走访问pinp的次数。访问的次数越多,它与查询pinq的相关性就越高。基本随机行走过程BasicRandomWalk在算法1中描述[28]。每个随机行走产生一个步骤序列。每个步骤由三个操作组成。首先,给定当前的pinp(初始化为q),我们从E(p)中选择一条连接q和一个boardb的边e。然后,我们通过采样来选择pin p'。02我们注意到有其他定义图G的方法。例如,也可以将用户连接到他们拥有的boards。这里我们呈现这个简化的图,但我们的所有算法也可以推广到更复杂的图。0算法1基本随机行走;q是查询pin;E表示图G的边;α确定行走的长度;N是行走的总步数;V存储pin的访问计数。BasicRandomWalk(q:查询pin,E: 边集,α: 实数,N: 整数)01: totSteps = 0, V = 002: 重复03: currPin = q04: currSteps = SampleWalkLength(α)05: for i = [1: currSteps] do06: currBoard = E(currPin)[rand()]07: currPin = E(currBoard)[randNeighbor()]08: V[currPin]++09: totSteps += currSteps010: 直到totSteps≥N011: return V0边缘e'是连接b和p'的边。第三,当前的pin更新为p',然后步骤重复。步行长度由参数α确定。所有这些短随机步行的步数总和确定了该过程的时间复杂度,我们用N表示这个总和。最后,我们维护一个计数器V,将候选pin映射到访问计数。要获取推荐的pin,我们可以从返回的计数器中提取访问次数最多的pin,并将它们作为查询响应返回。这个过程所花费的时间是恒定的,并且与图的大小无关(由参数N确定)。在描述了基本的随机行走过程之后,我们现在将其推广并扩展为Pixie随机行走。Pixie随机行走算法由算法2和算法3组成,并在基本随机行走的基础上包括以下改进:(1)将随机行走偏向于用户特定的pin;(2)多个查询pin,每个都有不同的权重;(3)多击增强器,增强与多个查询pin相关的pin;(4)提前停止,减少随机行走的步数,同时保持结果的质量。0(1)偏置 Pixie随机游走。以用户特定的方式偏置随机游走非常重要。这样,即使对于相同的查询集合Q,推荐也将是个性化的,并且会因用户而异。例如,Pinterest图中包含具有不同语言和主题的引脚和画板,从用户参与的角度来看,用户以其语言和感兴趣的主题接收推荐非常重要。我们通过改变基于用户特征的随机边选择来解决偏置随机游走的问题。随机游走更倾向于遍历与该用户更相关的边。可以将这些边看作图中具有比其他边更高的权重/重要性。这样,我们以用户特定的方式偏置随机游走,使其专注于图的特定部分并关注特定的引脚子集。实践中,这种修改非常重要,因为它提高了个性化、质量和推荐的主题性,从而提高了用户参与度。Pixie 算法以一组用户特征 U作为输入(算法2)。请注意,在为不同用户和查询的不同 Pixie调用之间,我们可以动态选择偏置边选择。�q∈Q�2(3)Track: IndustryWWW 2018, April 23-27, 2018, Lyon, France17780基于用户和边特征,这增加了 Pixie推荐的灵活性。特别是,PixieRandomWalk 选择具有PersonalizedNeighbor(E,U) 的边,以优先选择对用户 U重要的边。这使我们可以偏好与用户特征/偏好(如语言或主题)匹配的边。从概念上讲,这使我们能够以用户特定的方式偏置游走,但存储和计算开销最小。本质上,可以将这种方法视为为每个用户使用不同的图,其中边的权重适应该用户(但无需为每个2亿多个用户存储不同的图)。出于性能原因,我们目前限制权重仅取可能值的离散集合。我们通过将相似语言和主题的边连续存储在内存中来避免开销,并且 PersonalizedNeighbor(E,U) 是一个子范围运算符。0(2)带权重的多个查询引脚。为了全面地建模用户,根据给定用户的整个历史上下文进行推荐非常重要。我们通过基于多个引脚而不仅仅是一个引脚进行查询来实现这一点。查询集合 Q 中的每个引脚 q被分配一个不同的权重 w q。权重基于用户与引脚互动的时间和类型。为了为查询引脚集合 Q生成推荐,我们按照以下步骤进行。我们从查询引脚集合 Q中的每个查询引脚 q 运行 Pixie随机游走(算法2),并为每个查询引脚 q 维护一个引脚 p 的计数器V q[p]。最后,我们通过应用一种我们稍后描述的新颖公式来组合访问计数。这里的一个重要见解是获得有意义的访问计数所需的步数取决于查询引脚的度。从出现在许多画板中的高度查询引脚进行推荐需要比从度较小的引脚进行推荐需要更多的步骤。因此,我们将分配给每个查询引脚的步数按比例缩放以与其度成比例。然而,挑战在于如果我们将步数按线性比例分配给度,则可能不会分配任何步骤给低度引脚。我们通过为每个引脚构造一个随查询引脚度数递增的函数来实现我们的步骤分配目标,并通过缩放因子 s q 缩放每个引脚的权重 w q。我们构造了以下每个引脚的缩放因子:0s q = |E(q)| ∙ (C - log |E(q)|) (1)0其中,s q 是查询引脚 q ∈ Q 的缩放因子,|E(q)| 是 q 的度,C =max p ∈ P |E(p)|是最大引脚度。这个函数的设计不会给热门引脚带来不成比例的高权重。然后我们按照以下方式分配步数:0Nq = wq Nsq � r ∈ Q sr (2)0其中 Nq 是分配给从查询针脚 q开始的随机行走的总步数。该分布给出了这样的性质,即更多的步数分配给具有高度的起始针脚,而具有低度的针脚也会获得足够数量的步数。我们在算法3的第2行中实现了这一点。0(3) 多次命中增强器。Pixie算法的另一个创新是,对于一组查询针脚Q 的查询,我们更喜欢0与 Q中的多个查询针脚相关的推荐。直观地说,候选针脚与多个查询针脚相关联,它对整个查询的相关性更高。换句话说,与仅来自单个查询针脚的候选者相比,从多个查询针脚获得高访问计数的候选者对查询更相关。这里的见解是,我们让Pixie增加从多个查询针脚访问的候选针脚的得分。我们通过一种新颖的方式聚合给定针脚 p 的访问计数Vq[p] 来实现这一点。我们不仅仅是简单地对所有查询针脚 q ∈ Q上给定针脚 p 的访问计数 Vq[p]进行求和,而是对它们进行转换,以此奖励从多个不同的查询针脚 q多次访问的针脚。0V [p] = � ��0Vq[p] �� �0其中 V [p] 是针对针脚 p 的组合访问计数。请注意,当候选针脚 p仅从单个查询针脚 q的行走中访问时,计数不变。然而,如果候选针脚从多个查询针脚访问,则计数会增加。随后,当从计数器 V中选择访问次数最多的针脚时,多次访问的针脚比例更高。我们在算法3的第5行中实现了这一点。0(4) 提前停止。到目前为止描述的过程将为给定的固定步数 Nq运行随机行走。然而,由于Pixie运行时间严重依赖于我们希望运行的步数,我们希望尽可能少地运行步数。在这里,我们展示了通过根据查询 q 而不是对所有查询针脚使用固定的 Nq 来调整步数 Nq可以大大减少运行时间。我们解决这个问题的方法是在候选针脚集合变得稳定时终止行走,即,随着更多的步数,候选针脚集合几乎不发生变化。由于Pixie推荐了数千个针脚,如果实施得很幼稚,这种监控可能比随机行走本身更昂贵。然而,我们的解决方案通过使用两个整数 np 和 nv 来优雅地克服了这个问题。然后,当至少有 np个候选针脚被访问至少 nv次时,我们终止行走。这种监控易于实现和高效,因为我们只需要一个计数器来跟踪已经被访问至少 nv次的候选针脚的数量(算法2的第12-15行)。我们稍后在第4.2节中展示,提前停止产生的结果几乎与长时间的随机行走相同,但步数减少了一半,从而将算法加速了两倍。03.2 图剪枝0我们方法的另一个重要创新是图的清理和剪枝。图的剪枝提高了推荐质量,同时减小了图的大小,使其适应更小、更便宜的机器,并具有更好的缓存性能以进行服务。原始的Pinterest图拥有70亿个节点和超过1000亿条边。然而,并非所有的Pinterest画板都是专注于特定主题的。大型多样化的画板会使行走在太多方向上扩散,从而导致推荐性能较低。同样,许多针脚被错误地分类到错误的画板中。图剪枝过程清理了图并使其更加专注于特定主题。图剪枝的一个附带好处是大大减少了图的大小。11:nHighVisited++12:totSteps += currSteps17790算法2 具有提前停止的Pixie随机游走算法。0PixieRandomWalk(q: 查询钉子, E: 边集合, U:用户个性化特征, α: 实数, N: 整数, np: 整数, nv: 整数)01: totSteps = 0, V = 空集02: nHighVisited = 003: 重复04: currPin = q05: currSteps = SampleWalkLength(α)06: 对于 i = [1 : currSteps] 做07: currBoard = E(currPin)[PersonalizedNeighbor(E,U)]08: currPin = E(currBoard)[PersonalizedNeighbor(E,U)]09: V[currPin]++010: 如果 V[currPin] == nv 则013: 直到 totSteps ≥ N 或 nHighVisited >np 14: 返回 V0算法3 多个钉子的Pixie推荐。PixieRandomWalkMultiple(Q:查询钉子, W: 查询钉子的权重集合, E: 边集合, U: 用户个性化特征, α:实数, N: 整数)01: 对于所有的 q ∈ Q 做03: Vq = PixieRandomWalk(q, E, U, α, Nq)05: V[p] = ∑q∈Q Vq[p] / 206: 返回 V0将图缩小到适合单台机器的主内存中。不需要将图分布在多台机器上,这带来了巨大的性能优势,因为随机游走不需要在机器之间跳跃。我们的图剪枝问题的解决方法如下。首先,我们通过计算每个画板的内容多样性来量化其熵。我们在每个钉子描述上运行LDA主题模型,以获得概率主题向量。然后,我们使用最新添加到画板上的钉子的主题向量作为输入信号来计算画板的熵。熵较大的画板以及其所有边都从图中删除。另一个挑战是现实世界的图具有偏重于重尾度分布。在Pinterest的情况下,这意味着某些钉子非常受欢迎,并且已经保存到数百万个画板中。对于这样的节点,需要运行多个步骤的随机游走,因为它在大量的网络邻居中扩散。我们通过系统地丢弃高度钉子的边来解决这个问题。然而,我们丢弃边的方式不是随机的,而是丢弃那些钉子被错误分类并且在主题上不属于画板的边。我们使用上述相同的主题向量,并使用主题向量的余弦相似度计算钉子与画板的相似度,然后只保留具有最高余弦相似度的边。具体而言,剪枝的程度由剪枝因子δ确定。我们将每个钉子p的度更新为|E(p)|δ,并丢弃连接p到0通过剪枝,图中包含10亿个画板,20亿个钉子和170亿条边,其中画板的主题向量与p的主题向量的余弦相似度较低。令人惊讶的是,剪枝在两个方面都有益处:(1)将图的大小(和内存占用)减小了六倍;(2)还导致了58%更相关的推荐(详细信息请参见第4.3节)。03.3 实现0在这里,我们将讨论Pixie的实现细节。为了满足实时要求,Pixie依赖于高效的数据结构,我们首先讨论这些数据结构。然后我们讨论如何生成钉子和画板的图形。最后,我们简要讨论了响应Pinterest上各种应用程序构建的Pixie查询的服务器。Pixie是用C++编写的,建立在Stanford Network Analysis Platform (SNAP) [20]之上。0图数据结构。算法2中描述的随机游走过程大部分时间都花在内部循环(第6到13行)。因此,为了使此过程有效,我们需要高效的图和计数器实现。接下来我们描述这些内容。考虑算法2的第7-10行。为了使这些操作高效,我们需要快速采样连接到一个pin的board和连接到一个board的pin。我们接下来设计一个数据结构,在常数时间内执行这些操作。我们开发了一个自定义高度优化的数据结构,其中我们为G的每个节点,即P中的每个pin p和B中的每个boardb,分配一个唯一的ID,范围在|P∪B|之间。该图是作为标准邻接表实现的变体。每个节点与其邻居列表相关联。动态分配每个这样的列表很慢并且会导致内存碎片化,因此我们使用对象池模式将所有邻接列表连接在一起,形成一个连续的数组edgeVec。在edgeVec中,第i个条目offseti是节点i的邻居存储在关联的edgeVec中的偏移量。注意,节点i的邻居数由offset i + 1 - offset i给出。要从存储在edgeVecF中的节点i的邻居中采样一个邻居,我们读取存储在0F = offset i + rand() % (offset i + 1 - offset i).0因此,算法2的第5、8和10行的访问可以在常数时间内高效执行。0访问计数器。在采样一个pinp后,PixieRandomWalk增加访问计数-即pinp被访问的次数(第11行,算法2)。我们开发了一个开放寻址哈希表V,以线性探测的方式高效实现此操作。首先,我们分配一个固定大小的数组,其中每个元素都是一个键值对。对于Pixie,键是G中的pinID,值是访问计数。在增加pin IDk的访问计数时,我们首先使用一个哈希函数(下面描述)来索引到该数组。如果k与存储在索引处的键匹配,则更新值。否则,我们继续探测以下索引,直到找到一个空闲元素或k(即线性探测)。在前一种情况下,我们将键k和值1分配给空闲元素。我们使用线性探测的主要动机是在解决冲突时保持良好的缓存局部性。为了使此过程高效,哈希函数需要快速。我们使用非常轻量级的乘法哈希函数0Track: Industry WWW 2018, April 23-27, 2018, Lyon, France17800(即,将键与固定的素数相乘,对数组大小取模)。根据经验,我们观察到此计数器中的键插入性能与随机数组访问相当。PixieRandomWalkMultiple终止后,数组按值的降序排序,并将具有最高访问计数的pinID作为推荐返回。使用数组实现哈希表可能会有问题;例如,如果数组已满,则需要调整大小。在Pixie的上下文中,步数N为哈希表需要支持的键的数量提供了一个上限,因为具有非零访问计数的pin的数量永远不会超过步数的数量。在初始化哈希表时,我们保守地分配一个大小为N的数组,以避免调整大小。0图生成和修剪。图生成首先运行一个Hadoop管道,然后运行一个图编译器。Hadoop管道包含一系列MapReduce作业,通过Pinterest的数据,检索所有的board和属于它们的pin。管道输出一个包含board和pin之间边的原始文本文件,并将其上传到全局存储。图编译器在一台单一的千兆字节级RAM机器上运行,轮询新的原始图。一旦有新的原始图文件可用,图编译器下载并解析原始数据到内存中,修剪图,然后以二进制格式持久化到磁盘。这些二进制文件可以在机器之间轻松共享。此图生成过程每天运行一次。从磁盘加载图二进制文件到共享内存需要约10分钟。该过程高效,因为加载是从磁盘进行的顺序读取。我们使用LinuxHugePages来增加共享内存的大小,将每个虚拟内存页的大小从4KB增加到2MB,从而将页表条目的数量减少了512倍。太多的页表条目在虚拟机上特别有问题;HugePages选项使Pixie在虚拟机上能够以两倍的速度提供两倍的请求。0Pixie服务器。启动时,每个Pixie服务器将图从磁盘加载到内存中。每个服务器都有一个IO线程池和一个工作线程池。IO线程序列化和反序列化查询和响应。它们将一组钉子交给工作线程。每个工作线程都有自己的计数器,用于收集访问计数。为了避免工作线程之间的同步开销,每个查询由一个单独的工作线程处理。服务器还有一个后台线程,定期检查新图的可用性。当可用时,最新的图被下载到磁盘上。服务器每天重新启动一次,并将最新可用的图加载到内存中。04实验0在本节中,我们评估Pixie并通过实验证明其性能。我们量化Pixie推荐的质量,Pixie算法的运行时性能以及图修剪对推荐的影响。04.1 Pixie推荐质量0Pixie的目标是生成高度参与的推荐。我们通过两种方式量化推荐的质量:(1)给定一个用户,我们的目标是预测他们将与下一个钉子进行互动;(2)0方法 前10 前100 前10000基于内容(文本)1.0% 2.2% 4.8%基于内容(视觉)1.1% 2.4% 4.5%基于内容(组合)2.1% 4.6% 10.5%Pixie(基于图)6.3% 23.1% 52.2%0表1:给定一个查询钉子,预测哪个钉子将被重新钉住。性能通过正确的钉子在前K个中的排名的次数的比例来量化。0我们进行A/B实验,直接测量Pixie推荐对用户参与度的提升。为了比较,我们使用两种最先进的基于深度学习的内容推荐方法,这些方法使用给定钉子的视觉和文本特征来生成推荐。每个钉子都与用户定义的图像和一组文本注释相关联。我们使用这些内容特征来创建钉子的嵌入。为了为给定的查询钉子q生成推荐,我们应用最近邻方法找到最相似的钉子。视觉嵌入是使用VGG-16架构的分类网络的第6个全连接层[12,27]。文本注释嵌入使用Word2Vec模型[23]进行训练。注释的上下文包括与每个钉子相关联的注释。对于基于视觉嵌入生成推荐,我们使用汉明距离,而对于基于文本嵌入生成推荐,我们使用余弦距离。0排名最相关的钉子。我们通过执行以下预测任务来量化推荐的成功:给定一个正在检查查询钉子q的用户,我们的目标是预测哪个其他钉子与查询钉子最相关。在这里,我们依赖用户活动,并说钉子x与q最相关,如果用户在查看q时保存了与之相关的钉子x。我们将其作为一个排名任务来表述,给定一个查询钉子q,我们的目标是对其他2B个钉子进行排名,以便将保存的钉子x尽可能高地排名。我们通过命中率来衡量性能,命中率定义为保存的钉子在前K个结果中的排名次数的比例。表1给出了K =10、100和1000时的命中率。Pixie在所有K值下都能提供更好的推荐性能,并能够准确预测哪个钉子与查询钉子最相关(因此被用户保存)。请注意,由于我们推荐问题的大规模性质,我们不与其他基准方法(如协同过滤或矩阵分解方法)进行比较,因为没有现成的方法可用。0A/B实验结果。评估Pixie推荐质量的最终测试是在一个受控的A/B实验中,其中一组随机用户体验Pixie推荐,而其他用户体验由旧的基于Hadoop的预计算推荐系统提供的推荐,该系统不是实时的。这两组用户之间的参与度差异可以归因于Pixie推荐的提高质量。我们通过量化用户通过点击、点赞或保存来参与的钉子的比例来衡量参与度。表2总结了参与度的提升。0论文:Industry WWW 2018,2018年4月23日至27日,法国里昂17810实验提升0主页动态,每个点的参与度提升+48%相关推荐,每个点的参与度提升+13%画板推荐,每个点的参与度提升+26%本地化,用户本地语言的点+48-75%探索标签,每个点的参与度提升+20%0表2:在不同的Pinterest用户界面上进行的A/B实验总结。Pixie与当前生产系统的参与度提升。0(a) (b)0图1:(a)PixieRandomWalk的运行时间与步数的关系,(b)与查询集大小的关系。0在观察到的13%至48%的增长之间,通过Pixie在受控的A/B实验中推荐的点的数量。04.2 Pixie性能和稳定性0接下来,我们将评估Pixie算法的运行时间性能。0Pixie运行时间。我们评估步数和查询集大小对Pixie运行时间的影响。对于实验,我们随机抽取了20000个大小为1的查询,并计算每个N的平均运行时间。图1(a)显示,运行时间与步数呈线性增长。此外,对于步数小于200000的随机步行,运行时间低于50毫秒。为了评估运行时间与查询大小的关系,我们随机抽取了每个查询大小的20000个查询。我们保持步数不变,并计算具有相同大小的查询的平均运行时间。图1(b)显示,运行时间随查询大小的增加而缓慢增加。这种增加主要是由于缓存未命中引起的。在从查询点开始的随机步行过程中,缓存会被该点周围的邻居填充。当从不同的查询点开始步行时,缓存变得“冷”,需要重新填充。随着查询长度的增加,缓存更容易变“冷”,运行时间略微增加。0顶部结果的方差。像Pixie这样的随机过程产生的推荐结果是不确定的。每次运行Pixie时,访问计数取决于采样的随机数。然而,我们希望推荐的稳定性,即推荐的点集在多次运行中不会发生太大变化。如果我们可以运行足够多的步数使步行收敛,那么推荐将变得稳定。然而,Pixie有严格的运行时间要求,我们无法运行数十亿步的随机步行。我们研究了顶部访问点集的稳定性如何随步数的变化而变化,目的是平衡低运行时间和高稳定性的矛盾要求。我们随机抽取了20000个大小为1的查询,然后运行每个查询100次。然后我们检查每个100个响应的前1000个结果,并计算出至少在K个响应中出现的点的数量(K =50,60,...,100)。图2显示,稳定性随步数的增加而提高。在10万步的情况下,400个结果在所有响应中出现,在50万步的情况下,600个结果在所有响应中出现(K =100)。此外,结果非常稳定。例如,在10万步的情况下,超过800个结果在至少50%的响应中出现(K =50)。最后,在增加步数后获得的稳定性的增益在约20万步后开始下降。因此,我们得出结论,几十万步足以获得稳定的推荐集,并且增加步数不会有太大帮助。0图2:结果方差与步数的关系。0随机步行的结果方差。像Pixie这样的随机过程产生的推荐结果是不确定的。每次运行Pixie时,访问计数取决于采样的随机数。然而,我们希望推荐的稳定性,即推荐的点集在多次运行中不会发生太大变化。如果我们可以运行足够多的步数使步行收敛,那么推荐将变得稳定。然而,Pixie有严格的运行时间要求,我们无法运行数十亿步的随机步行。我们研究了顶部访问点集的稳定性如何随步数的变化而变化,目的是平衡低运行时间和高稳定性的矛盾要求。我们随机抽取了20000个大小为1的查询,然后运行每个查询
下载后可阅读完整内容,剩余1页未读,立即下载
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://profile-avatar.csdnimg.cn/default.jpg!1)
cpongm
- 粉丝: 4
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 收起
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
会员权益专享
最新资源
- 京瓷TASKalfa系列维修手册:安全与操作指南
- 小波变换在视频压缩中的应用
- Microsoft OfficeXP详解:WordXP、ExcelXP和PowerPointXP
- 雀巢在线媒介投放策划:门户网站与广告效果分析
- 用友NC-V56供应链功能升级详解(84页)
- 计算机病毒与防御策略探索
- 企业网NAT技术实践:2022年部署互联网出口策略
- 软件测试面试必备:概念、原则与常见问题解析
- 2022年Windows IIS服务器内外网配置详解与Serv-U FTP服务器安装
- 中国联通:企业级ICT转型与创新实践
- C#图形图像编程深入解析:GDI+与多媒体应用
- Xilinx AXI Interconnect v2.1用户指南
- DIY编程电缆全攻略:接口类型与自制指南
- 电脑维护与硬盘数据恢复指南
- 计算机网络技术专业剖析:人才培养与改革
- 量化多因子指数增强策略:微观视角的实证分析
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)