Efficient algorithms for ranking documents represented as DNF formulas
David E. Losada, Álvaro Barreiro · 2000
This paper describes efficient procedures to compute similarity within a logical framework. The theory that underlies our approach is based on the use of Belief Revision techniques to get a measure of the uncertainty of d ! q, where d and q are logical representations of a document and a query respectively. However, a direct implementation of those techniques would have to deal with logical interpretations and, as a consequence, its complexity would be exponential. We propose a syntactic characterization of the logical formulas involved that allows us to design polynomial-time algorithms for computing similarity. The algorithms are presented in increasing order of expressiveness. An important aspect is that efficient IR systems realizing the theory and managing representations more expressive than classical ones can be built. 1 Introduction One of the major problems when using logic as a representational tool is the complexity of the resulting system. Usually, the more express...