Method of indexing keywords for searching in a database recorded on an information recording medium

• US 5,375,235 A
• Filed: 11/05/1991
• Issued: 12/20/1994
• Est. Priority Date: 11/05/1991
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Northern Telecom Limited (Nortel Networks Corporation)
• Inventors: Ross, Evan B., Daisley-Harrison, Aaron G., Berry, Victor A., Hanssens, Arsene
• Primary Examiner(s): Kriess, Kevin A.
• Application Number:
  US07/788,081
• Time in Patent Office: 1,141 Days
• Field of Search: 395/600, 395/650, 395/700
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9017 using directory or table look-up use of a directory or look-up table in file systems G06F16/13
• CPC Class Codes: G11B 2220/213 Read-only discs
• CPC Class Codes: G11B 2220/2545 CDs
• CPC Class Codes: G11B 27/105 of operating discs
• CPC Class Codes: G11B 27/329 on a disc [VTOC]
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

A method of storing and searching data on a mass storage medium is provided. A dictionary of keywords in a data file is compiled and a unique ID number is assigned to each keyword. A plurality of the most frequently occurring keywords are assigned ID numbers opposite in sense to the frequency of occurrence of the keyword. The dictionary of keywords is classified into a plurality of classes, the class of keywords least frequently occurring within the database having the fewest levels of indexing and the most amount of information regarding the exact location of a keyword within the data file.

Claims

1. A method of indexing a plurality of keywords for searching in a database recorded on an information recording medium, the method comprising the steps of:

providing a plurality of information pages in the database for searching by the keywords and for display or printing in readable form;

providing a dictionary of the keywords to be used in searching the information pages, each of the keywords having associated therewith a unique ID number, a keyword type dependent upon a frequency of occurrence of the keyword within the database and an occurrence pointer;

providing an occurrence table for mapping the keywords of at least one keyword type to corresponding occurrence data; and

providing a plurality of pagemaps, one for each corresponding information page in the database, for mapping keyword ID numbers to physical locations on the corresponding information page;

whereby the location of a particular keyword within the information pages is determined by one of the occurrence pointers, the occurrence table and pagemaps.

2. A method as claimed in claim 1, wherein the dictionary includes first and second levels, the first level having truncated keywords each having a corresponding block indicator, the second level having for each block indicator a group of keywords corresponding thereto.

3. A method as claimed in claim 2, wherein the groups of keywords are ranked in alphabetical order.

4. A method as claimed in claim 1, wherein a first keyword type corresponds to a first set of the keywords whose frequency of occurrence is lowest, the occurrence pointer for each of the keywords the first keyword type comprising a pagemap location including a pagemap number and a word number.

5. A method as claimed in claim 4, wherein a second keyword type corresponds to a second set of the keywords whose frequency of occurrence is second lowest, the occurrence pointer for the keywords of the second keyword type comprising a row in the occurrence table.

6. A method as claimed in claim 5, wherein a third keyword type corresponds to a third set of the keywords whose frequency of occurrence is highest, the occurrence pointer for each of the keywords of the third keyword type comprising no occurrence information, whereby the plurality of pagemaps are searched sequentially to locate a particular keyword of the third keyword type.

7. A method of indexing a plurality of keywords for searching in a database containing a plurality of information pages, a keyword dictionary, on occurrence table and a plurality of pagemaps corresponding to the plurality of information pages, the method comprising the steps of:

storing the keywords in the dictionary;

associating, in the dictionary, each of the keywords with a unique ID number, a keyword type dependent upon a frequency of occurrence of the keyword in the database and an occurrence pointer;

mapping, in the occurrence table, the keywords of at least one keyword type to corresponding occurrence data; and

mapping, in the pagemaps, keyword ID numbers to corresponding physical locations in the information pages;

whereby the location in the database of a particular keyword is determined by one of an occurrence pointer associated with the particular keyword, an entry related to the particular keyword in the occurrence table and an entry related to the particular keyword in the pagemaps.

8. A method as claimed in claim 7, wherein the dictionary includes, for at least a subset of the keywords, first and second levels, the first level containing truncated keywords each corresponding to a block indicator and the second level containing a group of keywords corresponding to each block indicator.

9. A method as claimed in claim 8, wherein the groups of keywords are ranked in alphabetical order.

10. A method as claimed in claim 7, wherein a first keyword type corresponds to a first set of the keywords having a lowest frequency of occurrence, the occurrence pointer for each of the keywords of the first keyword type comprising a pagemap location including pagemap number and a word number.

11. A method as claimed in claim 10, wherein a second keyword type corresponds to a second set of the keywords having a second lowest frequency of occurrence, the occurrence pointer for each of the keywords of the second keyword type comprising a row in the occurrence table.

12. A method as claimed in claim 11, wherein a third keyword type corresponds to a third set of the keywords having a highest frequency of occurrence, the occurrence pointer for each of the keywords of the third keyword type comprising no occurrence information, whereby the plurality of pagemaps are searched sequentially to locate a particular keyword of the third keyword type.

13. A method as claimed in claim 11, wherein a keyword search for a string of keywords comprises a first search for keywords of the first keyword type, upon failure to locate the string of keywords in the first search, the keyword search proceeds to a second search, the second search being for keywords of the second keyword type, and upon failure to locate the string of keywords in the second search, the keyword search includes a third search to search for keywords of the third keyword type.