Synonyms
Paging in Web search engines; Search engine caching and prefetching; Search engine query result caching
Definition
Caching is a well-known concept in systems with multiple tiers of storage. For simplicity, consider a system storing N objects in relatively slow memory, that also has a smaller but faster memory buffer of capacity k which can store copies of k of the N objects (N > > k). This fast memory buffer is called the cache. The storage system is presented with a continuous stream of queries, each requesting one of the N objects. If the object is stored in the cache, a cache hit occurs and the object is quickly retrieved. Otherwise, a cache miss occurs, and the object is retrieved from the slower memory. At this point, the storage system can opt to save the newly retrieved object in the cache. When the cache is full (i.e., already contains k objects), this entails evicting some currently cached object. Such decisions are handled by a replacement policy, whose goal is to...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Baeza-Yates R, Gionis A, Junqueira F, Murdock V, Plachouras V, Silvestri F. The impact of caching on search engines. In: Proceedings of the 33rd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval; 2007. p. 183–90.
Baeza-Yates R, Junqueira F, Plachouras V, Witschel HF. Admission policies for caches of search engine results. In: Proceedings of the 14th International Symposium on String Processing and Information Retrieval; 2007. p. 74–85.
Belady LA. A study of replacement algorithms for a virtual-storage computer. IBM Syst J. 1966;5(2):78–101.
Fagni T, Perego R, Silvestri F, Orlando S. Boosting the performance of web search engines: caching and prefetching query results by exploiting historical usage data. ACM Trans Inf Syst. 2006;24(1):51–78.
Karedla R, Love JS, Wherry BG. Caching strategies to improve disk system performance. Computer. 1994;27(3):38–46.
Lempel R, Moran S. Optimizing result prefetching in web search engines with segmented indices. In: Proceedings of the 28th International Conference on Very Large Data Bases; 2002. p. 370–81.
Lempel R, Moran S. Predictive caching and prefetching of query results in search engines. In: Proceedings of the 12th International World Wide Web Conference; 2003. p. 19–28.
Lempel R, Moran S. Competitive caching of query results in search engines. Theory Comput Sci. 2004;324(2):253–71.
Lempel R, Moran S. Optimizing result prefetching in web search engines with segmented indices. ACM Trans Internet Tech. 2004;4(1):31–59.
Long X, Suel T. Three-level caching for efficient query processing in large web search engines. In: Proceedings of the 14th International World Wide Web Conference; 2005. p. 257–66.
Markatos EP. On caching search engine query results. Comput Commun. 2001;24(2):137–43.
Saraiva P, Moura E, Ziviani N, Meira W, Fonseca R, Ribeiro-Neto B. Rank-preserving two-level caching for scalable search engines. In: Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval; 2001. p. 51–8.
Silverstein C, Henzinger M, Marais H, Moricz M. Analysis of a very large altavista query log. Technical Report 1998-014, Compaq Systems Research Center. Oct 1998.
Silvestri F, Fagni T, Orlando S, Palmerini P, Perego R. A hybrid strategy for caching web search engine results. In: Proceedings of the 12th International World Wide Web Conference; 2003 (Poster).
Sleator DD, Tarjan RE. Amortized efficiency of list update and paging rules. Commun ACM. 1985;28(2):202–8.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2018 Springer Science+Business Media, LLC, part of Springer Nature
About this entry
Cite this entry
Lempel, R., Silvestri, F. (2018). Web Search Result Caching and Prefetching. In: Liu, L., Özsu, M.T. (eds) Encyclopedia of Database Systems. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8265-9_464
Download citation
DOI: https://doi.org/10.1007/978-1-4614-8265-9_464
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-8266-6
Online ISBN: 978-1-4614-8265-9
eBook Packages: Computer ScienceReference Module Computer Science and Engineering