一个产品小白如何理解布尔表达式检索?

访客4年前关于黑客接单1292

布尔表达式检索是广告受众定向的检索问题,本文从基础概念和 *** 出发,结合实际案例,深入浅出地阐述了布尔表达式检索的作用以及用法。

一个产品小白如何理解布尔表达式检索?

广告主投放广告的本质是流量的采买,所以广告主在投放时会选择自身角度的潜在用户群,也就是当代广告的受众定向售卖方式。现在的广告系统对于大数据量处理及实时性都有着极高的要求,当用户发起广告请求时,广告引擎如何快速筛选出符合定向条件的广告,让索引设计变得极为关键。

基础概念

一般的广告主定向条件都类似于:20岁+女性,25岁+北京

这里的定向条件用布尔表达式进行表示:

a1={age∈(20)∩gender∈(female)}∪{age∈(25)∩geo∈(一线)}

这里的形式即为析取范式(Disjunctive Normal Form,DNF)

每个DNF都可以分解成一个或者多个交集(conjunction),即age∈(25)∩geo∈(一线)

每个交集进一步分解成一个或者多个赋值集(assignment),即age∈(25),geo∈(一线)

双层索引结构设计

算法会维护一个两层的倒排索引,即conjunction-ad,attribute-conjunction。

实际检索过程中:

通过assignment筛选出满足条件的 conjunction,再根据conjunction找出满足条件的广告 *** 。

下面就是一步一步的举例过程!

假设线上有7个广告,定向条件如下:

Ad1:age∈(20)

Ad2:age∈(20)∩ gender∈(female)

Ad3:age∈(20)∩ geo∈(一线)

Ad4:age∈(20)∩ gender∈(female)∩geo∈(一线)

Ad5:age∈(20)∩ gender∈(female)∩geo∈(一线)

Ad6:age∈(20)∩ geo∈(一线)∩ mobile∉(apple)

Ad7:age∈(20)∩ gender∈(female)∩mobile∈(apple)

对应有6种定向条件,将定向条件编辑如下(其中size表示其中含有几个assignment):

Conjunction1:age∈(20),size1

Conjunction2:age∈(20)∩ gender∈(female),size2

Conjunction3:age∈(20)∩geo∈(一线),size2

Conjunction4:age∈(20)∩gender∈(female)∩ geo∈(一线),size3

Conjunction5:age∈(20)∩geo∈(一线)∩ mobile∉(apple),size3

Conjunction6:age∈(20)∩gender∈(female)∩mobile∈(apple),size3

则可以建立从conjunction到ad的之一层倒排索引:

Conjunction1:Ad1

Conjunction2:Ad2

Conjunction3:Ad3

Conjunction4:Ad4,Ad5

Conjunction5:Ad6

Conjunction6:Ad7

根据conjunction 的size大小及包含情况建立从attribute到conjunction的第二层倒排索引(标注conjunction是否含有/不含有该assignment):

Size1:age∈(20),(1,∈)

Size2:

age∈(20),(2,∈)(3,∈)

gender∈(female),(2,∈)

geo∈(一线),(3,∈)

Size3:

age∈(20),(4,∈)(5,∈)(6,∈)

gender∈(female),(4,∈)(6,∈)

geo∈(一线),(4,∈)(5,∈)

mobile∈(apple),(5,∉)(6,∈)

线上请求检索过程

当某次广告请求的定向条件满足某个conjunction,一定满足包含该conjunction的所有广告。如果用size of(query)表示请求中的定向标签个数,如果size of(query)<size of(conjunction),该conjunction一定不满足要求。可以先利用这个判断减少计算。

当线上有一个用户发起了广告请求,该用户的标签为:

age∈(20)∩geo∈(一线)

因为size of(query)=2,则从size为1和2的conjunction中进行查询

Size=2的查询

age∈(20)   (2,∈)(3,∈)

geo∈(一线)  (3,∈)

只有Conjunction3满足条件,对应Ad3

Size=1的查询

age∈(20)   (1,∈)

只有Conjunction1满足条件,对应Ad1

维度爆炸问题

这里的维度组合并不取决于标签的乘积,即2个性别,100个年龄,34个地理……(2*100*34……),而是取决于广告的规模,假设有100w的广告,每个广告的定向标签都不一样,也只是百万级的检索,并且大量的广告受众定向是重复的,远远小于广告数量。

相关文章

微信账户体系科普:什么是UnionId、OpenId与wxopenid?

微信账户体系科普:什么是UnionId、OpenId与wxopenid?

如果你对 UnionId、OpenId、wxopenid这三个概念傻傻分不清,那看这篇文章就对了。了解微信账户体系,能帮助你更好地做小程序设计。 01 概念解释 1. 小程序OpenId OpenI...

互联网商业模式的建立与运转

互联网商业模式的建立与运转

你知道推动互联网商业模式发展的动力是什么吗?互联网商业模式又是如何建立发展并运转的呢?针对以上问题,笔者将予以仔细分析。 划重点 互联网商业模式由价值和成本决定,并由价值牵引。 互联网产品本质就是...

交互规范:响应式让屏幕利用更高,用户体验更佳

交互规范:响应式让屏幕利用更高,用户体验更佳

让用户在不同设备和尺寸的屏幕下看的页面显示效果更佳,屏幕空间利用更高,操作体验更统一,交互方式更符合习惯。本文主要围绕什么是响应式,如何搭建响应系统,响应式网站解析 三个部分进行阐述,在项目中提前定义...

疫情之下,互联网+农批行业的发展机遇与挑战

疫情之下,互联网+农批行业的发展机遇与挑战

疫情之下,许多传统的线下实体经济遭受了重大打击,而互联网新经济则受到了追捧。对于农批行业来说,这场疫情又意味着什么呢?又有哪些机遇呢?笔者在文中给出了自己的思考。 一场突如其来的新型冠状病毒疫情给武...

2020,B站出圈势不可挡

2020,B站出圈势不可挡

B站为什么能够出圈,它做对了哪些事情、搭上了哪趟列车呢?本文从弹幕文化、社区文化、推荐机制和发展潮流等角度解析B站,思考B站的出圈过程。 提起B站,你会想起什么? 鬼畜社区?二次元社区?新年晚会?哔...

Axure高保真:如何在原型图上实现「知乎」问答卡片交互效果?

Axure高保真:如何在原型图上实现「知乎」问答卡片交互效果?

如何在原型图上实现「知乎」问答卡片交互效果呢?来文中看看~ 当我们在使用别人产品时,遇到一些觉得比较好的设计或是一些交互体验上比较舒适的设计时,我们想要将其借鉴过来,但又苦于低保真原型无法将交互效果...