Patent US106041A successfully refreshed from Google Patents.
Patent US5890147A successfully refreshed from Google Patents.
US5890147A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Scope testing of documents in a search engine using document to folder mapping
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-03-07
•
Granted: 1999-03-30
•
Expires: 2017-03-07
Abstract
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.
Inventors
- 👤 Kyle G. Peltonen
- 👤 Sitaram C. V. Raju
- 👤 Bartosz B. Milewski
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-28 16:55
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/10; G06F16/90; G06F16/93; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 40
Claim 1
Independent Claim
135 words
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.
Claim 2
Dependent Claim
135 words
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.
Claim 3
Dependent Claim
37 words
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.
Claim 4
Dependent Claim
41 words
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.
Claim 5
Dependent Claim
29 words
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.
Claim 6
Dependent Claim
13 words
The method of claim 1 wherein the data structure comprises a hash table.
Claim 7
Dependent Claim
125 words
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.
Claim 8
Dependent Claim
54 words
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.
Claim 9
Dependent Claim
34 words
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.
Claim 10
Dependent Claim
18 words
The method of claim 1 wherein the parent folder is an immediate parent folder of the current document.
Claim 11
Dependent Claim
51 words
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.
Claim 12
Dependent Claim
70 words
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.
Claim 13
Dependent Claim
13 words
The method of claim 1 wherein the hierarchically-organized system is a file system.
Claim 14
Dependent Claim
141 words
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.
Claim 15
Dependent Claim
141 words
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.
Claim 16
Dependent Claim
26 words
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.
Claim 17
Dependent Claim
13 words
The mechanism of claim 13 wherein the data structure comprises a hash table.
Claim 18
Dependent Claim
13 words
The mechanism of claim 13 wherein the hierarchically-organized system is a file system.
Claim 19
Dependent Claim
136 words
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.
Claim 20
Dependent Claim
55 words
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.
Claim 21
Dependent Claim
18 words
The mechanism of claim 13 wherein the parent folder of the current document is the immediate parent folder.
Claim 22
Dependent Claim
73 words
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.
Claim 23
Dependent Claim
142 words
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.
Claim 24
Dependent Claim
142 words
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.
Claim 25
Dependent Claim
240 words
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.
Claim 26
Dependent Claim
240 words
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.
Claim 27
Dependent Claim
31 words
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.
Claim 28
Dependent Claim
241 words
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.
Claim 29
Dependent Claim
241 words
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.
Claim 30
Dependent Claim
54 words
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.
Claim 31
Dependent Claim
34 words
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.
Claim 32
Dependent Claim
171 words
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.
Claim 33
Dependent Claim
171 words
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.
Claim 34
Dependent Claim
182 words
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.
Claim 35
Dependent Claim
182 words
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.
Claim 36
Dependent Claim
262 words
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.
Claim 37
Dependent Claim
262 words
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.
Claim 38
Dependent Claim
55 words
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.
Claim 39
Dependent Claim
201 words
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.
Claim 40
Dependent Claim
201 words
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.
References Cited (Backward Citations)
US5202986A
Cited
US5333317A
Cited
US5319762A
Cited
US5544360A
Cited
US5465353A
Cited
US5692173A
Cited
US5729730A
Cited
US5701469A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-03-29 | 2002-09-28 | 2003-03-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-03-29 | 2006-09-28 | 2007-03-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-03-29 | 2010-09-28 | 2011-03-30 | $7700.00 | Window Closed / Lapsed |