戴老师的博客 - 广告
type: channel
link: https://tushu.info/category/%E5%B9%BF%E5%91%8A/
description: 广告
items: 基于布尔表达式的广告索引设计

基于布尔表达式的广告索引设计
type: item
date: 2026-07-09T04:29:14+00:00
description: 问题背景广告主在广告投放平台勾选定向条件后，当用户发起请求时，广告引擎需要快速筛选出符合定向条件的广告。通常容易想到如下代码结构：Attributes = list<Attribute> // 用户的流量标签，例如：用户的年龄、性别... for (Ad ad : ads.html) { check attributes for each ad. // 对于每一个广告检查是不是符合流量标签，挑选广告 }然而，该方案的时间复杂度随广告数量线性增长，显然无法满足业务发展需要。无论是在品牌广告还是竞价广告场景中，该问题普遍存在。自然地，我们想到建立索引，那么索引结构如何设计就成为问题的关键。索引结构两层索引结构为了说明两层索引结构，我们定义如下术语：Attribute（属性）：单个流量标签，包含两个信息：属性类别和属性取值。例如：AGE: 5。Assignment（赋值）：多个流量标签组成的用户画像。例如：AGE: 5, GENDER: 1, NETWORK: 1。Conjunction（合取范式）：布尔表达式的合取范式。例如：AGE ∈ (4,5,6.html) ∧ GENDER ∈ (1.html)。Predicate（谓词）：布尔表达式的一个子表达式。例如：AGE ∈ (4,5,6.html)，GENDER ∈ (1.html)。两层索引设计的主要思想是：从 Assignment 找出包含这些流量标签的 Conjunction，筛选满足条件的 Conjunction，再根据筛选出的 Conjunction 找出满足条件的广告集合。下面我们举个例子：假设线上有 7 个广告，它们的定向条件如下。其中 Ad3 和 Ad7 定向条件相同；Ad6 包含反向定向，即该广告不能出在 AppInterest 标签为 19-1 的用户上面。Ad1 定向：PlacementType ∈ (2.html) Ad2 定向：PlacementType ∈ (2.html) ∧ AppInterest ∈ (15-0, 19-1.html) ∧ InstalledApp ∈ (30202.html) Ad3 定向：PlacementType ∈ (2.html) ∧ AppInterest ∈ (15-0, 19-1.html) ∧ NetworkType ∈ (1.html) Ad4 定向：PlacementType ∈ (2.html) ∧ AppInterest ∈ (19-1.html) Ad5 定向：PlacementType ∈ (2.html) ∧ InstalledApp ∈ (30202.html) ∧ NetworkType ∈ (1.html) Ad6 定向：PlacementType ∈ (2.html) ∧ IpGeo ∈ (141.html) ∧ NetworkType ∈ (1.html) ∧ AppInterest ∉ (19-1.html) Ad7 定向：PlacementType ∈ (2.html) ∧ AppInterest ∈ (15-0, 19-1.html) ∧ NetworkType ∈ (1.html)对应定向条件可归纳为 6 个 Conjunction，编号如下：conjunctionIdconjunctionsize1PlacementType ∈ (2.html)12PlacementType ∈ (2.html) ∧ AppInterest ∈ (19-1.html)23PlacementType ∈ (2.html) ∧ IpGeo ∈ (141.html) ∧ NetworkType ∈ (1.html) ∧ AppInterest ∉ (19-1.html)34PlacementType ∈ (2.html) ∧ InstalledApp ∈ (30202.html) ∧ NetworkType ∈ (1.html)35PlacementType ∈ (2.html) ∧ AppInterest ∈ (15-0, 19-1.html) ∧ InstalledApp ∈ (30202.html)36PlacementType ∈ (2.html) ∧ AppInterest ∈ (15-0, 19-1.html) ∧ NetworkType ∈ (1.html)3其中，conjunctionId 为编号，conjunction 为布尔表达式内容，size 为 ∈ 语句的个数。可以建立 conjunctionId 到 Ad 的索引如下：conjunction1 -> Ad1 conjunction2 -> Ad4 conjunction3 -> Ad6 conjunction4 -> Ad5 c…