Sort system for text retrieval

• US 6,505,198 B2
• Filed: 08/21/2001
• Issued: 01/07/2003
• Est. Priority Date: 07/25/1997
• Status: Expired due to Fees

• Current Assignee: Justsystems Evans Research Incorporated
• Original Assignee: Claritech Corporation
• Inventors: Horowitz, Michael L.
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/933,937
• Publication Number:
  US 20020059346A1
• Time in Patent Office: 504 Days
• Field of Search: 707/3, 707/1, 707/2, 707/5, 707/500, 707/104, 707/7
• US Class Current: 1/1
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• 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/99937 Sorting
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The present invention is a method for operating a computer system to retrieve information from a computer database. This method decomposes documents from the database into subdocuments and then inverts the database. Also, a query for retrieving documents from a database is decomposed into terms. The subdocuments from the inverted database and the terms from the query are then used to compute a score that indicates a quantitative relation between terms in the query and the subdocuments. The resulting list of the subdocuments and their scores is then reorganized into a heap form. The highest ranking subdocument is then selected by the computer and the text associated with this subdocument is displayed. The remainder of the subdocument score list is concurrently reheapified.

Claims

1. A method for retrieving documents from a database, comprising the steps of:

creating a plurality of subdocuments from a plurality of documents stored in a database;

scoring the subdocuments;

sorting the subdocument scores via a modified heap sort, wherein said modified heap sort identifies the highest ranking subdocument from a portion of said subdocuments prior to a complete sort of said subdocuments; and

upon completing said modified heap sort, displaying text from a document corresponding to said highest ranking subdocument.

2. The method of claim 1, wherein said portion of said subdocuments is equal to about half of said subdocuments.

3. The method of claim 1 further comprising displaying text from a plurality of documents wherein said display of said documents corresponds to a rank order of said subdocuments generated by said modified heap sort.

4. An apparatus for retrieving documents from a database, comprising:

a computer coupled to a disk storage unit and to a display unit, said disk storage unit stores a database in at least one file;

said computer retrieves data from said database file to create a plurality of subdocuments from a plurality of documents stored in a database file;

said computer scores said subdocuments;

said computer sorts the subdocument scores via a modified heap sort, wherein said modified heap sort identifies the highest ranking subdocument from a portion of said subdocuments prior to a complete sort of said subdocuments; and

upon completing said modified heap sort, said computer displays on said display unit text retrieved from a document corresponding to said highest ranking subdocument.

5. The apparatus of claim 4, wherein said portion of said subdocuments is equal to about half of said subdocuments.

6. The apparatus of claim 4 wherein said computer displays text from a plurality of documents and wherein said display of said documents corresponds to a rank order of said subdocuments generated by said modified heap sort.

7. A computer readable media bearing sequences of computer executable instructions for retrieving documents from a database, comprising the computer-implemented steps of:

creating a plurality of subdocuments from a plurality of documents stored in a database;

scoring the subdocuments;

sorting the subdocument scores via a modified heap sort, wherein said modified heap sort identifies the highest ranking subdocument from a portion of said subdocuments prior to a complete sort of said subdocuments; and

upon completing said modified heap sort, displaying text from a document corresponding to said highest ranking subdocument.

8. The computer readable media bearing sequences of computer executable instructions of claim 7, wherein said portion of said subdocuments is equal to about half of said subdocuments.

9. The computer readable media bearing sequences of computer executable instructions of claim 7 comprising the computer-implemented step of displaying text from a plurality of documents wherein said display of said documents corresponds to a rank order of said subdocuments generated by said modified heap sort.