Method for performing a search of a plurality of documents for similarity to a plurality of query words

• US 5,544,049 A
• Filed: 05/22/1995
• Issued: 08/06/1996
• Est. Priority Date: 09/29/1992
• Status: Expired due to Term

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Henderson, Richard D., Barbarino, Michael J.
• Primary Examiner(s): McElheny, Jr., Donald E.
• Assistant Examiner(s): Poinvil, Frantzy
• Application Number:
  US08/447,317
• Time in Patent Office: 442 Days
• Field of Search: 364/419.19, 364/419.13, 364/200.75, 364/900.75, 364/419.07, 395/600
• US Class Current: 704/7
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method for performing a search of a plurality of documents for similarity to a query word includes retrieving a first document, and determining a number of occurrences of the at least one query word in the first document. Then, a next document is retrieved and a number of occurrences of the at least one query word in the next document is determined. The steps are repeated until each of the plurality of documents have been retrieved, and the number of occurrences of the at least one query word has been determined in each of the plurality of documents. The query word can include a plurality of query words, all of which are searched in each document, in turn, rather than being searched word by word in the whole collection of documents. The documents are then ranked according to the number of occurrences of the query words determined in each document, and a list of documents is produced according to the document ranking.

Claims

1. A computer implemented method for performing a search of a plurality of documents for similarity to a query having multiple terms using an inverted index of the plurality of documents, the method comprising the sequential steps of:

(a) searching the inverted index for each of the query terms and determining a number of occurrences of the query terms in a first document;

(b) calculating a similarity score for the first document based on the number of occurrences of the query terms in the first document;

(c) searching the inverted index for each of the query terms and determining a number of occurrences of the query terms in a subsequent document;

(d) calculating a similarity score for the subsequent document based on the number of occurrences of the query terms in the subsequent document; and

(e) repeating steps (c) and (d) until a similarity score has been calculated for each of the plurality of documents.

2. The method of claim 1, further comprising the step of ranking the plurality of documents based on the calculated similarity scores.

3. The method of claim 1, further comprising the step of producing a list of the plurality documents that is ordered based on the calculated similarity scores.

4. The method of claim 1, wherein the query terms comprise images, and wherein the inverted index is an inverted index of images that occur in the plurality of documents.

5. The method of claim 1, further comprising the step of storing a predetermined number of the highest similarity scores in a memory as the searching and calculating steps are performed.

6. The method of claim 1, wherein a similarity score for each document is calculated before a search is performed for occurrences of the query terms in a subsequent document.

7. The method of claim 1, wherein, the steps of calculating a similarity score comprise calculating a similarity score based on a user defined formula and a number of occurrences of the query terms in a document.

8. A computer implemented method for performing a search of a plurality of documents for similarity to a query having multiple terms using an inverted index of the plurality of documents, comprising the sequential steps of:

(a) searching the inverted index for each of the query terms and determining a number of occurrences of the query terms in a first document;

(b) calculating a similarity score for the first document based on the number of occurrences of the query terms in the first document;

(c) storing the first document'"'"'s similarity score in a memory;

(d) searching the inverted index for each of the query terms and determining a number of occurrences of the query terms in a subsequent document;

(e) calculating a similarity score for the subsequent document based on the number of occurrences of the query terms in the subsequent document;

(f) storing the subsequent document'"'"'s similarity score in the memory when fewer than a predetermined number of similarity scores are stored in the memory;

(g) comparing the subsequent document'"'"'s similarity score to the similarity scores stored in the memory, deleting the lowest similarity score stored in the memory, and storing the subsequent document'"'"'s similarity score in the memory when the subsequent document'"'"'s similarity score is higher than the lowest similarity score stored in the memory and more than a predetermined number of similarity scores are stored in the memory; and

(h) repeating steps (d) through (g) until a similarity score has been calculated for each of the plurality of documents.

9. The method of claim 8, further comprising the step of ranking the documents whose similarity scores are stored in the memory based on the calculated similarity scores.

10. The method of claim 8, further comprising the step of producing a list of the documents whose similarity scores are stored in the memory, the list being ordered based on the calculated similarity scores.

11. The method of claim 8, wherein the query terms comprise images, and wherein the inverted index is an inverted index of images that occur in the plurality of documents.

12. The method of claim 8, wherein a similarity score for each document is calculated before a search is performed for occurrences of the query terms in a subsequent document.

13. The method of claim 8, wherein the steps of calculating a similarity score comprise calculating a similarity score based on a user defined formula and a number of occurrences of the query terms in a document.

14. A computer implemented method for performing a search of a corpus of documents for similarity to a query having multiple terms using an inverted index of the corpus of documents, the method comprising the sequential steps of:

(a) retrieving a first portion of the inverted index corresponding to a first plurality of documents from a first memory into a second memory;

(b) searching the first portion of the inverted index for each of the query terms and determining a number of occurrences of the query terms in each of the documents in the first portion of the inverted index;

(c) calculating similarity scores for each of the documents in the first portion of the inverted index based on the number of occurrences of the query terms in the documents;

(d) retrieving a subsequent portion of the inverted index corresponding to a subsequent plurality of documents from the first memory into the second memory;

(e) searching the subsequent portion of the inverted index for each of the query terms and determining a number of occurrences of the query terms in each of the documents in the subsequent portion of the inverted index;

(f) calculating similarity scores for each of the documents in the subsequent portion of the inverted index based on the number of occurrences of the query terms in the documents; and

(g) repeating steps (d) through (f) until a similarity score has been calculated for each of the documents in the corpus of documents.

15. The method of claim 14, further comprising the step of ranking the plurality of documents based on the calculated similarity scores.

16. The method of claim 14, further comprising the step of producing a list of the plurality documents that is ordered based on the calculated similarity scores.

17. The method of claim 14, wherein the query terms comprise images, and wherein the inverted index comprises an inverted index of images that occur in the plurality of documents.

18. The method of claim 14, further comprising the step of storing a predetermined number of the highest similarity scores in the second memory as the searching and calculating steps are performed.

19. The method of claim 14, wherein similarity scores for documents in each portion of the inverted index are calculated before a search is performed for occurrences of the query terms in documents in a subsequent portion of the inverted index.

20. The method of claim 14, wherein, the steps of calculating a similarity score comprise calculating a similarity score based on a user defined formula and a number of occurrences of the query terms in a document.