Scope testing of documents in a search engine using document to folder mapping

• US 5,890,147 A
• Filed: 03/07/1997
• Issued: 03/30/1999
• Est. Priority Date: 03/07/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Peltonen, Kyle G., Raju, Sitaram C. V., Milewski, Bartosz B.
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): WALLACE, MICHAEL J
• Application Number:
  US08/813,618
• Time in Patent Office: 753 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/6, 707/100, 707/200, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/93 Document management systems
• 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/99943 Generating database or data structure, e.g. via user interface

Abstract

A method and mechanism for responding to a query in a hierarchically organized system of documents and folders. In response to the query, a set of documents is retrieved based on specified criteria. Only documents in that set which match a specified scope are returned in a result set. Scope testing is performed on each of the documents in the set by obtaining a document identifier of each document, and then using that document identifier to obtain a document identifier of the parent folder thereof. The document identifier of the parent folder is used as a key to a data structure, which stores flags indicative of whether parent folders are in the specified scope. If the flag for a given parent folder indicates that the parent folder is in scope, the document having that parent is returned in the result set. If the flag indicates that the current document is not in scope, that document is not returned. If there was not an entry in the data structure for that key, prefix matching is performed on the parent folder to determine whether it is in scope. The parent folder scope information is then added to the data structure as a flag indexed by the document identifier of the parent folder.

Claims

1. In a hierarchically-organized system of documents and folders, a method of responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, the method comprising the steps of:

selecting a retrieved document as a current document;

obtaining an identifier of the current document;

obtaining an identifier of a parent folder of the current document;

accessing a data structure to determine scope information of the current document, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of the whether the current document is in scope; and

returning information for the current document in response to the query when the value of the flag equals a predetermined value.

2. The method of claim 1 wherein the step of obtaining the identifier of the parent folder comprises the step of retrieving the identifier of the parent folder from a document identifier to parent document identifier mapping table.

3. The method of claim 2 wherein the step of retrieving the identifier of the parent folder includes the step of using the document identifier of the current document as an index to the document identifier to parent document identifier mapping table.

4. The method of claim 1 wherein the step of returning information for the current document comprises the step of placing information about the current document in a result set.

5. The method of claim 1 wherein the data structure comprises a hash table.

6. The method of claim 1 further comprising the steps of selecting another retrieved document as a second current document, obtaining an identifier of the second current document, obtaining an identifier of a second parent folder of the second current document, accessing the data structure with the identifier of the second parent folder as an index thereto, receiving a value from the data structure indicating that the identifier of the second parent folder does not correspond to an entry in the data structure, comparing the second parent folder with the specified scope, and adding an entry to the data structure indexed by the identifier of the second parent folder, the entry including a value indicative of whether the second parent folder corresponds to the specified scope.

7. The method of claim 6 wherein the step of comparing the second parent folder with the specified scope includes the steps of obtaining an identifier of a third folder which is hierarchically above the second parent folder, and accessing the data structure with the identifier of the third parent folder as an index thereto.

8. The method of claim 6 wherein the entered value indexed by the identifier of the second parent folder is equal to the predetermined value when the second parent folder corresponds to the specified scope.

9. The method of claim 1 wherein the parent folder is an immediate parent folder of the current document.

10. The method of claim 1 wherein the query specifies at least one folder, and further comprising the step of priming the data structure with a flag indexed by an identifier of the at least one folder, the flag having a value indicating that the at least one folder is in scope.

11. The method of claim 1 wherein the flag indicates that the document is in scope, and further comprising the steps of obtaining an identifier of a folder hierarchically below the parent folder, and entering at least one additional flag into the data structure indexed by the identifier of the folder below the parent folder, the flag having a value indicating that the folder below the parent folder is in scope.

12. The method of claim 1 wherein the hierarchically-organized system is a file system.

13. In a hierarchically-organized system of documents and folders, a mechanism for responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, comprising:

means for selecting a retrieved document as a current document;

means for obtaining an identifier of the current document;

means for obtaining an identifier of a parent folder of the current document;

means for accessing a data structure to determine scope information of the current document, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of whether the current document is in scope; and

means for returning information for the current document in response to the query when the value of the flag indicates the document is in scope.

14. The mechanism of claim 13 wherein the means for obtaining an identifier of the parent folder includes a document identifier to parent document identifier mapping table.

15. The mechanism of claim 13 wherein the data structure comprises a hash table.

16. The mechanism of claim 13 wherein the hierarchically-organized system is a file system.

17. The mechanism of claim 13 further comprising means for selecting another retrieved document as a second current document, means for obtaining an identifier of the second current document, means for obtaining an identifier of a second parent folder of the second current document, means for accessing a data structure with the identifier of the second parent folder as an index thereto, means for receiving a value from the data structure indicating that the identifier of the second parent folder does not correspond to an entry in the data structure, means for comparing the second parent folder with the specified scope, and means for adding an entry to the data structure indexed by the identifier of the second parent folder, the entry including a value indicative of whether the second parent folder corresponds to the specified scope.

18. The mechanism of claim 17 wherein the means for comparing the second parent folder with the specified scope includes means for obtaining an identifier of a third folder which is hierarchically above the second parent folder, and means for accessing the data structure with the identifier of the third parent folder as an index thereto.

19. The mechanism of claim 13 wherein the parent folder of the current document is the immediate parent folder.

20. The mechanism of claim 13 wherein the flag indicates that the document is not in scope, and further comprising means for obtaining an identifier of a folder hierarchically below the parent folder, and means for entering at least one additional flag into the data structure indexed by the identifier of the folder below the parent folder, the flag having a value indicating that the folder below the parent folder is not in scope.

21. In a query engine, a mechanism for responding to a query, comprising:

a criteria matching component for retrieving one or more documents in response to a user specified restriction; and

a scope testing component for selecting each of the retrieved documents in response to a user specified scope, the scope testing component including means for obtaining an identifier of a selected one of the documents, means for accessing a table indexed by the identifier of the current document to obtain an identifier of a parent folder above the current document, means for accessing a data structure indexed by the identifier of the parent folder, the data structure including a flag indicative of the scope of documents stored below the parent folder, and means for returning information for the current document in response to the query when the flag equals a predetermined value.

22. In a query engine having a criteria matching component for retrieving documents in response to a user specified restriction, a method of determining the scope of at least one of the plurality of documents in response to a scope specification, the method comprising the steps of:

selecting a retrieved document as a current document, obtaining an identifier of the current document, obtaining an identifier of a parent folder of the current document, accessing a data structure using the identifier of the parent folder as an index, the data structure including flags indexed by the identifiers of parent folders;

receiving a response from the data structure, the response comprising a flag having a value indicative of the whether the current document is in scope, or an indication that the parent folder was not indexed in the data structure; and

when the flag is received, determining if the value indicates that the document is in scope, and if in scope, returning information for the current document in response to the query; and

when the indication that the parent folder was not indexed is received, comparing the parent folder against the scope specification to determine the scope of the current document, storing in the data structure a flag indexed by the parent folder, the flag having a value indicative of the whether the current document is in scope, and if in scope, returning information for the current document in response to the query.

23. The method of claim 22 wherein the step of obtaining an identifier of a parent folder of the current document includes the step of accessing a document to parent mapping table.

24. In a hierarchically-organized system of documents and folders, a method of responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, the method comprising the steps of:

selecting a retrieved document as a current document;

obtaining an identifier of the current document;

obtaining an identifier of a parent folder of the current document;

accessing a data structure, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of the whether the current document is in scope;

returning information for the current document in response to the query when the value of the flag equals a predetermined value;

selecting another retrieved document as a second current document;

obtaining an identifier of the second current document;

obtaining an identifier of a second parent folder of the second current document;

accessing the data structure with the identifier of the second parent folder as an index thereto;

receiving a value from the data structure indicating that the identifier of the second parent folder does not correspond to an entry in the data structure;

comparing the second parent folder with the specified scope; and

adding an entry to the data structure indexed by the identifier of the second parent folder, the entry including a value indicative of whether the second parent folder corresponds to the specified scope.

25. The method of claim 24 wherein the step of comparing the second parent folder with the specified scope includes the steps of obtaining an identifier of a third folder which is hierarchically above the second parent folder, and accessing the data structure with the identifier of the third parent folder as an index thereto.

26. The method of claim 24 wherein the entered value indexed by the identifier of the second parent folder is equal to the predetermined value when the second parent folder corresponds to the specified scope.

27. In a hierarchically-organized system of documents and folders, a method of responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, wherein the query specifies at least one folder, the method comprising the steps of:

selecting a retrieved document as a current document;

obtaining an identifier of the current document;

obtaining an identifier of a parent folder of the current document;

accessing a data structure, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of the whether the current document is in scope;

returning information for the current document in response to the query when the value of the flag equals a predetermined value; and

priming the data structure with a flag indexed by an identifier of the at least one folder specified in the query, the flag having a value indicating that the at least one folder is in scope.

28. In a hierarchically-organized system of documents and folders, a method of responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, the method comprising the steps of:

selecting a retrieved document as a current document;

obtaining an identifier of the current document;

obtaining an identifier of a parent folder of the current document;

accessing a data structure, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of the whether the current document is in scope;

returning information for the current document in response to the query when the value of the flag equals a predetermined value indicating that the document is in scope;

obtaining an identifier of a folder hierarchically below the parent folder; and

entering at least one additional flag into the data structure indexed by the identifier of the folder below the parent folder, the flag having a value indicating that the folder below the parent folder is in scope.

29. In a hierarchically-organized system of documents and folders, a mechanism for responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, comprising:

means for selecting a retrieved document as a current document;

means for obtaining an identifier of the current document;

means for obtaining an identifier of a parent folder of the current document;

means for accessing a data structure, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of whether the current document is in scope; and

means for returning information for the current document in response to the query when the value of the flag indicates the document is in scope;

means for selecting another retrieved document as a second current document, means for obtaining an identifier of the second current document;

means for obtaining an identifier of a second parent folder of the second current document;

means for accessing a data structure with the identifier of the second parent folder as an index thereto;

means for receiving a value from the data structure indicating that the identifier of the second parent folder does not correspond to an entry in the data structure;

means for comparing the second parent folder with the specified scope; and

means for adding an entry to the data structure indexed by the identifier of the second parent folder, the entry including a value indicative of whether the second parent folder corresponds to the specified scope.

30. The mechanism of claim 29 wherein the means for comparing the second parent folder with the specified scope includes means for obtaining an identifier of a third folder which is hierarchically above the second parent folder, and means for accessing the data structure with the identifier of the third parent folder as an index thereto.

31. In a hierarchically-organized system of documents and folders, a mechanism for responding to a query with at least one document that matches a specified scope from among one or more documents which have been retrieved based on specified criteria, comprising, means for selecting a retrieved document as a current document, means for obtaining an identifier of the current document, means for obtaining an identifier of a parent folder of the current document, and means for accessing a data structure, the data structure including a flag indexed by the identifier of the parent folder wherein the flag has a value indicative of whether the current document is in scope;

means for returning information for the current document in response to the query when the value of the flag indicates the document is in scope; and

when the value of the flag indicates the document is not in scope, means for obtaining an identifier of a folder hierarchically below the parent folder, and means for entering at least one additional flag into the data structure indexed by the identifier of the folder below the parent folder, the flag having a value indicating that the folder below the parent folder is not in scope.