Patent US5765168A successfully refreshed from Google Patents.
US5765168A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for maintaining an index
Assignee: AltaVista Co
•
Filing: 1996-08-09
•
Granted: 1998-06-09
•
Expires: 2016-08-09
Abstract
Abstract A computer implemented method maintains an index of a database. The database stores information as a plurality of records. Batches of records are indexed by storing index entries in a memory. Each index entry includes a word entry for each unique portion of information of the database, and one or more location entries pointing at occurrences of the portions of information. The index entries are organized according to a collating order of the word entries. The location entries are stored sequentially for each word entry. The index entries are organized into a plurality of tiers of files. There is one tier of files for each batch of records indexed. A merged tier of files is periodically produced by merging a subsequently produced tier of files with a previously produced tier of files. The index entries of the merged tier of files are a logical union of the index entries of the subsequently and previous produced tiers of files. The location entries of deleted records are expunged while merging the tiers of files.
Inventors
- 👤 Michael Burrows
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:08
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/316; G06F16/319
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
154 words
A computer implemented method for maintaining an index of a database, the database storing information as a plurality of records, comprising: indexing batches of the records by storing index entries in a memory, each index entry including a word entry for each unique portion of information of the database, and one or more location entries pointing at occurrences of the portions of information; collating the index entries according to the order of the word entries, and sequentially according to the locations of each word entry; organizing the index entries in a plurality of tiers of files, there at least initially being one tier of files for each batch of records indexed; and periodically merging a subsequently produced tier of files with a previously produced tier of files to produce a merged tier of files, the index entries being a logical union of the index entries of the subsequently and previous produced tiers of files.
Claim 2
Dependent Claim
154 words
A computer implemented method for maintaining an index of a database, the database storing information as a plurality of records, comprising: indexing batches of the records by storing index entries in a memory, each index entry including a word entry for each unique portion of information of the database, and one or more location entries pointing at occurrences of the portions of information; collating the index entries according to the order of the word entries, and sequentially according to the locations of each word entry; organizing the index entries in a plurality of tiers of files, there at least initially being one tier of files for each batch of records indexed; and periodically merging a subsequently produced tier of files with a previously produced tier of files to produce a merged tier of files, the index entries being a logical union of the index entries of the subsequently and previous produced tiers of files.
Claim 3
Dependent Claim
50 words
The method of claim 1 further comprising: writing a deleted location entry in an index entry having a word entry indicating a deleted status of a deleted record identified by the deleted location entry; deleting the location entries of the deleted record substantially simultaneous with merging the tiers of files.
Claim 4
Dependent Claim
103 words
A computer implemented method for maintaining an index of a database, the database storing information as a plurality of records, comprising the steps of: indexing batches of the records by storing index entries in a memory; organizing the index entries into a plurality of tiers, including a first tier and a second tier, wherein the first tier includes a first bucket and the second tier includes a second bucket, the first bucket and the second bucket each including at least one of the index entries; and merging the first tier with the second tier to merge the first bucket with the second bucket.
Claim 5
Dependent Claim
103 words
A computer implemented method for maintaining an index of a database, the database storing information as a plurality of records, comprising the steps of: indexing batches of the records by storing index entries in a memory; organizing the index entries into a plurality of tiers, including a first tier and a second tier, wherein the first tier includes a first bucket and the second tier includes a second bucket, the first bucket and the second bucket each including at least one of the index entries; and merging the first tier with the second tier to merge the first bucket with the second bucket.
Claim 6
Dependent Claim
18 words
The computer implemented method of claim 3, wherein the first bucket is an extension of the second bucket.
Claim 7
Dependent Claim
19 words
The computer implemented method of claim 4, wherein the first bucket is a logical extension of the second bucket.
Claim 8
Dependent Claim
26 words
The computer implemented method of claim 3, further comprising the step of: responsive to the merging, decreasing a number of tiers within the plurality of tiers.
Claim 9
Dependent Claim
53 words
The computer implemented method of claim 3, further comprising the steps of: attaching a delete flag to a particular index entry responsive to the deletion of one of the plurality of records; and responsive to the delete flag, expunging at least a portion of the particular index entry from the plurality of tiers.
Claim 10
Dependent Claim
89 words
A computer system for maintaining a database storing information as a plurality of records, the computer system comprising: a memory configured to store a first and a second section of data, the first section having a first storage area configured to store a first entry and the second section having a second storage area configured to store a second entry, wherein the second storage area is a logical extension of the first storage area; and a processor configured to merge the second storage area with the first storage area.
Claim 11
Dependent Claim
89 words
A computer system for maintaining a database storing information as a plurality of records, the computer system comprising: a memory configured to store a first and a second section of data, the first section having a first storage area configured to store a first entry and the second section having a second storage area configured to store a second entry, wherein the second storage area is a logical extension of the first storage area; and a processor configured to merge the second storage area with the first storage area.
Claim 12
Dependent Claim
37 words
The computer system of claim 8, wherein the processor is further configured to merge the second section with the first section such that the first entry and the second entry are merged to form a logical union.
Claim 13
Dependent Claim
40 words
The computer system of claim 8, wherein the processor is further configured to index one of the plurality of records by storing an index record in the memory, wherein the index record includes a word entry and a location entry.
Claim 14
Dependent Claim
21 words
The computer system of claim 10, wherein the index record is stored in one of the first and the second entries.
Claim 15
Dependent Claim
37 words
The computer system of claim 10, wherein the word entry is indicative of a portion of information stored in the database and the location entry is indicative of occurrences of the portion of information within the database.
Claim 16
Dependent Claim
31 words
The computer system of claim 8, wherein the processor is further configured to expunge at least a portion of the second entry from the second storage area responsive to the merger.
Claim 17
Dependent Claim
42 words
The computer system of claim 8, wherein the processor is further configured to attach a delete flag to one of the first and the second entries which corresponds, at least partially, to one of the plurality of records that has been deleted.
Claim 18
Dependent Claim
17 words
The computer system of claim 14, wherein the browser is further configured to identify the deleted record.
References Cited (Backward Citations)
US4977594A
Cited
US5148541A
Cited
US5276616A
Cited
US5293616A
Cited
US5551027A
Cited
US5550967A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-06-08 | 2001-12-08 | 2002-06-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-06-08 | 2005-12-08 | 2006-06-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-06-08 | 2009-12-08 | 2010-06-09 | $7700.00 | Window Closed / Lapsed |