起點(diǎn)課堂會員權(quán)益
職業(yè)體系課特權(quán)
線下行業(yè)大會特權(quán)
個(gè)人IP打造特權(quán)
30+門專項(xiàng)技能課
1300+專題課程
12場職場軟技能直播
12場求職輔導(dǎo)直播
12場專業(yè)技能直播
會員專屬社群
榮耀標(biāo)識一個(gè)產(chǎn)品小白如何理解布爾表達(dá)式檢索？
布爾表達(dá)式檢索是廣告受眾定向的檢索問題，本文從基礎(chǔ)概念和方法出發(fā)，結(jié)合實(shí)際案例，深入淺出地闡述了布爾表達(dá)式檢索的作用以及用法。
廣告主投放廣告的本質(zhì)是流量的采買，所以廣告主在投放時(shí)會選擇自身角度的潛在用戶群，也就是當(dāng)代廣告的受眾定向售賣方式?，F(xiàn)在的廣告系統(tǒng)對于大數(shù)據(jù)量處理及實(shí)時(shí)性都有著極高的要求，當(dāng)用戶發(fā)起廣告請求時(shí)，廣告引擎如何快速篩選出符合定向條件的廣告，讓索引設(shè)計(jì)變得極為關(guān)鍵。
基礎(chǔ)概念
一般的廣告主定向條件都類似于：20歲+女性，25歲+北京
這里的定向條件用布爾表達(dá)式進(jìn)行表示：
a1=｛age∈（20）∩gender∈（female）｝∪｛age∈（25）∩geo∈（一線）｝
這里的形式即為析取范式（Disjunctive Normal Form，DNF）
每個(gè)DNF都可以分解成一個(gè)或者多個(gè)交集（conjunction），即age∈（25）∩geo∈（一線）
每個(gè)交集進(jìn)一步分解成一個(gè)或者多個(gè)賦值集（assignment），即age∈（25），geo∈（一線）
雙層索引結(jié)構(gòu)設(shè)計(jì)
算法會維護(hù)一個(gè)兩層的倒排索引，即conjunction-ad，attribute-conjunction。
實(shí)際檢索過程中：
通過assignment篩選出滿足條件的 conjunction，再根據(jù)conjunction找出滿足條件的廣告集合。
下面就是一步一步的舉例過程！
假設(shè)線上有7個(gè)廣告，定向條件如下：
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）
對應(yīng)有6種定向條件，將定向條件編輯如下（其中size表示其中含有幾個(gè)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
根據(jù)conjunction 的size大小及包含情況建立從attribute到conjunction的第二層倒排索引（標(biāo)注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，∈）
線上請求檢索過程
當(dāng)某次廣告請求的定向條件滿足某個(gè)conjunction，一定滿足包含該conjunction的所有廣告。如果用size of（query）表示請求中的定向標(biāo)簽個(gè)數(shù)，如果size of（query）＜size of（conjunction），該conjunction一定不滿足要求。可以先利用這個(gè)判斷減少計(jì)算。
當(dāng)線上有一個(gè)用戶發(fā)起了廣告請求，該用戶的標(biāo)簽為：
age∈（20）∩geo∈（一線）
因?yàn)閟ize of（query）=2，則從size為1和2的conjunction中進(jìn)行查詢
Size=2的查詢
age∈（20）???（2，∈）（3，∈）
geo∈（一線） ?（3，∈）
只有Conjunction3滿足條件，對應(yīng)Ad3
Size=1的查詢
age∈（20）???（1，∈）
只有Conjunction1滿足條件，對應(yīng)Ad1
維度爆炸問題
這里的維度組合并不取決于標(biāo)簽的乘積，即2個(gè)性別，100個(gè)年齡，34個(gè)地理……（2*100*34……），而是取決于廣告的規(guī)模，假設(shè)有100w的廣告，每個(gè)廣告的定向標(biāo)簽都不一樣，也只是百萬級的檢索，并且大量的廣告受眾定向是重復(fù)的，遠(yuǎn)遠(yuǎn)小于廣告數(shù)量。
本文由 @崔巍Bella 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載
題圖來自Unsplash，基于CC0協(xié)議
- 目前還沒評論，等你發(fā)揮！
