Method and apparatus for generating query responses in a computer-based document retrieval system

• US 20010000356A1
• Filed: 12/12/2000
• Published: 04/19/2001
• Est. Priority Date: 07/07/1995
• Status: Active Grant

• Current Assignee: Woods, William A.
• Original Assignee: Woods, William A.
• Inventors: Woods, William A.
• Granted Patent: US 6,594,658 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/30 of unstructured textual data document management systems G06F16/93
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

The present invention relates to a method and apparatus for generating responses to queries to a document retrieval system. The system responds to a specific request for information by locating and ranking portions of text that may contain the information sought. It locates small relevant passages of text (called “hit passages”) and ranks them according to an estimate of the degree to which they correspond to the information sought. The system minimizes the number of these hit passages that need to be examined before an information seeker has either found the desired information or can safely conclude that the information sought is not in the collection of texts. A relaxation ranking mechanism is provided to accommodate paraphrase variations that occur between the description of the information sought and the content of the text passages that may constitute suitable answers, by retrieving phrases that are dissimilar to the query phrase to different degrees according to a predefined set of rules, and penalizing the retrieved phrases based upon the degree of this dissimilarity, thus providing the user with a priority organized query hit list.

Claims

1. A method for locating information in documents in a database stored in a memory coupled to a processor, the method being carried out by program steps executed by said processor, including the steps of:

(1) receiving a search query including at least one query term;

(2) generating at least one hit passage from said documents, said hit passage including at least one hit term corresponding to said at least one query term;

(3) for at least a first hit term and a second hit term corresponding, respectively, to at least a first query term and a second query term, determining a first distance between said first and second hit terms and a second distance between said first and second query terms;

(4) generating a factor having a magnitude based upon a comparison of said first distance with said second distance; and

(5) generating a score for said hit passage incorporating the magnitude of said factor.

2. The method of

claim 1

, wherein:

step 2 includes the step of generating a plurality of said hit passages;

step 3 is carried out for at least two said hit terms in each of said plurality of hit passages;

step 4 is carried out for each of said distances determined in step 3 for each set of corresponding hit terms and query terms; and

step 5 is carried out for said plurality of hit passages.

3. The method of

claim 2

, further including the steps of:

after step 5, determining a best-scored said hit passage; and

retrieving at least said best-scored hit passage.

4. The method of

claim 2

, further including the steps of:

after step 5, determining a best-scored said hit passage; and

retrieving at least a document containing said best-scored hit passage.

5. The method of

claim 1

, wherein said score is generated at least in part based upon a factor proportional to said first distance.

6. The method of

claim 1

, wherein said hit passage has a size based upon a size of said search query.

7. The method of

claim 1

, wherein said score is additionally based upon a penalty generated from a measure of a semantic similarity between at least one query term and at least one hit term.

8. The method of

claim 1

, wherein said score is additionally based upon a penalty generated from a comparison of the total number of query terms with the total number of hit terms.

9. The method of

claim 3

, including the step of providing at least one hyperlink in said retrieved passage, said hyperlink linked to the document containing said passage.

10. A method for locating information in documents in a database stored in a memory coupled to a processor, the method being carried out by program steps executed by said processor, including the steps of:

(1) receiving a search query including at least a first query term and a second query term in a first order;

(2) generating at least one hit passage from said documents, said hit passage including at least a first hit term corresponding to said first query term and a second hit term corresponding to said second query term, said first and second hit terms being in a second order;

(3) generating a factor having a magnitude based upon a comparison of said first order with said second order; and

(4) generating a score for said hit passage incorporating the magnitude of said factor.

11. The method of

claim 10

, further including the steps of:

after step 4, determining a best-scored said hit passage; and

retrieving at least said best-scored hit passage.

12. The method of

claim 10

, further including the steps of:

after step 4, determining a best-scored said hit passage; and

retrieving at least a document containing said best-scored hit passage.

13. The method of

claim 10

, wherein said score is additionally based upon a penalty generated from a measure of a semantic similarity between at least one query term and at least one hit term.

14. The method of

claim 10

, wherein said score is additionally based upon a penalty generated from a comparison of the total number of query terms with the total number of hit terms.

15. A method for locating information in documents in a database stored in a memory coupled to a processor of a computer system, the computer system further including a proximity buffer and an output buffer coupled to said processor, the method being carried out by program steps executed by said processor and including the steps of:

(1) receiving a search query including at least one query term;

(2) determining at least one target region of at least one said document in said database;

(3) setting a penalty threshold to a predefined maximum;

(4) determining query hits corresponding to said query terms within said target region and correlating with each said query hit a score reflecting how closely it corresponds to its corresponding query term;

(5) storing said query hits in said proximity buffer;

(6) designating a best-scoring query hit from said proximity buffer as a current query hit;

(7) if said output buffer is full, discarding a lowest-scored query hit;

(8) inserting said current query hit into said output buffer;

(9) if the output buffer is now full, setting said penalty threshold to the score of a lowest-scored query hit in the output buffer;

(10) if a predetermined criterion is met, then proceeding to step 13 and otherwise proceeding to step 11;

(11) if there are more entailing term hits to generate, then proceeding to step 12 and otherwise proceeding to step 13;

(12) repositioning the target region relative to said document, and proceeding to step 4; and

(13) returning the contents of the output buffer.

16. The method of

claim 15

, wherein the predetermined criterion of step 10 is whether the last lowest-scored query hit in the output buffer has zero penalty.

17. The method of

claim 15

, wherein the predetermined criterion of step 10 is whether all documents have been searched.

18. A computer system for locating information in documents in a database stored in a memory coupled to a processor of said computer system, including:

a query module configured to receive a search query including a plurality of query terms;

a retrieval module configured to retrieve passages from said documents, each said passage including at least one hit term corresponding to at least one said query term;

a scoring module configured to generate scores for said passages based upon an order of occurrence of said query terms compared with an order of occurrence of hit terms appearing in said passages and corresponding to said query terms.

19. A search system for retrieving and ranking passages of documents in a database, including:

a retrieval module configured to retrieve passages from said documents in response to a search query including at least one query term, each said passage including at least one hit term corresponding to at least one said query term; and

a scoring module configured to generate scores for said passages based upon an order of occurrence of said query terms compared with an order of occurrence of hit terms appearing in said passages and corresponding to said query terms.

20. A computer system for locating information in documents in a database stored in a memory coupled to a processor of said computer system, including:

a query module configured to receive a search query including a plurality of query terms;

a retrieval module configured to retrieve at least one passage from said documents, said passage including at least two said hit terms corresponding to at least two said query terms;

a scoring module configured to generate scores for said passages based upon a factor having a magnitude incorporating a distance between said at least two said hit terms.

21. A search system for retrieving and ranking passages of documents in a database, including:

a retrieval module configured to retrieve at least a first said passage from said documents in response to a search query including a plurality of query terms, said passage including at least two said hit terms corresponding to at least two said query terms; and

a scoring module configured to generate scores for said passages based upon a factor having a magnitude incorporating a distance between said at least two said hit terms.