Implementing Boolean Search
Typical: OR of ANDS, handle each OR
For ANDs, inverted index:
- list (set) of documents containing each term
- intersect lists
- find smallest query-term list
- check each document in list for other terms
No faster algorithm known
- (unless use quadratic space, preprocessing)
Challenge: anything provably better