Indexing Boolean Expressions
Steven Whang (Stanford Univ.), Chad Brower (Yahoo! Research), Jayavel Shanmugasundaram (Yahoo! Research), Serguei Vassilvitskii (Yahoo! Research), Erik Vee (Yahoo! Research), Ramana Yerneni (Yahoo! Research), Hector Garcia-Molina (Stanford Univ.)
VLDB 2009 [slides]
Xianming LIU

The problem is simple but practical. I like this type of problems.

[Problem]
Input: Given a assignment, a large set of Boolean Expressions(BE)
Output: All satisified BEs  under the assignment.

[Application]
Online Advertisig:
A BE represents an advertiser’s user targeting requirements.
An assignment of value to attributes represents the characteristics of a user visiting an online page.
Publish/Subscribe System:
A BE represents a subscription.
An assignment of value to attributes represents an event.

[Solution]
Build a inverted index [Atomic Expression, BE position list] to index all expressions.
- Conjunction: Merge sorted list
- DNF: find the
- CNF:
What is the key difference between the IR joining algorithms