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 cache, the method comprising the steps of:
determining whether a received user query is answerable by said cache;
querying a data source other than said cache when determining said user query is not answerable by said cache;
storing results of said query in said cache, when space is available in said cache;
determining whether benefit of maintaining existing query templates for said cache versus benefit of introducing a new set of query templates that includes a generalization of said user query,
when the result of the query fetched from a directory server by a cache manager does not fit in said cache; and
identifying and storing said introduced new set of query templates to be associated with said cache if said benefit of maintaining existing query templates for said cache is smaller than the sum of the benefits of said introduced new set of templates that includes a generalization of said user query.
2. A method of managing a cache in response to generalized queries obtained by generalized individual user query is not answerable by said cache, said cache includes a first set of actual templates that corresponds to query result retrieved from said data source in response to a query, and a second set of candidate templates, said method comprising the steps of:
determining whether a received user query is answerable by said cache;
querying a data source other than said cache when determining said user query is not answerable by said cache;
storing results of said query in said cache, when space is available in said cache;
updating each of said candidate templates based on said user query, to form an updated set of candidate templates; and
when said cache has insufficient space to store said responsive query results:
selecting a subset of said updated candidate templates as a set of hypothetical templates, wherein the hypothetical set is a set of templates that, when applied to said data source, would result in an amount of responsive information that can be stored in said cache;
determining whether a collective of said hypothetical set of templates is greater than a collective of said set of actual templates;
replacing said actual templates with said hypothetical set of templates to form a new set of actual templates and, correspondingly, updating said cache to contain information of data store that corresponds to said new set of actual templates, when said step of determining concludes in the affirmative; and
removing a subset actual templates from said set of actual templates, and removing information from said cache that is not associated with any of the templates that remain in said set of actual templates, where the actual templates in said subset are such that the removed information enables storing said responsive information in said cache, and storing said responsive information in said cache, when said step of determining concludes in the negative.