Method for using query templates in directory caches

• US 20030097355A1
• Filed: 04/25/2001
• Published: 05/22/2003
• Est. Priority Date: 04/25/2000
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Kapitskaia, Olga, Srivastava, Divesh, Ng, Raymond
• Granted Patent: US 6,904,433 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: H04L 61/4517 using open systems interconnection [OSI] directories, e.g. X.500
• CPC Class Codes: H04L 61/4523 using lightweight directory access protocol [LDAP]
• CPC Class Codes: H04L 67/289 Intermediate processing functionally located close to the data consumer application, e.g. in same machine, in same home or in same sub-network
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 9/40 Network security protocols
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99939 Privileged access
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention discloses the use of generalized queries, referred to as query templates, obtained by generalizing individual user queries, as the semantic basis for low overhead, high benefit directory caches for handling declarative queries. Caching effectiveness can be improved by maintaining a set of generalizations of queries and admitting such generalizations into the cache when their estimated benefits are sufficiently high. In a preferred embodiment of the invention, the admission of query templates into the cache can be done in what is referred to by the inventors as a “revolutionary” fashion—followed by stable periods where cache admission and replacement can be done incrementally in an evolutionary fashion. The present invention can lead to considerably higher hit rates and lower server-side execution and communication costs than conventional caching of directory queries—while keeping the clientside computational overheads comparable to query caching.

Claims

1. A method of managing a network directory cache, comprising the steps of:

receiving and storing a plurality of user queries;

creating a query template that generalizes the user queries; and

retrieving directory entries answering the query template so that the directory entries can be stored in the cache.

2. The invention of claim 1 wherein the directory entries are retrieved after estimating benefits of storing the directory entries in the cache.

3. The invention of claim 1 wherein the query template is stored and modified as new user queries are received.

4. The invention of claim 1 wherein the network directory cache utilizes the Lightweight Directory Access Protocol.

5. A method of managing a network directory cache comprising the steps of:

maintaining a plurality of candidate templates that may be used to retrieve directory entries to store in the cache;

receiving and storing a user query; and

generating a plurality of new candidate templates that generalize the candidate templates with the user query.

6. The invention of claim 5 wherein the new candidate templates are generated after estimating benefits of storing directory entries in the cache answering the new candidate templates.

7. The invention of claim 5 wherein the network directory cache utilizes the Lightweight Directory Access Protocol.

8. A method of managing a network directory cache, comprising the steps of:

maintaining a plurality of candidate templates;

estimating a benefit of caching directory results answering the candidate templates; and

selecting a candidate template based on its benefit estimate and retrieving directory entries answering the candidate template so that the directory entries can be stored in the cache.

9. The invention of claim 8 wherein the directory entries are retrieved to replace old directory entries in the cache.

10. The invention of claim 8 wherein the directory entries are retrieved only if the estimated benefit is greater than an estimate of benefits of old directory entries in the cache.

11. The invention of claim 10 wherein old directory entries in the cache are replaced incrementally if the the estimated benefit is not greater than an estimate of benefits of old directory entries in the cache.

12. The invention of claim 8 wherein the network directory cache utilizes the Lightweight Directory Access Protocol.