Now 直播发现页短视频瀑布流优化

发现页是Now直播短视频的主要曝光平台(如下图),内容以运营人工筛选为主,瀑布流式展示。

为了兼顾短视频质量和时效性,短视频排序采用了重力算法:

H为短视频的质量分,通过观看,点赞,评论,转发等数据加权求和计算,T为短视频发布时间戳,T0位基准时间,取发现页最早发布的短视频创建时间戳,单位均为秒。A为时间系数,根据发现页短视频的平均更新间隔,取36000(10小时)。该算法的效果是,发布时间接近,质量分高的短视频靠前,随着时间推移,短视频不断下沉,削弱头部曝光产生的马太效应。

为了提高内容的新鲜感,我们希望用户在每次下拉刷新以及翻页的时候,都能看到新的短视频,同时在短视频列表头部加入新的短视频时,能得到优先展示,如下图所示:

左图为首屏显示的短视频,如在此时,短视频列表顺序发生了更新,C+和D+插入了EF的前面,我们希望在下次刷新的时候,优先插入C+、D+。实现这个需求最简单的方法是保存用户最近观看过的全部短视频作为过滤器,每次返回列表的时候,从头部开始遍历,去掉用户看过的短视频。显然,过滤器的容量,决定了短视频列表的最大展示深度。根据产品需求,发现页需要展示最近一个月的短视频,大约4000个,平均每个短视频id的长度为50字节,这个过滤器如果用传统的redis set等手段实现,存储成本和过滤效率都比较低,针对这个问题,我们采用了一个简单而强大的数据结构---布隆过滤器。

Bloom Filter(布隆过滤器)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省。

下面我们具体来看Bloom Filter是如何用位数组表示集合的。初始状态时,Bloom Filter是一个包含m位的位数组,每一位都置为0。

为了表达S={x1, x2,…,xn}这样一个n个元素的集合,Bloom Filter使用k个相互独立的哈希函数(Hash Function),它们分别将集合中的每个元素映射到{1,…,m}的范围中。对任意一个元素x,第i个哈希函数映射的位置hi(x)就会被置为1(1≤i≤k)。注意,如果一个位置多次被置为1,那么只有第一次会起作用,后面几次将没有任何效果。在下图中,k=3,且有两个哈希函数选中同一个位置(从左边数第五位)。

在判断y是否属于这个集合时,我们对y应用k次哈希函数,如果所有hi(y)的位置都是1(1≤i≤k),那么我们就认为y是集合中的元素,否则就认为y不是集合中的元素。下图中y1就不是集合中的元素。y2或者属于这个集合,或者刚好是一个false positive。

我们使用MurmurHash和bitset实现了一个可以序列化成整形数组的布隆过滤器,可以利用redis支持的简单key-value数据结构进行存取,在本地实现高效的过滤运算,一个能保存4000个短视频id的布隆过滤器,只占用不到8KB的空间,get&set的效率都比较高。

因为布隆过滤器容量有限,且无法删除元素,需要配合重建策略使用。我们用redis维护了一个最近观看的100个短视频id,当布隆过滤器空间利用率超过百分之50的时候,清空并使用这100个id进行重建,避免了极端情况下的重复问题。

短视频瀑布流刷新涉及到大量的图片下载,在图片加载期间,会显示默认底图(如下图):

为了优化图片加载体验,尤其是网络条件较差时的展示效果,我们采用了预加载图片主色调的方法,即离线计算好短视频封面的主色调RGB值,使前端在完成图片下载前用主色调代替默认的底图,平滑图片的加载过程:

关于图片主色调的提取,我们尝试了多种算法,最终参考了《基于OTSU分割与K-均值聚类的MPEG-7主颜色提取算法》这篇论文,实现了短视频封面图片主色调的提取,基本方法如下:

  1. 提取图片的RGB空间值,转化为HSV空间值
  2. 对HSV空间下的像素点进行k均值迭代。
  3. 选择点数量最多的一个聚类,将聚类中心的HSV空间值转换为RGB空间值。

以上几点是我们在NOW直播发现页瀑布流迭代优化中的一些尝试和技术总结,希望能给大家在开发Feeds流类型应用时提供一些参考,如有意见或建议,可与本文作者联系。

原创声明,本文系作者授权云+社区-专栏发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

杨世宇的专栏

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏宏伦工作室

200行Python代码实现2048

1424
来自专栏Java Web

背包问题

问题描述 假设你是一个贪婪的小偷,背着可以装35磅重东西的背包,在商场伺机偷窃各种可以装入背包的商品。 ? 你力图往背包中装入价值最高的商品,你会用哪种算法呢?...

2485
来自专栏java达人

通过人工智能编写自修改/自完善的程序

作者:Kory Becker 译者: Mr派 来源:http://www.primaryobjects.com/2013/01/27/using-artific...

1818
来自专栏华章科技

Python爬虫新手进阶版:怎样读取非结构化网页、图像、视频、语音数据

导读:常见的数据来源和获取方式,你或许已经了解很多。本文将拓展数据来源方式和格式的获取,主要集中在非结构化的网页、图像、视频和语音。

663
来自专栏大数据挖掘DT机器学习

用python实现决策树ID3算法,对隐形眼镜类型预测

本节讲解如何预测患者需要佩戴的隐形眼镜类型。 1、使用决策树预测隐形眼镜类型的一般流程 (1)收集数据:提供的文本文件(数据来源于UCI数据库) (2)准备数据...

3707
来自专栏机器学习和数学

[数据结构和算法]《算法导论》动态规划笔记(1)

动态规划是求解最优化问题的方法,这类问题有很多可行解,每个解都有一个值,我们希望寻找具有最优值的解。我们称这个解为问题的一个最优解,而不是最优解,因为可能有多个...

35310
来自专栏量子位

Facebook发布张量理解库,自动编译高性能机器学习核心

? Facebook AI Research今天发布了张量理解(Tensor Comprehension),这是一个C ++库,也是一种数学语言,它能够自动、...

3335
来自专栏前端架构

计算机模型与体系架构的发展——从图灵机到云计算机

按照图灵(Alan Turing)给出的计算机模型,计算机是由一个有限状态读写头和一个存储器构成。有限状态读写头从一个初始状态开始,对存储器上的(输入)数据进行...

652
来自专栏Crossin的编程教室

用 Python 实现一个简单的微信红包算法

今年过年各位一定在微信里抢了不少红包。那么当别人是手气王而你只抢到1分钱的时候,你有没有想过,如果你来实现红包的分配算法,会怎么写? 这里我给一个简单的实现方案...

3467
来自专栏性能与架构

算法中描述复杂度的大O是什么意思?

简介 算法是解决问题的方法,通常一个问题会有多种解决方法,就是有多种算法,那么我们如何决定哪个算法更好或者更高效呢? 为了描述一个算法的效率,就用到了这个大O,...

2895

扫码关注云+社区