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

崔巍Bella 2023-07-22 07:47:40

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

基础概念

一般的广告主定向条件都类似于：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