Ranking large document collections by a state space search

An algorithm is described for ordering by probability of relevance overlap- ping document subsets from which a searcher should choose the next document. The al- gorithm produces the ordering without assumptions of index term independence, improves its performance with increasing feedback, and estimates most accurately the probabilities of relevance of the subsets most likely to be relevant. The efficiency and ef- fectiveness of the algorithm are analyzed theoretically. A collection of documents described by index terms defines a search space of document subsets. For efficient and effective retrieval on a large document database, a searcher must make decisions about a vast number of such subsets. These decisions, concerning which subset to retrieve a document from next, implicitly involve probability estimations and com- binatorics. Unfortunately, people deal poorly with such situations. Kahneman, Slavic, and Tversky (1982) describe pervasive human fallacies in estimating probabilities, even among mathematically sophisticated individuals. Blair (1980) argues that unaided searchers can- not effectively construct queries that explore a large search space of overlapping document subsets. This paper presents a theoretical rationale for employing a novel form of information retrieval algorithm. The algorithm helps searchers better navigate through large document collections by continually revising probability estimates for document subsets. The algo- rithm avoids assumptions of index term independence and predicts relevance more accu- rately with increasing feedback. A mathematical analysis of the algorithm shows it can efficiently provide information about the probability of relevance of many different sub- sets of documents. Consider a set of documents relevant to an inquirer's need for information. Suppose the collection containing this set is very large (millions of documents or more), and the rel- evant set itself contains thousands of documents. Further, suppose the inquirer requires many of these documents to do his or her job effectively. (Legal, scholarly, or business re- search are examples of situations in which these assumptions apply.) Of course, the entire collection is far too large for the inquirer to search, and he or she needs the collection ar- ranged in an order that reduces the effort required to find the number of relevant docu- ments needed. Finally, suppose that the inquirer can identify perhaps a dozen or fifteen "good" search terms* but is unable to specify in what combinations they will be best used to retrieve rel- evant documents. Call this number of terms m. 2" - 1 disjoint, non-empty subsets of these good search terms can thus be defined. A particular subset of terms can be used to specify for retrieval just those documents that are indexed by all these terms but by none of the other m terms. For instance, with m = *Following the model for probabilistic retrieval (van Rijsbergen, 1979), a "good" search term might be one for which pi > qi, that is, one for which the probability of the term being used in a relevant document exceeds its being used in a nonrelevant document. Such terms contribute positively, for documents which employ them, to a discriminant function whose value increases as its prediction of the relevance of a document increases.