US5685003A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for automatically indexing data in a document using a fresh index table
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1994-10-26
•
Granted: 1997-11-04
•
Expires: 2014-10-26
Abstract
Abstract A system and method for indexing words in documents, the system including a master index for storing the words and for storing associated index data. One of the documents is selected for updating and is edited. Next, a shadow index is created. Each word from the selected edited document is then indexed in the shadow index. A fresh index table is updated to indicate that the shadow index contains the most up-to-date data regarding the selected edited document. Query requests will be processed by searching all relevant indexes and comparing the retrieved results with the data in the fresh index table. Only the most up-to-date data will actually be returned as the query results. Periodically, shadow indexes and the master index can be merged into a new master index. Only the most up-to-date data, as determined by a comparison with the fresh index table, will be stored in the new master index.
Inventors
- 👤 Kyle Gordon Peltonen
- 👤 Bartosz Milewski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 08:48
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/30; G06F16/31; G06F16/316; G06F16/328; G06F16/319; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 47
Claim 1
Independent Claim
158 words
In a data processing system having documents, a plurality of indexes, and a fresh index table, each document having an associated index containing out-of-date indexing information for the document and having an associated index containing up-to-date indexing information that supersedes the out-of-date indexing information for the document, the fresh index table having entries that indicate the index having the up-to-date indexing information for each document, a method comprising the steps of: receiving a request to determine which of the documents contains a keyword; accessing the indexes to retrieve aggregate indexing information that indicates the documents containing the keyword, the aggregate indexing information comprising both up-to-date indexing information and out-of-date indexing information; and for each of the documents containing the keyword, accessing the fresh index table with the aggregate indexing information to determine the index having the up-to-date indexing information for the document and to identify the up-to-date indexing information for the document from among the aggregate indexing information.
Claim 2
Dependent Claim
158 words
In a data processing system having documents, a plurality of indexes, and a fresh index table, each document having an associated index containing out-of-date indexing information for the document and having an associated index containing up-to-date indexing information that supersedes the out-of-date indexing information for the document, the fresh index table having entries that indicate the index having the up-to-date indexing information for each document, a method comprising the steps of: receiving a request to determine which of the documents contains a keyword; accessing the indexes to retrieve aggregate indexing information that indicates the documents containing the keyword, the aggregate indexing information comprising both up-to-date indexing information and out-of-date indexing information; and for each of the documents containing the keyword, accessing the fresh index table with the aggregate indexing information to determine the index having the up-to-date indexing information for the document and to identify the up-to-date indexing information for the document from among the aggregate indexing information.
Claim 3
Dependent Claim
25 words
The method of claim 1 wherein the step of receiving a request further includes the step of receiving the request in response to user input.
Claim 4
Independent Claim
30 words
The method of claims 1 wherein the aggregate indexing information contains the keyword, at least one document identifier for the keyword and at least one occurrence for each document identifier.
Claim 5
Dependent Claim
167 words
In a data processing system having documents, a plurality of indexes, and a fresh index table, each document having an index containing indexing information for the document, a plurality of the documents being revised documents having a plurality of indexes, each revised document having an index containing out-of-date indexing information and an index having up-to-date indexing information that supersedes the out-of-date indexing information, the fresh index table having an entry for each revised document indicating which of the indexes has the up-to-date indexing information for the revised document, a method for automatically indexing one of the revised documents comprising the steps of: receiving an indication that the revised document has been updated such that the up-to-date indexing information for the revised document is out of date; creating an index containing new up-to-date indexing information for the revised document; and updating the entry in the fresh index table for the revised document to reflect that the created index contains the new up-to-date indexing information for the revised document.
Claim 6
Dependent Claim
167 words
In a data processing system having documents, a plurality of indexes, and a fresh index table, each document having an index containing indexing information for the document, a plurality of the documents being revised documents having a plurality of indexes, each revised document having an index containing out-of-date indexing information and an index having up-to-date indexing information that supersedes the out-of-date indexing information, the fresh index table having an entry for each revised document indicating which of the indexes has the up-to-date indexing information for the revised document, a method for automatically indexing one of the revised documents comprising the steps of: receiving an indication that the revised document has been updated such that the up-to-date indexing information for the revised document is out of date; creating an index containing new up-to-date indexing information for the revised document; and updating the entry in the fresh index table for the revised document to reflect that the created index contains the new up-to-date indexing information for the revised document.
Claim 7
Dependent Claim
72 words
The method of claim 4 wherein the documents that are not revised documents are non-revised documents, and wherein the method further includes the steps of receiving an indication that one of the non-revised documents has been updated, generating an index containing up-to-date indexing information for the non-revised document, and adding an entry to the fresh index table to reflect that the generated index contains the up-to-date indexing information for the non-revised document.
Claim 8
Dependent Claim
165 words
In a data processing system having documents, a plurality of indexes, and a fresh index table, a first type of index being a master index having indexing information for all documents at system startup and a second type of index being a shadow index having indexing information for at least one document that is updated at system runtime, the fresh index table having entries that indicate a shadow index having a most recent indexing information for a document, a method for merging indexes comprising the steps of: accessing the shadow indexes and the master index to retrieve indexing information for all of the documents, wherein at least one document has less recent indexing information in the master index and most recent indexing information in one of the shadow indexes; accessing the fresh index table to determine most recent indexing information for all of the documents from the retrieved indexing information; and creating an index containing the most recent indexing information for all of the documents.
Claim 9
Dependent Claim
165 words
In a data processing system having documents, a plurality of indexes, and a fresh index table, a first type of index being a master index having indexing information for all documents at system startup and a second type of index being a shadow index having indexing information for at least one document that is updated at system runtime, the fresh index table having entries that indicate a shadow index having a most recent indexing information for a document, a method for merging indexes comprising the steps of: accessing the shadow indexes and the master index to retrieve indexing information for all of the documents, wherein at least one document has less recent indexing information in the master index and most recent indexing information in one of the shadow indexes; accessing the fresh index table to determine most recent indexing information for all of the documents from the retrieved indexing information; and creating an index containing the most recent indexing information for all of the documents.
Claim 10
Dependent Claim
32 words
The method of claim 6 wherein the step of creating an index includes the step of creating a second master index containing the most recent indexing information for all of the documents.
Claim 11
Dependent Claim
127 words
In a data processing system having documents, indexes, and a fresh index table, each index containing indexing information for at least one document, the fresh index table having entries, each entry indicating an index having a most recent indexing information for one of the documents, a method for automatically indexing one of the documents comprising the steps of: creating a first index for the document containing up-to-date indexing information comprising keywords, a document identifier, and an occurrence; determining when the document is updated such that the up-to-date indexing information is out of date; and creating a second index containing new up-to-date indexing information for the document and updating the fresh index table to reflect that the second index contains the new up-to-date indexing information for the document.
Claim 12
Dependent Claim
127 words
In a data processing system having documents, indexes, and a fresh index table, each index containing indexing information for at least one document, the fresh index table having entries, each entry indicating an index having a most recent indexing information for one of the documents, a method for automatically indexing one of the documents comprising the steps of: creating a first index for the document containing up-to-date indexing information comprising keywords, a document identifier, and an occurrence; determining when the document is updated such that the up-to-date indexing information is out of date; and creating a second index containing new up-to-date indexing information for the document and updating the fresh index table to reflect that the second index contains the new up-to-date indexing information for the document.
Claim 13
Dependent Claim
46 words
The method of claim 8 wherein the data processing system has a file system for storing documents and wherein the step of determining when the document is updated includes the step of receiving a notification from the file system indicating that the document has been updated.
Claim 14
Dependent Claim
35 words
The method of claim 9 wherein the step of receiving a notification includes the step of receiving a notification from the file system indicating that the document has been updated in response to user input.
Claim 15
Dependent Claim
38 words
The method of claim 8 wherein the data processing system has resources, and wherein the method includes the steps of determining utilization of the resources, and when the resources are underutilized, creating the second index for the document.
Claim 16
Dependent Claim
169 words
In a data processing system having documents, a plurality of indexes containing indexing information for the documents, and a fresh index table, a first type of index being a master index and a second type of index being a shadow index, the fresh index table having entries, each entry indicating which shadow index has up-to-date indexing information for one of the documents, a method for automatically indexing documents comprising the steps of: accessing the documents; creating a master index containing up-to-date indexing information for the documents, wherein the indexing information contains a keyword, at least one document identifier for each keyword, and at least one occurrence for each document identifier; receiving an indication that one of the documents has been updated such that the up-to-date indexing information for the document is out of date; creating a shadow index for the document containing new up-to-date indexing information; and adding an entry into the fresh index table indicating that the shadow index contains the new up-to-date indexing information for the document.
Claim 17
Dependent Claim
169 words
In a data processing system having documents, a plurality of indexes containing indexing information for the documents, and a fresh index table, a first type of index being a master index and a second type of index being a shadow index, the fresh index table having entries, each entry indicating which shadow index has up-to-date indexing information for one of the documents, a method for automatically indexing documents comprising the steps of: accessing the documents; creating a master index containing up-to-date indexing information for the documents, wherein the indexing information contains a keyword, at least one document identifier for each keyword, and at least one occurrence for each document identifier; receiving an indication that one of the documents has been updated such that the up-to-date indexing information for the document is out of date; creating a shadow index for the document containing new up-to-date indexing information; and adding an entry into the fresh index table indicating that the shadow index contains the new up-to-date indexing information for the document.
Claim 18
Dependent Claim
43 words
The method of claim 12 wherein the step of creating a master index includes the step of creating the master index containing indexing information from the documents, wherein the indexing information contains a derived keyword that is derived from data in the document.
Claim 19
Dependent Claim
53 words
The method of claim 12, further including the steps of: receiving an indication that a second document has been updated; creating a second shadow index for the second document; and adding an entry into the fresh index table indicating that the second shadow index contains most recent indexing information for the second document.
Claim 20
Dependent Claim
26 words
The method of claim 14, further including the step of merging the first shadow index and the second shadow index to create a third shadow index.
Claim 21
Dependent Claim
58 words
The method of claim 15 wherein the data processing system has resources and wherein the step of merging the first shadow index includes the step of determining when the resources are underutilized and when it is determined that the resources are underutilized, merging the first shadow index and the second shadow index to create a third shadow index.
Claim 22
Dependent Claim
16 words
The method of claim 15, further including the step of storing the third shadow index persistently.
Claim 23
Dependent Claim
25 words
The method of claim 12, further including the step of merging the shadow index and the first master index to create a second master index.
Claim 24
Dependent Claim
56 words
The method of claim 18 wherein the data processing system has resources and wherein the step of merging the shadow index includes the step of determining when the resources are underutilized and when it is determined that the resources are underutilized, merging the shadow index and the first master index to create a second master index.
Claim 25
Dependent Claim
173 words
An automatic document index system comprising: a plurality of documents; a master index containing indexing information for the documents that is stored at startup of the automatic document index system; a plurality of shadow indexes, wherein a shadow index is generated when a document is updated such that the indexing information for the document in the master index becomes out of date and wherein the shadow index contains up-to-date indexing information for the document that is updated; a fresh index table containing entries, each entry indicating which shadow index has the up-to-date indexing information for one of the documents; and a query component for receiving a request for indexing information, for retrieving indexing information from the master index that satisfies the request, for retrieving indexing information from the shadow indexes that satisfies the request, for accessing the fresh index table with the retrieved indexing information from the master index and the shadow indexes to determine up-to-date indexing information that satisfies the request and for returning the up-to-date indexing information that satisfies the request.
Claim 26
Dependent Claim
173 words
An automatic document index system comprising: a plurality of documents; a master index containing indexing information for the documents that is stored at startup of the automatic document index system; a plurality of shadow indexes, wherein a shadow index is generated when a document is updated such that the indexing information for the document in the master index becomes out of date and wherein the shadow index contains up-to-date indexing information for the document that is updated; a fresh index table containing entries, each entry indicating which shadow index has the up-to-date indexing information for one of the documents; and a query component for receiving a request for indexing information, for retrieving indexing information from the master index that satisfies the request, for retrieving indexing information from the shadow indexes that satisfies the request, for accessing the fresh index table with the retrieved indexing information from the master index and the shadow indexes to determine up-to-date indexing information that satisfies the request and for returning the up-to-date indexing information that satisfies the request.
Claim 27
Independent Claim
147 words
A method in a computer system for identifying which of a plurality of documents contain a requested keyword, each document containing words, certain words being designated as keywords, the method comprising: creating a master index that contains, for each keyword, an indication of which documents contain that keyword; receiving an indication that one or more documents have been updated; creating a shadow index that contains, for each keyword, an indication of which of the updated documents contain that keyword; creating a fresh index table with an indication of each updated document; receiving a request to identify which documents contain the requested keyword; identifying from the master index which documents contain the requested keyword and which documents are not indicated in the fresh index table; and identifying from the shadow index which updated documents contain the requested keyword wherein each of the identified documents contains the requested keyword.
Claim 28
Independent Claim
147 words
A method in a computer system for identifying which of a plurality of documents contain a requested keyword, each document containing words, certain words being designated as keywords, the method comprising: creating a master index that contains, for each keyword, an indication of which documents contain that keyword; receiving an indication that one or more documents have been updated; creating a shadow index that contains, for each keyword, an indication of which of the updated documents contain that keyword; creating a fresh index table with an indication of each updated document; receiving a request to identify which documents contain the requested keyword; identifying from the master index which documents contain the requested keyword and which documents are not indicated in the fresh index table; and identifying from the shadow index which updated documents contain the requested keyword wherein each of the identified documents contains the requested keyword.
Claim 29
Dependent Claim
127 words
In a data processing system having documents, a master index containing indexing information for the documents when the documents are indexed for a first time, a plurality of shadow indexes each containing indexing information for a document when the document is indexed for at least a second time, and a fresh index table having entries that indicate a shadow index having a most recent indexing information for a document, a method comprising the steps of: receiving a query for indexing information; generating query results that satisfy the received query by accessing the master index and the shadow indexes; determining which of the generated query results contains most recent indexing information by accessing the fresh index table; and returning the query results containing the most recent indexing information.
Claim 30
Dependent Claim
127 words
In a data processing system having documents, a master index containing indexing information for the documents when the documents are indexed for a first time, a plurality of shadow indexes each containing indexing information for a document when the document is indexed for at least a second time, and a fresh index table having entries that indicate a shadow index having a most recent indexing information for a document, a method comprising the steps of: receiving a query for indexing information; generating query results that satisfy the received query by accessing the master index and the shadow indexes; determining which of the generated query results contains most recent indexing information by accessing the fresh index table; and returning the query results containing the most recent indexing information.
Claim 31
Independent Claim
129 words
A method in a computer system for identifying which of a plurality of documents contain a requested keyword, each document containing words, certain words being designated as keywords, the method comprising: creating a master index that contains, for each keyword, an indication of which documents contain that keyword; receiving an indication that one or more documents have been updated; creating a shadow index that contains, for each keyword, an indication of which of the updated documents contain that keyword; receiving a request to identify which documents contain the requested keyword; identifying from the master index which documents contain the requested keyword and have not been updated; and identifying from the shadow index which updated documents contain the requested keyword wherein each of the identified documents contains the requested keyword.
Claim 32
Independent Claim
129 words
A method in a computer system for identifying which of a plurality of documents contain a requested keyword, each document containing words, certain words being designated as keywords, the method comprising: creating a master index that contains, for each keyword, an indication of which documents contain that keyword; receiving an indication that one or more documents have been updated; creating a shadow index that contains, for each keyword, an indication of which of the updated documents contain that keyword; receiving a request to identify which documents contain the requested keyword; identifying from the master index which documents contain the requested keyword and have not been updated; and identifying from the shadow index which updated documents contain the requested keyword wherein each of the identified documents contains the requested keyword.
Claim 33
Dependent Claim
168 words
A computer-readable medium whose contents cause a data processing system to index documents, the data processing system having a plurality of indexes and a fresh index table, each document having an associated index containing out-of-date indexing information for the document and having an associated index containing up-to-date indexing information that supersedes the out-of-date indexing information for the document, the fresh index table having entries that indicate the index having the up-to-date indexing information for each document, by performing the steps of: receiving a request to determine which of the documents contains a keyword; accessing the indexes to retrieve aggregate indexing information that indicates the documents containing the keyword, the aggregate indexing information comprising both up-to-date indexing information and out-of-date indexing information; and for each of the documents containing the keyword, accessing the fresh index table with the aggregate indexing information to determine the index having the up-to-date indexing information for the document and to identify the up-to-date indexing information for the document from among the aggregate indexing information.
Claim 34
Dependent Claim
168 words
A computer-readable medium whose contents cause a data processing system to index documents, the data processing system having a plurality of indexes and a fresh index table, each document having an associated index containing out-of-date indexing information for the document and having an associated index containing up-to-date indexing information that supersedes the out-of-date indexing information for the document, the fresh index table having entries that indicate the index having the up-to-date indexing information for each document, by performing the steps of: receiving a request to determine which of the documents contains a keyword; accessing the indexes to retrieve aggregate indexing information that indicates the documents containing the keyword, the aggregate indexing information comprising both up-to-date indexing information and out-of-date indexing information; and for each of the documents containing the keyword, accessing the fresh index table with the aggregate indexing information to determine the index having the up-to-date indexing information for the document and to identify the up-to-date indexing information for the document from among the aggregate indexing information.
Claim 35
Dependent Claim
27 words
The computer readable medium of claim 24 wherein the step of receiving a request further includes the step of receiving the request in response to user input.
Claim 36
Dependent Claim
32 words
The computer readable medium of claim 24 wherein the aggregate indexing information contains the keyword, at least one document identifier for the keyword and at least one occurrence for each document identifier.
Claim 37
Dependent Claim
148 words
A computer-readable medium whose contents cause a data processing system to merge indexes, the data processing system having documents, a plurality of indexes and a fresh index table, a first type of index being a master index having indexing information for all documents at system startup and a second type of index being a shadow index having indexing information for at least one document that is updated at system runtime, the fresh index table having entries that indicate a shadow index having a most recent indexing information for a document, by performing the steps of: accessing the shadow indexes and the master index to retrieve indexing information for all of the documents; accessing the fresh index table to determine most recent indexing information for all of the documents from the retrieved indexing information; and creating an index containing the most recent indexing information for all of the documents.
Claim 38
Dependent Claim
148 words
A computer-readable medium whose contents cause a data processing system to merge indexes, the data processing system having documents, a plurality of indexes and a fresh index table, a first type of index being a master index having indexing information for all documents at system startup and a second type of index being a shadow index having indexing information for at least one document that is updated at system runtime, the fresh index table having entries that indicate a shadow index having a most recent indexing information for a document, by performing the steps of: accessing the shadow indexes and the master index to retrieve indexing information for all of the documents; accessing the fresh index table to determine most recent indexing information for all of the documents from the retrieved indexing information; and creating an index containing the most recent indexing information for all of the documents.
Claim 39
Dependent Claim
175 words
A computer-readable medium whose contents cause a data processing system to index documents, the data processing system having a plurality of indexes containing indexing information for the documents, and a fresh index table, a first type of index being a master index and a second type of index being a shadow index, the fresh index table having entries, each entry indicating which shadow index has up-to-date indexing information for one of the documents, by performing the steps of: accessing the documents; creating a master index containing up-to-date indexing information for the documents, wherein the indexing information contains a keyword, at least one document identifier for each keyword, and at least one occurrence for each document identifier; receiving an indication that one of the documents has been updated such that the up-to-date indexing information for the document is out of date; creating a shadow index for the document containing new up-to-date indexing information; and adding an entry into the fresh index table indicating that the shadow index contains the new up-to-date indexing information for the document.
Claim 40
Dependent Claim
175 words
A computer-readable medium whose contents cause a data processing system to index documents, the data processing system having a plurality of indexes containing indexing information for the documents, and a fresh index table, a first type of index being a master index and a second type of index being a shadow index, the fresh index table having entries, each entry indicating which shadow index has up-to-date indexing information for one of the documents, by performing the steps of: accessing the documents; creating a master index containing up-to-date indexing information for the documents, wherein the indexing information contains a keyword, at least one document identifier for each keyword, and at least one occurrence for each document identifier; receiving an indication that one of the documents has been updated such that the up-to-date indexing information for the document is out of date; creating a shadow index for the document containing new up-to-date indexing information; and adding an entry into the fresh index table indicating that the shadow index contains the new up-to-date indexing information for the document.
Claim 41
Dependent Claim
44 words
The computer-readable medium of claim 28 wherein the step of creating a master index includes the step of creating the master index containing indexing information from the documents, wherein the indexing information contains a derived keyword that is derived from data in the document.
Claim 42
Dependent Claim
54 words
The computer-readable medium of claim 28, further including the steps of: receiving an indication that a second document has been updated; creating a second shadow index for the second document; and adding an entry into the fresh index table indicating that the second shadow index contains most recent indexing information for the second document.
Claim 43
Dependent Claim
27 words
The computer-readable medium of claim 30, further including the step of merging the first shadow index and the second shadow index to create a third shadow index.
Claim 44
Dependent Claim
59 words
The computer-readable medium of claim 31 wherein the data processing system has resources and wherein the step of merging the first shadow index includes the step of determining when the resources are underutilized and when it is determined that the resources are underutilized, merging the first shadow index and the second shadow index to create a third shadow index.
Claim 45
Dependent Claim
17 words
The computer-readable medium of claim 31, further including the step of storing the third shadow index persistently.
Claim 46
Dependent Claim
26 words
The computer-readable medium of claim 28, further including the step of merging the shadow index and the first master index to create a second master index.
Claim 47
Dependent Claim
57 words
The computer-readable medium of claim 34 wherein the data processing system has resources and wherein the step of merging the shadow index includes the step of determining when the resources are underutilized and when it is determined that the resources are underutilized, merging the shadow index and the first master index to create a second master index.
References Cited (Backward Citations)
US4498142A
Cited
US4754326A
Cited
US4768144A
Cited
US4760526A
Cited
US4817032A
Cited
US4819156A
Cited
US5119291A
Cited
US4827462A
Cited
US4875159A
Cited
US4961139A
Cited
US5020019A
Cited
US5202982A
Cited
US5129082A
Cited
US5153831A
Cited
US5051745A
Cited
US5247437A
Cited
US5193180A
Cited
US5204958A
Cited
US5251316A
Cited
US5347653A
Cited
US5293616A
Cited
US5404510A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-11-03 | 2001-05-05 | 2001-11-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-11-03 | 2005-05-05 | 2005-11-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-11-03 | 2009-05-05 | 2009-11-04 | $7700.00 | Window Closed / Lapsed |