Hybrid search

• US 5,809,496 A
• Filed: 02/20/1997
• Issued: 09/15/1998
• Est. Priority Date: 02/20/1997
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Byrd, Roy Jefferson Jr., Goeser, Sebastian
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/802,510
• Time in Patent Office: 572 Days
• Field of Search: 707/3, 707/5, 707/531
• US Class Current: 707/706
• CPC Class Codes: G06F 16/319 Inverted lists
• 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

Abstract

A method is described for a computerized search for words in an electronic database with a large number of documents stored in memory. With this method, a Boolean retrieval method is used to determine in which of a large number of documents an initial word meets a Boolean condition. A probabilistic retrieval method is then used to determine in which of the documents fulfilling the Boolean condition, the relevance of appearance of a second word exceeds a specified value. The two retrieval methods use different indexes for this. The disadvantages normally found with this are avoided by the two different indexes having a common element that can be processed by both retrieval methods.

Claims

1. A method for searching an electronic database in which a number of documents are stored, said method comprising the steps of:

conducting a Boolean retrieval search of an initial word using a first index of said electronic database to determine in which of said number of documents said initial word meets a Boolean condition;

conducting a probabilistic retrieval search of a second word using a second index of said electronic database to determine in which of said documents meeting said Boolean condition, the relevance of appearance of said second word exceeds a specified value; and

wherein said first and second indexes have a common element that can be processed by both said Boolean and said probabilistic retrieval searches.

2. The method of claim 1, wherein:

said step of conducting a Boolean retrieval search additionally comprises the step of creating a bit sequence in which each bit represents one of said number of documents and the value of said each bit specifies whether said Boolean condition is met or not; and

said step of conducting said probabilistic retrieval search comprises computing said relevance of appearance of said second word only for those documents specified by said bit sequence as meeting said Boolean condition.

3. The method of claim 2, wherein:

said step of conducting a Boolean retrieval search comprises using a two-stage said first index, which index specifies for a selected word, which of said number of documents contain said word or not.

4. The method of claim 1, wherein:

said step of conducting a Boolean retrieval search comprises using a two-stage said first index, which index specifies for a selected word, which of said number of documents contain said word or not.

5. The method of claim 4, wherein:

said step of conducting a probabilistic retrieval search comprises using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

6. The method of claim 1, wherein:

said step of conducting a probabilistic retrieval search comprises using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

7. The method of claim 2, wherein:

said step of conducting a probabilistic retrieval search comprises using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

8. The method of claim 3, wherein:

said step of conducting a probabilistic retrieval search comprises using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

9. The method of claim 8, wherein:

said created bit sequence is derived from said two-stage index and is applied to said three-stage index.

10. The method of claim 9, wherein:

said step of conducting a probabilistic retrieval search comprises linking said created bit sequence with said documents of said three-stage index by means of an AND operation.

11. A computer system for searching an electronic database in memory in which a number of documents are stored, comprising:

first and second indexes of said electronic database, said indexes having a common element;

a Boolean retrieval searcher for conducting a Boolean retrieval search of an initial word using said first index to determine in which of said number of documents said initial word meets a Boolean condition; and

a probabilistic retrieval searcher for conducting a probabilistic retrieval search of a second word using said second index and said common element thereof to determine in which of said documents meeting said Boolean condition, the relevance of said second word exceeds a specified value.

12. The computer system of claim 11, wherein:

said Boolean retrieval searcher additionally provides a bit sequence in which each bit represents one of said number of documents and the value of said each bit specifies whether said Boolean condition is met or not; and

said probabilistic retrieval searcher computes said relevance of appearance of said second word only for those documents specified by said bit sequence as meeting said Boolean condition.

13. The computer system of claim 12, wherein:

said first index comprises a two-stage index which specifies for a selected word, which of said number of documents contain said word or not.

14. The computer system of claim 11, wherein:

said first index comprises a two-stage index which specifies for a selected word, which of said number of documents contain said word or not.

15. The computer system of claim 14, wherein:

said second index comprises a three-stage index which specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

16. The computer system of claim 11, wherein:

said second index comprises a three-stage index which specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

17. The computer system of claim 13, wherein:

said second index comprises a three-stage index which specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word;

said Boolean retrieval searcher provides said bit sequence from said two-stage index; and

said probabilistic retrieval searcher computes said relevance using said bit sequence and said three-part index.

18. The computer system of claim 17, wherein:

said probabilistic retrieval searcher additionally comprises an AND computation arrangement for linking said provided bit sequence with said three-stage index.

19. An article of manufacture for use in a computer system for searching an electronic database in which a number of documents are stored, said article of manufacture comprising a computer-readable storage medium having a computer program embodied in said medium which may cause the computer system to:

conduct a Boolean retrieval search of an initial word using a first index of said electronic database to determine in which of said number of documents said initial word meets a Boolean condition;

conduct a probabilistic retrieval search of a second word using a second index of said electronic database to determine in which of said documents meeting said Boolean condition, the relevance of appearance of said second word exceeds a specified value; and

wherein said first and second indexes have a common element that can be processed by both said Boolean and said probabilistic retrieval searches.

20. The article of manufacture of claim 19, wherein said computer program embodied in said medium additionally may cause the computer system to:

conduct said Boolean retrieval search by additionally creating a bit sequence in which each bit represents one of said number of documents and the value of said each bit specifies whether said Boolean condition is met or not; and

conduct said probabilistic retrieval search by computing said relevance of appearance of said second word only for those documents specified by said bit sequence as meeting said Boolean condition.

21. The article of manufacture of claim 20, wherein said computer program embodied in said medium additionally may cause the computer system to:

conduct said Boolean retrieval search using a two-stage said first index, which index specifies for a selected word, which of said number of documents contain said word or not.

22. The article of manufacture of claim 19, wherein said computer program embodied in said medium additionally may cause the computer system to:

conduct said Boolean retrieval search using a two-stage said first index, which index specifies for a selected word, which of said number of documents contain said word or not.

23. The article of manufacture of claim 22, wherein said computer program embodied in said medium additionally may cause the computer system to:

conducting said probabilistic retrieval search using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

24. The article of manufacture of claim 19, wherein said computer program embodied in said medium additionally may cause the computer system to:

conduct said probabilistic retrieval search using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

25. The article of manufacture of claim 20, wherein said computer program embodied in said medium additionally may cause the computer system to:

conducting said probabilistic retrieval search using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

26. The article of manufacture of claim 21, wherein said computer program embodied in said medium additionally may cause the computer system to:

conduct said probabilistic retrieval search using a three-stage said second index, which index specifies for a selected word, which of said number of documents contain said word, and at which location said word is found in each said documents containing said word.

27. The article of manufacture of claim 26, wherein:

said created bit sequence is derived from said two-stage index and is applied to said three-stage index.

28. A computer program product for operating a computer system for searching an electronic database in which a number of documents are stored, said computer program product comprising a storage medium having computer-readable program code embodied in said medium for causing the computer system to:

conduct a Boolean retrieval search of an initial word using a first index of said electronic database to determine in which of said number of documents said initial word meets a Boolean condition;

conduct a probabilistic retrieval search of a second word using a second index of said electronic database to determine in which of said documents meeting said Boolean condition, the relevance of appearance of said second word exceeds a specified value; and

wherein said first and second indexes have a common element that can be processed by both said Boolean and said probabilistic retrieval searches.

29. The computer program product of claim 28, wherein said computer-readable program code additionally causes the computer system to:

conduct said Boolean retrieval search by additionally creating a bit sequence in which each bit represents one of said number of documents and the value of said each bit specifies whether said Boolean condition is met or not; and

conduct said probabilistic retrieval search by computing said relevance of appearance of said second word only for those documents specified by said bit sequence as meeting said Boolean condition.