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 条评论
登录 后参与评论

相关文章

来自专栏WOLFRAM

版本11.2——追求极致的极限

2004
来自专栏菩提树下的杨过

UML:类图复习-鸡生蛋,蛋生鸡

这是前一阵《高级软件工程》课堂上,老师随堂出的一道讨论题,随手贴在这里: ps: 今天是520,正好聊一些OoXx,关于爱的扯淡话题:) 题目:“鸡生蛋,蛋孵鸡...

1979
来自专栏数据魔术师

运筹学教学 | 十分钟快速掌握最短路算法(附C++代码及算例)

最近被BOSS抽查 运筹学 基本功课, 面对BOSS的突然发问, 机智的小编果断选择了—— 拿 · 出 · 课 · 本 然后BOSS 微微一笑 : “来,实现下...

5458
来自专栏IT派

使用 Python 分析 14 亿条数据

Google Ngram viewer是一个有趣和有用的工具,它使用谷歌从书本中扫描来的海量的数据宝藏,绘制出单词使用量随时间的变化。举个例子,单词 Pytho...

862
来自专栏后台全栈之路

《ArcGIS 地理信息系统教程》概念笔记

之前研究了 GIS,接触到了很多 GIS 的概念。因此找了《 ArcGIS 地理信息系统教程(第 4 版)》来看。书的版本比较老了,不过一些基本概念还是想通的,...

2426
来自专栏工科狗和生物喵

【计算机本科补全计划】CCF 2016_09_04 交通规划 (Dijkstra - 单源最短路径算法)

具体的想法来自下面这篇写的很好的博客,当然,他的代码很复杂,不如我的精简,但是解释这个算法的手法比我好得多!

1392
来自专栏数说工作室

哈希函数的套路 | 文本分析:大规模文本处理(1)

这个系列打算以文本相似度为切入点,逐步介绍一些文本分析的干货。 第一篇中,介绍了文本相似度是干什么的; 第二篇,介绍了如何量化两个文本,如何计算余弦相似度,穿...

4318
来自专栏程序人生 阅读快乐

[C++数值算法]

本书选材内容丰富,除了通常数值方法课程的内容外,还包含当代科学计算大量用到的专题,如求特殊函数值、随机数、排序、最优化、快速傅里叶变换、谱分析、小波变换、统计描...

481
来自专栏杨建荣的学习笔记

字符画,你可能未知的美 (76天)

在平时的工作中,如果接触字符界面时间比较长的时候,都会无意识的感觉到单调,认为字符只能表达一些抽象复杂的东西,对于图形的那种简单和清晰,显得有些力不从心。 今天...

2835
来自专栏PPV课数据科学社区

【学习】excel函数嵌套

1. 前言: 相信很多学习EXCEL的同伴都会时常将一句话挂在嘴边: “请老师教我下这个公式怎么写?” 要么就是: “老师太牛了,这么厉害的嵌套您是怎么写出来...

3449

扫码关注云+社区