ACM通信
研究突出了
技术角度:普及的真实成本
受欢迎的概念在社会中很普遍。我们制作了20世纪早期以来最受欢迎的音乐和电影排行榜th世纪。选举和全民公决主要取决于谁获得的选票最多。在计算机系统中，我们监控社交网络中的追随者和背书，并跟踪其他网络中的浏览量、点击率和连接尝试。
从计算的角度来看，决定哪些物品最受欢迎的问题一开始看起来很简单。给定一个投票数据集，我们可以简单地按项目标识符排序，然后计算分配给每个项目的投票数。当投票数量很大时，我们可能会试图避免排序的开销，并旨在通过数据的几次传递更直接地选出最受欢迎的项。
当我们进一步细化问题时，事情就变得更有趣了。当选票的数量和候选项目的数量变得如此之大，以至于无法对每个候选人进行计数时，会发生什么?在政治选举的背景下，这可能难以置信，但在社会系统中，这是一种日常的现实，它处理着数十亿的行为(代表投票)，或链接(代表条目)。在这里，我们可能只有一次机会看到每一张选票，并且必须在进入下一个观察之前相应地更新我们的数据结构。还有一些变化让事情变得更加复杂:如果投票可以有不同的权重，以反映背书的强度，那该怎么办?如果这些权重可以为负，编码删除对某项的支持，该怎么办?如果计算总分的公式不是权重之和，而是权重之和的平方和，该怎么办?
每一种变化都让问题变得更有挑战性，同时只会增加任何解决方案的普遍性:如果我们可以创建一个算法来处理所有这些变化，那么当它们不适用时，它仍然可以工作。设计有效高效的算法的兴趣如此之高，以至于出现了一个词汇来描述它们:最受欢迎的条目是沉重的打击；当每个更新到达时处理一次，会产生流模型；允许负权重是(一般)旋转栅门模型;设置一个阈值为一个沉重的打击基于移除k最重的物品是k-tail版本;一个基于平方和的加权函数被称为l2．因此，虽然Larsen等人的以下论文解决了k-tail l2在旋转门流模型中的重磅问题，它应该被理解为解决问题的一个最一般的版本。
多年来，针对这个问题的更严格版本的解决方案已经被定义出来，并被用于处理大量数据的部署。例如，Twitter使用重量级算法来跟踪嵌入在网络不同页面的单个推文的浏览次数。一个与此同时，苹果公司将强大的算法与隐私工具相结合，可以私下追踪用户中日益流行的词汇、短语和表情符号。b
一般来说，重打击者算法被定义为两个阶段:收集阶段，从查看更新流中收集数据和统计信息;搜索过程，提取重打击者项目。有一些简单而有效的随机算法可以创建摘要，从而可以高度准确地估计给定项目的最终权重。然而，当有大量可能的条目需要考虑时(例如，将每个tweet和Web上的每个页面结合起来)，提高搜索过程的效率就成为了主要目标。
下面这篇文章的主要重点是建立足够的信息来实现更有效的搜索过程。
因此，下面的论文的主要重点是建立足够的信息，以使更有效的搜索过程。它从基本原理开始逐步发展解决方案，依赖于跨计算机科学的概念:随机划分输入空间以简化核心问题;修改物品标识符的编码，应用编码理论的思想对噪声进行校正;使用基于扩展器图的结构使其更加健壮;最后，利用谱图理论中的聚类方法，确保能够正确提取出重者的标识符。最终的结果是，该算法首次满足解决问题的最小空间开销，同时给出了有效的搜索时间开销。
这为进一步的工作开辟了道路。这种集群方法在实践中实现的效率如何?在其他地方可以找到什么应用程序?虽然确定热门项目是数据分析的一个基本问题，但还可以提出更多问题。流算法领域关注的是寻找有效的算法来统计和查询被视为更新流的大数据。当前的挑战围绕着处理海量数据集来提取预测和推断的统计模型。
脚注
一个。https://skillsmatter.com/skillscasts/6844-count-min-sketch-in-real-data-applications
b。https://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html
查看所附文件，请访问doi.acm.org/10.1145/3339185
数字图书馆是由计算机协会出版的。版权所有©2019 ACM股份有限公司
没有发现记录