Rtb發展到現在，流量對廣告系統的速度要求越來越高。如何在使用者無感覺的時間内快速從大量的廣告中選出一條呈現在使用者面前，是一個非常有研究價值的問題。本文會形象生動地介紹廣告檢索技術，了解系統如何從大量的廣告庫裡拉出那些符合使用者流量特征的廣告。
檢索其實分為2步：1，為廣告庫裡所有廣告建立反向索引，2，在索引中查找符合使用者畫像的所有廣告。
- 為廣告庫裡所有廣告建立反向索引
輸入：所有廣告
輸出：所有廣告的反向索引
- 在索引中查找符合使用者畫像的所有廣告
輸入：所有廣告的反向索引，使用者畫像
輸出：符合使用者畫像的所有廣告
假設現在有2個廣告，他們分别有自己的定向條件。
a1=年齡在（20,30）或（40,50）且性别男且在廣東=(age∈(20,30) ∪age∈(40,50))∩(gender∈{男})∩(geo∈{廣東})
a2=年齡在（25,45）且在廣州=(age∈(25,45))∩(geo∈{廣州})
現在有一個使用者來請求廣告，他的使用者畫像為：ios、男、廣州、28歲。請問哪些廣告是與他比對的？
接下來我們就來看看這個過程是怎麼進行的。
正式開始之前，介紹點背景知識。
定義（析取範式）析取範式（DNF）是合取（連詞∧）子句的析取（連詞∨）。也就是說，析取範式是多個多個交集的并。
定理（範式存在定理）任何一個命題共識都存在着與之等值的析取範式與合取範式。
方案1：
第1步，建立反向索引。
根據範式存在定理，任何一個用布爾表達式的廣告，都可以表示成析取範式的形式。那麼前面提到的a1/a2可以變形為：
a1=( (age∈(20,30))∩(gender∈{男})∩(geo∈{廣東}) ) ∪ ( (age∈(40,50) )∩(gender∈{男})∩(geo∈{廣東}) )
a2=(age∈(25,45))∩(geo∈{廣州})
引入j1/j2/j3，用來代表析取範式中的各個交集：
j1=(age∈(20,30))∩(gender∈{男})∩(geo∈{廣東}), j2=(age∈(40,50) )∩(gender∈{男})∩(geo∈{廣東}) , j3=(age∈(25,45))∩(geo∈{廣州})
那麼，前面提到的2則廣告可以表示為：
a1=j1∪j2, a2=j3
這裡進行倒排，
第2步，在索引中查找廣告。
請求廣告的使用者畫像為：ios、男、廣州、28歲。直接去反向索引中比對，j1符合要求，那麼a1廣告可以出，j2不符合要求，j3符合要求，那麼a2廣告可以出。綜合起來看，a1/a2均符合該使用者，後續可以再對這兩個廣告進行排序，決定最終出哪一則廣告，後續的過程就不是檢索系統的範圍了，這裡不贅述。
這個方案并不是最優的，麻煩的地方在于j1~j3很少重複，這樣廣告需要比對很多很多個j式，并不是特别節省時間，下面介紹另外一種優化算法，采用的兩層反向索引。
優化方案2：
建立兩層的反向索引，考慮把(age∈(20,30))∩(gender∈{男})∩(geo∈{廣東})拆得更細。
引入size這個量，用來表示某個j需要同時滿足多少個條件，即定向條件是多少個子條件的交集。j1，需要同時滿足3個定向條件，則size=3；同理，j2，size=3；j3，需要同時滿足2個定向條件，size=2。按照size組織一層索引。
對size=2中的内容，命中2次（含義是同時滿足兩個條件）則算成功（兩個條件取值均為true，那麼他們交集仍然為true），對size=3中的内容，命中3次則算成功。如下圖所示。
請求廣告的使用者畫像為：ios、男、廣州、28歲。現在上層索引中比對。
- size=2。25~45歲，j3命中+1；廣州，j3命中+1。即命中2條，已達到size要求，那麼j3條件得到滿足。再查下層索引，j3滿足意味着可以出a2廣告。
- size=3。20~30歲，j1命中+1；男，j1命中+1，j2命中+1；廣東，j1命中+1，j2命中+1。j1命中了3次，達到size要求，那麼j1條件得到滿足。再查下層索引，j1滿足意味着可以出a1廣告。
綜上所述，該使用者比對到的廣告有a1、a2.