Exploiting the Use of Similar Past Search Results Through a Dynamic Cache

摘要

Search engines are prone to the computation of redundant queries. Without any optimization this can be a costly procedure; limited processing power is used to compute new responses for queries that have already been answered. Despite the latter, little work exists on leveraging similar past queries to reduce the engine's workload while improving its precision. This paper describes a dynamic cache based on an on-line algorithm, which takes advantage of similar past queries to reduce the engine's response times, while simultaneously improving precision. Roughly, the algorithm uses a priority queue to build a dynamic index of past queries, alongside their responses, where each query's priority is linked to its overall popularity (the top-K queries along with their results): similar queries that have appeared multiple times are indexed with a high priority value. This ensures that their results will be easily recoverable from the queue without recomputation. Notably, the algorithm also improves response times for queries that only share a subset of their search terms. Several experiments were performed over a dataset of simulated queries and documents. Empirical results show that the proposed dynamic cache improves on both precision and response times.