大量中小广告主参与的竞价广告市场中, 复杂的定向条件对检索技术提出了新的要求。倒排索引是搜索引擎的关键技术, 而广告检索上也采用这样的框架。但是广告的检索问题也有一些自身的特点和需求, 基本的倒排索引技术在广告检索中遇到两个新问题。

  1. 广告的定向条件组合可以看成是一个由与或关系连接的布尔表达式,这样的文档显然与搜索引擎面对的BoW文档不太一样,这里存在着有针对性的检索性能优化空间。

  2. 在上下文关键词或和用户标签比较丰富时, 广告检索中的查询可能相当长, 甚至会由上百个关键词组成, 这种情况下的检索也与搜索引擎中主要由1~4个关键词组成的查询有很大区别。 试想, 如果将100个关键词同时输入搜索框中, 返回的结果会是你想要的吗?

这些差异使得广告中使用的检索技术在基本的倒排索引之上有所发展。

布尔表达式检索

基本概念

  • Doc DNF: \((age \in \{3\} \wedge state \in \{NY\} ) \vee (state \in \{CA\} \wedge gender \notin \{M\})\)

  • Conjunction: \((age \in \{3\} \wedge state \in \{NY\} )\), \((state \in \{CA\} \wedge gender \notin \{M\})\)

  • Assignment: \(age \in \{3\}\), \(state \in \{NY\}\), \(state \in \{CA\}\), …

  • sizeof(Conjunction): conjunction包含非\(\notin\)的Assignment的个数。

基本思想

  • 某查询满足conjunction, 也就满足包含此conjunction的doc;
  • 维护两层倒排关系: \(Conjunction -> DocId\), \(Assignment -> ConjunctionId\);
  • Assignment约束: 如果\(sizeof(Conjunction)\)大于\(sizeof(query)\), 则无需考虑。

Index算法

  1. 基于\(ConjunctionId -> DocId\)建立第一层索引:
  • 遍历文档DNF的Conjunction, 如果为新的, 则分配一个新ID(从0递增), 否则, 用之前分配的ConjunctionID; 文档分配DocID(从0递增); 写入conjunction到doc的倒排关系, 形成第一层Index。
  1. 对于上一步出现的新Conjunction, 建立第二层Index:
  • 将Conjunction切分成一组(键,值)对, 例如, 将\(age \in \{3, 4\}\)分解成\(age \in \{3\}\)\(age \in \{4\}\)两个Key, 这些Key作为第二层倒排索引的建, 而“\(\in\)”和“\(\notin\)”操作符放在倒排链表的具体元素(Entry)上, 每个Entry的形式: \((ConjunctionId, \in | \notin)\)

  • 利用上文所说的Assignment约束, 我们可以做的优化是将这一倒排索引按照\(sizeof(Conjunction)\)分成若干部分, 以提高检索效率。

  • 对于$sizeof(Conjunction) = 0 $ 的Conjunction, 添加一个特殊的Term: \((Z, \in)\)

  • 每个Key对应的倒排链表(Posting List)内部entry按规定比较方式升序排列排列;

  • 具有相同的\(sizeof(Conjunction)\)的Posting List之间, 按照各Posting List中第一个Entry进行升序排列;

A posting entry \(e_1\) is “smaller” than another entry \(e_2\) if the connjunction ID of \(e_1\) is smaller than \(e_2\). In the case where both conjunction IDs are the same (in which case \(e_1\) and \(e_2\) are in different lists), \(e_1\) is smaller than \(e_2\) only if \(e_1\) contains a \(\notin\) and \(e_2\) contains a \(\in\).

Index实例

  • Doc DNF

\(doc_1 = (age \in \{3\} \wedge state \in \{NY\}) \vee (state \in \{CA\} \wedge gender \in \{M\}) = c_1 \vee c_4\)

\(doc_2 = (age \in \{3\} \wedge state \in \{F\}) \vee (state \notin \{CA:NY\} ) = c_2 \vee c_6\)

\(doc_3 = (age \in \{3\} \wedge gender \in \{M\} \wedge state \notin \{CA\}) \vee (state \in \{CA\} \wedge gender \in \{F\}) = c_3 \vee c_7\)

\(doc_4 = (age \in \{3:4\}) \vee (gender \in \{M\} \wedge state \in \{CA\}) = c_5 \vee c_4\)

\(doc_5 = (state \notin \{CA:NY\} \vee (age \in \{3:4\}) = c_6 \vee c_5\)

\(doc_6 = (state \notin \{CA:NY\} ) \vee (age \in \{3\} \wedge state \in \{NY\}) \vee (state \in \{CA\} \wedge gender \in \{M\}) = c_6 \vee c_1 \vee c_4\)

\(doc_7 = (age \in \{3\} \wedge state \in \{NY\}) \vee (state \in \{CA\} \wedge gender \in \{F\}) = c_1 \vee c_7\)

  • 倒排 conjunction -> doc
conjunctionId docId
\(c_1\) \(doc_1\), \(doc_6\), \(doc_7\)
\(c_2\) \(doc_2\)
\(c_3\) \(doc_3\)
\(c_4\) \(doc_1\), \(doc_4\), \(doc_6\)
\(c_5\) \(doc_4\), \(doc_5\)
\(c_6\) \(doc_2\), \(doc_5\), \(doc_6\)
\(c_7\) \(doc_3\), \(doc_7\)
  • 倒排 term -> conjunction
\(K\)(conjunctionSize) Key Posting List
0 \((state, NY)\) \((c_6, \notin)\)
- \((state, CA)\) \((c_6, \notin)\)
- \(Z\) \((c_6, \in)\)
\(K\)(conjunctionSize) Key Posting List
1 \((age, 3)\) \((c_5, \in)\)
- \((age, 4)\) \((c_5, \in)\)
\(K\)(conjunctionSize) Key Posting List
2 \((age, 3)\) \((c_1, \in)\), \((c_2, \in)\), \((c_3, \in)\)
- \((state, NY)\) \((c_1, \in)\)
- \((gender, F)\) \((c_2, \in)\), \((c_7, \in)\)
- \((gender, M)\) \((c_3, \in)\), \((c_4, \in)\)
- \((state, CA)\) \((c_3, \notin)\), \((c_4, \in)\) ,\((c_7, \in)\)

查询算法

Algorithm: The Conjunction algorithm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
package booleanindex;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class BooleanIndexer {
/**
* Assignment 定义
* attribute: 改assignment指定的标签类型
* value: value值
* belong: 属于 or 不属于
*/
public static class Assignment {
public String attribute;
public boolean belong;
String value;

public Assignment(String attribute, boolean belong, String value) {
this.attribute = attribute;
this.belong = belong;
this.value = value;
}
}

public class Conjunction {
public List<Assignment> assignments;

public Conjunction(List<Assignment> assignments) {
this.assignments = assignments;
}
}

public class DNF {
public List<Conjunction> conjunctions;

public DNF(List<Conjunction> conjunctions) {
this.conjunctions = conjunctions;
}
}

public static class Key {
private String attribute;
private String value;

public Key(String attribute, String value) {
this.attribute = attribute;
this.value = value;
}

public String getAttribute() {
return attribute;
}

public void setAttribute(String attribute) {
this.attribute = attribute;
}

public String getValue() {
return value;
}

public void setValue(String value) {
this.value = value;
}

@Override
public String toString() {
return String.format("(%s,%s)", attribute, value);
}

@Override
public int hashCode() {
return this.toString().hashCode();
}

@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
final Key key = (Key) o;
return attribute.equals(key.attribute) &&
value.equals(key.value);
}
}

public static class Entry {
private int conjunctionId;
private boolean belong;

public Entry(int conjunctionId, boolean belong) {
this.conjunctionId = conjunctionId;
this.belong = belong;
}

public int getConjunctionId() {
return conjunctionId;
}

public void setConjunctionId(int conjunctionId) {
this.conjunctionId = conjunctionId;
}

public boolean isBelong() {
return belong;
}

public void setBelong(boolean belong) {
this.belong = belong;
}

@Override
public String toString() {
return "Entry{" +
"conjunctionId=" + conjunctionId +
", belong=" + belong +
'}';
}
}

/**
* PostingList 用于存储(ConjunctionId, belongValue)的倒排拉链
*/
public static class PostingList {
public int currentPos; // 记录当前倒排拉链的遍历位置
public List<Entry> postingList; // 倒排拉链

public PostingList(List<Entry> postingList) {
this.currentPos = 0;
this.postingList = postingList;
}

public int size() {
return this.postingList.size();
}

public Entry get(int index) {
return this.postingList.size() <= index ? null : this.postingList.get(index);
}

public Entry getCurrentEntry() {
return postingList.get(currentPos);
}

public void skipTo(int nextConjunctionId) {
for (; currentPos < postingList.size(); currentPos++) {
if (postingList.get(currentPos).conjunctionId >= nextConjunctionId) {
break;
}
}
}
}

/**
* Key -> Posting List
* 键: Pair(attribute, value)
* 值: PostingList
*/
public static class PostingListMap {
public Map<Key, PostingList> postingListMap;

public PostingListMap(Map<Key, PostingList> postingListMap) {
this.postingListMap = postingListMap;
}

public PostingListMap() {
this.postingListMap = Collections.emptyMap();
}

/**
* 根据查询assignments获取当前满足条件的Posting Lists倒排
*
* @param assignments
* @return
*/
public List<PostingList> getPostingLists(List<Assignment> assignments) {
List<PostingList> result = new ArrayList<>();

Set<Key> keySet = new HashSet<>();

assignments.forEach(assignment -> keySet.add(new Key(assignment.attribute, assignment.value)));

postingListMap.forEach((key, value) -> {
if (keySet.contains(key)) {
result.add(value);
}
});
return result;
}

}

private Map<Integer, PostingListMap> conjunctionIndex;
private int maxConjunctionSize;

public Set<Integer> retriveWithDNF(List<Assignment> assignments) {
Set<Integer> result = new HashSet<>();

int k = Math.min(maxConjunctionSize, assignments.size());
for (; k >= 0; k--) {
/**
* List of posting lists matching A for conjunction Size K
* (currentPosition, postingList) pair
*/
List<PostingList> postingLists =
conjunctionIndex.getOrDefault(k, new PostingListMap()).getPostingLists(assignments);

int currentSize = k;
if (currentSize == 0) {
currentSize = 1;
}

/**
* Too few posting lists for any conjunction to be satisfied
*/
if (postingLists.size() < currentSize) {
continue;
}

/**
* To make sure there is still enough conjunctions to match
* 因为当前部分倒排索引的ConjunctionSize = k, 所以如果需要进一步判断的assignment不足k个
* 就可以剪枝, 没有必要进行进一步判断了
*/
sortByCurrentEntries(postingLists);
while (postingLists.get(currentSize - 1).currentPos < postingLists.get(currentSize - 1).postingList.size()) {
Entry currentEntry0 = postingLists.get(0).getCurrentEntry();
Entry currentEntryK = postingLists.get(currentSize - 1).getCurrentEntry();

/**
* nextConjunctionID is the smallest possible ID after current conjunctionID
*/
int nextConjunctionId = currentEntryK.getConjunctionId();

/**
* Check if the first K posting lists have the same conjunction ID
* in their current entries
*/
if (currentEntry0.getConjunctionId() == currentEntryK.getConjunctionId()) {
/**
* Reject conjunction if a not belong is violated
*/
if (!currentEntry0.isBelong()) {
Integer rejectId = currentEntry0.getConjunctionId();
for (int l = currentSize; l < postingLists.size(); l++) {
/**
* Skip to smallest conjunctionID where conjunctionID > rejectID
*/
Entry currentEntryL = postingLists.get(l).getCurrentEntry();
if (currentEntryL.conjunctionId == rejectId) {
postingLists.get(l).skipTo(rejectId + 1);
} else {
/**
* Break out of for loop
*/
break;
}
}
} else {
/**
* current conjunction id is fully satisfied
*/
result.add(currentEntryK.getConjunctionId());
}
nextConjunctionId = currentEntryK.getConjunctionId() + 1;
}

for (int l = 0; l <= currentSize - 1; l++) {
postingLists.get(l).skipTo(nextConjunctionId);
}
sortByCurrentEntries(postingLists);
}
}

return result;
}

/**
* Sort posting lists by current entry
* with: o1.conjunctionId < o2.conjunctionID and if o1.conjunctionId = o2.conjunctionId than not belong is smaller
* @param postingLists
*/
private void sortByCurrentEntries(List<PostingList> postingLists) {
postingLists.sort((o1, o2) -> {

Entry value1 = o1.get(o1.currentPos);
Entry value2 = o2.get(o2.currentPos);

if (value1 != null && value2 != null) {
if (value1.getConjunctionId() == value2.getConjunctionId()) {
return value1.belong ? 1 : -1;
} else {
if (value1.getConjunctionId() > value2.getConjunctionId()) {
return 1;
} else {
return -1;
}
}
} else {
if (value1 == null && value2 == null) {
return 0;
} else {
return value1 == null ? 1 : -1;
}
}
});
}

/***
* Just as example from [Indexing Boolean Expressions]
*
* @param args
*/
public static void main(String[] args) {
BooleanIndexer booleanIndexer = new BooleanIndexer();

List<Entry> list0_0 = new ArrayList<>();
list0_0.add(new Entry(6, false));
List<Entry> list0_1 = new ArrayList<>();
list0_1.add(new Entry(6, true));
Map<Key, PostingList> postingListMap0 = new HashMap<>();
postingListMap0.put(new Key("state", "CA"), new PostingList(list0_0));
postingListMap0.put(new Key("Z", "Z"), new PostingList(list0_1));
PostingListMap postingListMapSize0 = new PostingListMap(postingListMap0);

List<Entry> list1_0 = new ArrayList<>();
list1_0.add(new Entry(5, true));
Map<Key, PostingList> postingListMap1 = new HashMap<>();
postingListMap1.put(new Key("age", "3"), new PostingList(list1_0));
PostingListMap postingListMapSize1 = new PostingListMap(postingListMap1);

List<Entry> list2_0 = new ArrayList<>();
list2_0.add(new Entry(1, true));
list2_0.add(new Entry(2, true));
list2_0.add(new Entry(3, true));
List<Entry> list2_1 = new ArrayList<>();
list2_1.add(new Entry(3, false));
list2_1.add(new Entry(4, true));
List<Entry> list2_2 = new ArrayList<>();
list2_2.add(new Entry(3, true));
list2_2.add(new Entry(4, true));
Map<Key, PostingList> postingListMap2 = new HashMap<>();
postingListMap2.put(new Key("age", "3"), new PostingList(list2_0));
postingListMap2.put(new Key("state", "CA"), new PostingList(list2_1));
postingListMap2.put(new Key("gender", "M"), new PostingList(list2_2));
PostingListMap postingListMapSize2 = new PostingListMap(postingListMap2);

booleanIndexer.maxConjunctionSize = 3;
booleanIndexer.conjunctionIndex = new HashMap<>();
booleanIndexer.conjunctionIndex.put(0, postingListMapSize0);
booleanIndexer.conjunctionIndex.put(1, postingListMapSize1);
booleanIndexer.conjunctionIndex.put(2, postingListMapSize2);

List<Assignment> assignments = new ArrayList<>(3);
assignments.add(new Assignment("age", true, "3"));
assignments.add(new Assignment("state", true, "CA"));
assignments.add(new Assignment("gender", true, "M"));

Set<Integer> result = booleanIndexer.retriveWithDNF(assignments);

// 结果输出: [4, 5]
System.out.println(result.toString());
}

}

搜索过程

参见原文:Indexing Boolean Expressions

时间复杂度分析

\(O(log(|S|) × |C| × P_{avg})\)

  • 原文中算法对PostingList的排序会借助额外的堆结构, 因此排序的时间复杂度会降到\(log(|S|)\);
  • \(|C|\) 是Index中Conjunction中的数量;
  • \(P_{avg}\)是平均每个conjunction包含的predicts数量;

Notice: 需要注意的一点是, 上面的算法相比于直接线性的遍历所有的布尔表达式(\(O(|C| × P_{avg})\))的平均时间复杂度要高, 但是在\(|S|\)的数量很小的情况下(这时候\(log(|S|)\)很小), 利用skipTo的剪枝操作, 算法的效果是有明显提升的。

相关性检索

竞价广告与搜索的检索问题还有一点不同, 有时, 竞价广告系统需要处理很多个标签组成的查询。 让我们考虑上下文定向的情形: 当通过网页内容的关键词来匹配广告候选时, 往往需要十个甚至几十个关键词去查询广告, 再进行eCPM排序。 在这一情形下, 如果仍然采用一般搜索引擎查询的处理办法, 则会陷入两难的境地。 如果假设各关键词之间是“与”关系, 基本上不可能得到任何匹配结果; 如果假设各关键词之间是“或”关系, 那么检索阶段就会返回大量相关性很差的候选, 给后续排序效率带来很大的挑战。

同样地, 当用户兴趣标签较为丰富时, 也存在类似的挑战。 简单的比较一下搜索与搜索重定向广告就可以理解为什么展示广告的查询信号会丰富很多: 在搜索中, 仅仅需要根据用户当前输入的关键词进行检索; 而在搜索重定向广告中虽然使用的也是搜索信号, 但是需要将用户一段时间内的搜索关键词全部考虑, 显然这样的查询要长了很多。 在此也可以看出, 搜索广告完全可以采用一般的检索技术, 但是展示广告需要有新的方案。

考虑上面问题产生的原因会发现, 在长查询的检索情形下, 我们实际上希望的是查询与广告候选见得相似度尽可能的高, 但任何一个关键词是否出现在文档中其实都不关键。 这样以查询和文档间的相似度为目标的检索问题成为相关性检索。

解决相关性检索的基本思路是在检索阶段就引入某种评价函数, 并以此评价函数的评价结果决定返回哪些候选。 评价函数的设计有两个要求: 一个是合理性, 即与最终排序时使用的评价函数近似; 而是高效性, 即需要在检索阶段实现快速评价算法, 否则就与在排序阶段对每个候选分别计算没有差别了, 研究表明当选用线性评价函数(变量为各个标签或关键词)且各权重为正时, 是可以构造出这样的快速检索算法的。 假设线性评价函数的形式如下式所示: \[score(a, c) = \sum _{t \in F(a) \cap F(c)} \alpha _t v_t(a) \]

  • \(F(a)\)\(F(c)\)分别表示广告文档\(a\)和上下文特征\(c\)上不为0的特征集合, 比如查询中的关键;
  • \(v_t(a)\) 表示这一特征在\(a\)广告中的贡献值; 常用的VSM(vector space model)模型不符合这一要求, 但是如果不考虑余弦距离中的归一化分母, 可以用这一线性函数在检索阶段做近似的预评估;
  • \(\alpha _t\) 为关键词\(t\)在上下文中的TF-IDF。 \(\alpha _t\)在不同查询中的取值不同, 但在同一次查询中是一组常数;

WAND

将线性函数评价过程加速的关键在于使用两个上界:

  1. 一是某个关键词\(t\)在所有文档上贡献值的上界, 即为\(u_t\)
  2. 二是某个文档中所有关键词上界的和, 这实际上是该文档对当前查询评价函数的上界, 记为\(U_a\);

巧妙的利用这两个上界可以在检索过程中排除大量不可能胜出的候选, 从而达到快速评价的目的。这一方法即为Andrei Broder等人提出的WAND(Weak AND)算法, 也是上下文定向广告和内容推荐产品中非常实用的快速检索算法。

WAND算法的检索过程如图所示, 图中每个关键词(Term)带有一条倒排链, 链表中的每一项是包含次关键词的文档ID, 用阴影表示。 WAND算法用到一个小顶堆的排序结构: 该堆维护着到目前为止的排序结果, 当新的候选产生时, 如果尚未装满或者相关度大于对顶文档的相关度, 则采用堆排序的方法将其插入堆, 否则就可以直接抛弃此候选。 检索过程迭代地执行以下两个步骤。

  1. 将各关键词对应的倒排链表按其最小的文档ID升序排列;
  2. 按前面的升序依次访问各关键词\(t\), 并累加器对应的\(u_t\)\(U\), 直至\(U\)大于堆顶。 设此时到达第\(n-1\)个关键词(图中\(n=3\)), 如果此时第0个关键词倒排链和第\(n-1\)个关键词倒排链的最小文档ID一致, 则计算文档准确的相关性, 如果仍然大于对队顶, 则该文档推入堆; 如果最小文档ID不一致, 说明该候选无胜出的可能, 于是在前n个关键词倒排中挑选一个, 将该链表头跳到第\(n-1\)个关键词到倒排链的最小文档ID, 然后流程跳转至第1步。

参考引用