Highly Efficient Query Processing via Temporal Caching

Categories: “Computer Science“

Reference #: 2019-034

OTC Contact: Zeinab Abouissa,  Phone: 202-687-2702, Email: zaa9@georgetown.edu

SUMMARY

Caching improves search engines efficiency. Generally, the cache space is divided into two segments, static and dynamic. The static cache stores responses to persistent common searches (i.e., the top searches), while the dynamic cache is periodically adjusted to deal with unpredictable frequency spikes, potentially triggered by an external event. For example, “earthquake” searches increase when an actual earthquake occurs, leading to inclusion of the results for “earthquake” in the dynamic cache when the cache is updated. 

Researchers at Georgetown University and Italy’s National Research Council (CNR) improved conventional caching system performance by the addition of a third partitioning, a “topic cache.” The topic cache centers on topicality of queries that periodically temporarily spike (for example searches for “World Cup” that spike every four years). Such queries are unaccounted for in the static cache as they are periodic but temporary in nature. The dynamic cache replacement strategy fails to capture topic periodicity, focusing on access patterns rather than topicality. In contrast, the topic cache maintains previous search results for popular topics. In combination, the static, dynamic, and topic caches capture consistent, repetitive, and topically focuses results, respectively. Using commercial query logs, a cache management strategy that includes a topic cache demonstrated performance gains. A schematic of the temporal cache approach is detailed in Figure 1. By supporting a topical query results cache, higher processing throughout is achieved with lower energy expenditure. 

INVENTORS

Ophir Frieder, Ph.D. 
Ida Mele, Ph.D. 
Raffaele Perego, Ph.D. 
Nicola Tonellotta, Ph.D. 

INTELLECTUAL PROPERTY

U.S. Patent No. 10,503,792 
U.S. Patent Application No. 16/654,725