Indexing Boolean expressions：索引的布尔表达式.ppt

Problem ? Online Display Advertising Example ? BE: age ∈ {10,20} & country ? {US} ? S: age=20 & country=FR & gender=F ? Given an assignment S, find all matching Boolean expressions (BEs) Possible Applications ? Display advertizing ? Publish/subscribe System ? Expert Systems ? Pattern matching in AI ? Compliance checker Contributions ? Use inverted indexing techniques for ‘ complex ’ BEs - DNF, CNF expressions of ∈, ? predicates with multiple values ? Support top-k pruning given relevance score Outline ? Inverted index construction ? Search algorithms – DNF – CNF ( ∈ only) ? Experimental results Inverted Index ? E1: A ∈ {1} ? E2: A ∈ {1} & B ∈ {2} & C ∈ {3,4} ? S: A=1 & B=2 Key Posting List (A,1) E1,E2 (B,2) E2 (C,3) E2 (C,4) E2 Inverted List Construction ID Expression K 1 age ∈ {3} ∧ state ∈{NY } 2 2 age ∈ {3} ∧ gender ∈{F} 2 3 age ∈ {3} ∧ gender ∈{M} ∧ state ? {CA} 2 4 state ∈ {CA} ∧ gender ∈{M} 2 5 age ∈ {3, 4} 1 6 state ? {CA,NY } 0 K Key and UB Posting List 0 (state,CA), (6, ?, 0) (state,NY ), 5 (6, ?, 0) Z, 0 (6, ∈, 0) 1 (age, 3), (5, ∈, ) (age, 4), (5, ∈, ) 2 (state,NY ), 5 (1, ∈, ) (age, 3), (1, ∈, ) (2, ∈, ) (3, ∈, ) (gender, F), 2 (2, ∈, ) (state,CA), (3, ?, 0) (4, ∈, ) (gender,M), (3, ∈, ) (4, ∈, ) Algorithm 1: 1: input: inverted list idx and assignment S 2: output: set of IDs O matching S 3: O ←? 4: for K=min(, |S| ). . .0 do 5: /* List of posting lists matching A for conjunction size K */ 6: PLists ← (S,K) 7: InitializeCurrentEntries(PLists) 8: /* Processing K =0 and K =1 are identical */ 9: if K=0 then K ←1 10: /* Too few posting lists for any conjunction to be satisfied */ 11: if () < K then 12: continue to next for loop iteration 13: while PLists[K-1].CurrEntry 6 = EOL do 14: SortByCurrentEntries(PLists) 15: /* Check if the first K posting lists have the same conjunction ID in