Boolean query processing is at the heart of most commercially available retrieval systems, and with extensions, can be important for future systems. In the laboratory we experiment with programs that implement the most important low-level operations.
The underlying structures are inverted files and postings files. These can be more effectively built if disk sorting is avoided, which is feasible with large primary memories. Two such approaches are discussed in Chapter 3.
The postings themselves yield sets of document identifiers, on which operations like union and intersection can take place. If bit vectors or hash tables are used to represent these sets, then the required operations can be easily carried out, as can be seen in Chapter 12.
Focusing on effectiveness, on the other hand, we see that Boolean queries should be interpreted in a soft scheme. Tradeoffs in time complexity of those computations, versus amount of improvement likely in a retrieval, must be considered.