Method for using query templates in directory caches
View Patent ↗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.
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, wherein said directory entries are stored in the cache thus forming said directory cache, and wherein said directory entries are retrieved after estimating benefits of storing the directory entries in the cache.
2. The method of claim 1 wherein the query template is stored and modified as new user queries are received.
3. The method of claim 1 wherein the network directory cache utilizes the Lightweight Directory Access Protocol.
4. A method of managing a network directory cache, comprising the steps of:
maintaining a plurality of candidate templates to 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, wherein said the new candidate templates are generated after estimating benefits of storing the directory entries in the cache answering the new candidate templates.
5. The method of claim 4 wherein the network directory cache utilizes the Lightweight Directory Access Protocol.
6. 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, wherein said directory entries are stored in the cache, and wherein said directory entries are retrieved only if they estimated benefit is greater than an estimate of benefits of old directory entries in the cache.
7. The method of claim 6 wherein the directory entries are retrieved to replace old directory entries in the cache.
8. The method of claim 6 wherein old directory entries in the cache are replaced incrementally if the estimated benefit is not greater than an estimate of benefits of old directory entries in the cache.
9. The method of claim 6 wherein the network directory cache utilizes the Lightweight Directory Access Protocol.
10. A method of managing a network directory cache, comprising the steps of:
receiving and storing a plurality of user queries to form a stored plurality of user queries;
creating one or more query templates, wherein each query template generalizes a chosen subset of stored plurality of user queries;
submitting said one or more query templates as a search query to a directory database on a server; and
receiving entries of said directory database that are responsive to said queries and storing them in the cache thus forming said directory cache, wherein said directory entries are received after estimating benefits of storing directory entries in the cache.
11. The method of claim 10 where said step of creating one or more query templates comprises:
creating a first number of candidate query templates;
evaluating a cost and benefit of each of the candidate query templates; and
selecting a second number of query templates from among said candidate query templates based on the evaluated costs and benefits.
12. The method of claim 11 , further comprising the steps of:
receiving and storing a query, thereby forming a modified plurality of stored user queries;
repeating said step of creating one or more query templates; and
updating said directory cache.
13. The method of claim 11 where said step of updating comprises the steps of:
retrieving entries from said directory database,
adding the retrieved entries to said directory cache; and
removing at least one entry from said directory cache.