一文看懂谷歌 NYC 算法与优化业务全景：三大项目组12个子领域详解（附重点论文下载）

雷锋网 (公众号：雷锋网) AI 科技评论消息，众所周知，谷歌的研究团队遍布世界各地，而纽约自然也是非常重要的一个地点，尤其是多个谷歌算法研究小组的孕育地。目前，谷歌算法优化团队为谷歌产品的顺利诞生提供了非常多的算法支持，解决了诸多挑战，包括基础优化、隐私保护、提升好友推荐度等多重挑战。

为了让大家更能第一时间了解到谷歌算法及优化的最新进展，谷歌研究院博客于今天更新了消息，谷歌 NYC 算法优化团队公布了主页。而从这个主页中，雷锋网 AI 科技评论也将和大家一窥谷歌算法优化团队的全貌。

目前，团队与谷歌内部的多个团队有着紧密联系，包括广告、搜索、YouTube、Play、基础架构、地理、社交、图像搜索与云服务等，并针对包括机器学习、分布式优化、经济、数据挖掘及数据驱动优化等多个研究领域进行研究。

算法优化与产品技术是紧密结合的，因此也存在诸多的交叉，NYC 算法优化团队的产品经理 Vahab Mirrokni 在更新的博客中指出，网站将从大规模图形挖掘、大规模优化及市场算法等三个子领域进行覆盖，涉及长短期的基础研究及应用研究。

大规模图形挖掘

这一项目组负责为图形算法及分析构建最大规模的数据库，并应用于大量的谷歌产品中。通过数据挖掘及机器学习等方法，研究者将解决图形算法问题，并在顶级期刊或会议上引领基础研究成果。

目前这一项目组有四个子任务，包括：

• 大规模相似性排序（Large-scale Similarity Ranking） ：在 WWW、ICML、VLDB 等顶级期刊／会议上，团队目前基于相似性排序已经提出了一些行之有效的方法，包括 ego－networks和在大规模多分类二分图中计算相似性排名等。

  相关论文：

  Improved Friend Suggestion using Ego-Net Analysis，VLDB 2016.

  论文地址： https://research.google.com/pubs/pub44265.html

  Reduce and aggregate: similarity ranking in multi-categorical bipartite graphs，WWW 2014.

  论文地址： https://research.google.com/pubs/pub42479.html

• 分区平衡（Balanced Partitioning） ：对于大规模图形优化问题而言，分区平衡自然是首要的难题。而在去年 WSDM 2016 上，谷歌所投递的一篇名为《Distributed Balanced Partitioning via Linear Embedding》的论文比起目前最顶尖算法实现了 15%－25% 的分区尺寸缩减。

  相关论文：

  Distributed Balanced Partitioning via Linear Embedding，WSDM 2016
  

  论文地址： https://research.google.com/pubs/pub44315.html

• 集群与连接组件（Clustering and Connected Components） ：谷歌团队表示他们目前已经拥有包括分层聚类，重叠聚类，局部聚类，频谱聚类和连通分量等多种顶尖的应用算法，与此同时，算法比以前研究的最佳算法快 10 到 30 倍，且能够扩展到数十亿图形中。

  相关论文：

  A Local Algorithm for Finding Well-Connected Clusters，ICML 2013

  论文地址： https://research.google.com/pubs/pub41596.html

  Connected Components in MapReduce and Beyond，SOCC 2014

  论文地址： https://research.google.com/pubs/pub43122.html

• 公有／私有图形计算化（Public-private Graph Computation） ：谷歌在基于个人隐私数据的保护上，对创新模型颇有研究。

  相关论文：

  Efficient Algorithms for Public-Private Social Networks，KDD 2015

  论文地址： http://dl.acm.org/citation.cfm?doid=2783258.2783354

大规模优化

这一项目组旨在开发大规模优化技术，并且提升谷歌基础技术的效率与鲁棒性。谷歌目前将这一技术广泛应用于组合优化、在线算法及控制理论等领域，使谷歌得以在大范围计算化基础设施上达成最高的投入产出比。不论是离线或是在线优化，该项目组都秉承增加吞吐量、减少延迟、最大限度地减少资源挤占、最大化高速缓存，并尽可能减少分布式系统中的冗余工作。核心产品包括：

• 一致性哈希（Consistent Hashing） ：谷歌设计了一种无记忆平衡分配算法，能够将动态客户端集合分配给动态服务器集合，使得每个服务器的负载是有界的（bounded），并且每次更新操作的分配不致变化太大。这种技术目前能够用于解决包括 Google Cloud Pub / Sub 的内部项目 ，及开源的 haproxy 等外部项目 。

  相关论文：

  Consistent Hashing with Bounded Loads，CoRR 2016 

  论文地址： https://research.google.com/pubs/pub45756.html

• 基于核心集的分布式优化（Distributed Optimization Based on Core-sets） ：可组合的核心集提供了解决大规模数据集优化问题的有效方法，此外，该技术可用于分布式均衡聚类和分布式子模块最大化等问题。

  相关论文：
  

  Composable core-sets for diversity and coverage maximization，PODS 2014

  论文地址： https://research.google.com/pubs/pub44219.html

  Distributed Balanced Clustering via Mapping Coresets，NIPS 2014

  论文地址： https://research.google.com/pubs/pub42964.html

  Randomized Composable Core-sets for Distributed Submodular Maximization，STOC 2015

  论文地址： https://research.google.com/pubs/pub44222.html

• 谷歌搜索基础架构优化（Google Search Infrastructure Optimization） ：算法优化团队通过与谷歌搜索基础架构团队，构建分布式反馈控制循环。此外，团队还通过增加任意单机的机器查询流，以提升缓存效率。

市场算法（Market Algorithms）

这一项目组对谷歌的整体市场进行分析和设计，并从经济和计算两方面有效提升谷歌业务。所做的研究主要包括优化 DoubleClick 的展示广告，以及赞助的搜索及移动广告。

在过去的几年内，该项目组主要涵盖的业务如下：

• 展示广告研究（Display Ads Research） ：展示广告生态系统为在线随机优化和计算经济学中的各种研究问题提供了绝佳的平台，如全页优化和最优契约设计。这个研究领域的重要组成部分还包括广告交易的竞价优化，通过处理中介参与的竞价活动，优化定价策略，实现预订契约和广告交易的最佳收益管理。

  相关论文：
  

  Whole-page optimization and submodular welfare maximization with online bidders，ACM Conference on Electronic Commerce (EC) 2013

  论文地址： https://research.google.com/pubs/pub41755.html

  Auctions with intermediaries: extended abstract，ACM Conference on Electronic Commerce (EC)  2010

  论文地址： https://research.google.com/pubs/pub36634.html

  Yield Optimization of Display Advertising with Ad Exchange，ACM Conference on Electronic Commerce (EC)  2011

  论文地址： https://research.google.com/pubs/pub36975.html

• 在线随机匹配（Online Stochastic Matching） ：团队已经开发各类新算法，用于在线随机匹配、预算分配及处理流量高峰等任务，此外还包括名为「子模块福利最大化」的通用性问题。

  相关论文：

  Online Stochastic Matching: Beating 1-1/e，FOCS 2009

  论文地址： https://research.google.com/pubs/pub35487.html

  Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation，ACM SIAM 2012

  论文地址： https://research.google.com/pubs/pub37475.html

  Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models，EC 2015

  论文地址： https://research.google.com/pubs/pub44231.html

  Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order，STOC 2015

  论文地址： https://research.google.com/pubs/pub44224.html
  

• 鲁棒随机分配（Robust Stochastic Allocation）：在一篇名为《Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation》的论文中，研究者探究了能在对抗和随机到达模型中实现良好性能的在线算法。在另一篇论文《Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models》中，团队开发了一个混合模型和算法，其近似因子能够随着预测的准确性而变化。

  Simultaneous Approximations for Adversarial and Stochastic Online Budgeted Allocation，ACM／SIAM 2012
  

  论文地址： https://research.google.com/pubs/pub37475.html

  Online Allocation with Traffic Spikes: Mixing Adversarial and Stochastic Models，EC 2015

  论文地址： https://research.google.com/pubs/pub44231.html

• 优化广告客户活动（Optimizing Advertiser Campaigns） ：团队对算法问题进行研究，包括积极结转效应，基于搜索竞价的预算优化，以及具有多个预算限制的简要出价优化策略。

  相关论文：

  Budget Optimization for Online Campaigns with Positive Carryover Effects，WINE 2012

  论文地址： https://research.google.com/pubs/pub40688.html

  Budget Optimization in Search-Based Advertising Auctions，ACM Conference on Electronic Commerce  2007

  论文地址： https://research.google.com/pubs/pub32834.html

  Concise Bid Optimization Strategies with Multiple Budget Constraints，WINE 2014

  论文地址： https://research.google.com/pubs/pub42963.html
  

• 动态机制设计（Dynamic Mechanism Design） ：团队已经开发有效机制用于互联网广告中的复杂设置，包括在线设置和多面体约束。此外，研究者还设计了一个新的动态机制系列，称为银行账户机制（bank account mechanisms），在设计非 CLairvoyant 动态机制上具有有效性，适用于不依赖预测未来步骤的情况。

  相关论文：

  Dynamic Auctions with Bank Accounts，IJCAI 2016

  论文地址： https://research.google.com/pubs/pub45750.html

  Oblivious Dynamic Mechanism Design，SSRN 2016

  论文地址： https://research.google.com/pubs/pub45751.html
  

官网页面： https://research.googleblog.com/

雷锋网 AI 科技评论小结：NYC 算法及优化团队存在已久，但由于其具有交叉性性强、基础研究明显等多种特点，一直没有一个「主阵营」能够为算法及优化团队提供分享最新研究成果的平台。而在包括谷歌大脑团队、自然语言理解团队、欧洲研究团队、安全隐私团队等诸多团队都建立自己的博客和子站后，NYC 算法及优化团队于近日公布的网站主页，自然能够更好地从全局让大家了解谷歌算法优化的过往和未来，并且从这一研究组的系统整理中得到做研究的启迪。

。