Method and system for automatically indexing data in a document using a fresh index table

• US 5,685,003 A
• Filed: 10/26/1994
• Issued: 11/04/1997
• Est. Priority Date: 12/23/1992
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Milewski, Bartosz, Peltonen, Kyle Gordon
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Thomas, Joseph
• Application Number:
  US08/329,810
• Time in Patent Office: 1,105 Days
• Field of Search: 364/419.19, 364/419.1, 364/419.01, 364/419.17, 395/600, 395/182.13, 395/601, 395/603, 395/619, 395/712, 395/761, 395/792, 395/793, 395/772, 369/47, 369/59
• US Class Current: 715/202
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. The method of claim 15, further including the step of storing the third shadow index persistently.

18. 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.

19. 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.

20. 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.

21. 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.

22. 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.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. 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.

33. The computer-readable medium of claim 31, further including the step of storing the third shadow index persistently.

34. 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.

35. 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.