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" fashionfollowed 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
querieswhile keeping the clientside computational overheads comparable
to query caching.
