Boolean Similarity Measures for Resource Discovery

We develop a new method to rank the degree of similarity between Boolean expressions, contrast it with other known methods, and describe its implementation. Our method reduces time and space complexity from exponential to polynomial in the number of Boolean terms. Index Terms - Boolean query, information retrieval, ranking, resource discovery, similarity measure. 1 Introduction Most library information systems let users make Boolean queries against their database. Internet resource discovery systems, such as WAIS [1] and our Indie [2], also support Boolean queries. Frequently, users find it convenient if the retrieval system returns the answers to their queries in a ranked order. This paper develops an efficient algorithm to rank the similarity between a user's Boolean query and a set of objects, each described by a Boolean expression. Our method produces similarity rankings between zero and one. If the query and the object with which it is compared contain some identical terms, the ..