More Web Proxy on the site http://driver.im/

article

On caching search engine query results

Author:

E.P MarkatosAuthors Info & Claims

Computer Communications, Volume 24, Issue 2

Pages 137 - 143

https://doi.org/10.1016/S0140-3664(00)00308-X

Published: 01 February 2001 Publication History

Abstract

In this paper we explore the problem of Caching of Search Engine Query Results in order to reduce the computing and I/O requirements needed to support the functionality of a search engine of the World Wide Web. We study query traces from the EXCITE search engine and show that they have a significant amount of temporal locality that is, a significant percentage of the queries have been submitted more than once by the same or a different user. Using trace-driven simulation we demonstrate that medium-size caches can hold the results of most of the frequently submitted queries. Finally, we compare the effectiveness of static and dynamic caching and conclude that although dynamic caching can use large caches more effectively, static caching can perform better for (very) small caches.

References

[1]

M. Abrams, C.R. Standridge, G. Abdulla, S. Williams, E.A. Fox, Caching proxies: limitations and potentials, Proceedings of the Fourth International WWW Conference, 1995.

[2]

Query caching and optimization in distributed mediator systems. In: Jagadish, H.V., Mumick, I.S. (Eds.), Proceedings of the 1996 ACM SIGMOD Conference on Management of Data, ACM, New York. pp. 137-148.

[3]

A. Bestavros, Speculative data dissemination and service to reduce server load, network traffic and service time for distributed information systems, Proceedings of ICDE '96: The 1996 International Conference on Data Engineering, March 1996.

[4]

P. Cao, S. Irani, Cost-aware WWW proxy caching algorithms, Proceedings of the first USENIX Symposium on Internet Technologies and Systems, 1997, pp. 1937-206.

[5]

J. Challenger, A. Iyengar, P. Danzig, A scalable system for consistently caching dynamic data, INFOCOM 99, 1999.

[6]

A. Chankhunthod, P.B. Danzig, C. Neerdaels, M.F. Schwartz, K.J. Worrell, A hierarchical internet object cache, Proceedings of the 1996 Usenix Technical Conference, 1996.

Digital Library

[7]

D. Dias, W. Kish, R. Muhkerjee, R. Tewari, A scalable and highly available web server, COMPCON 96, 1996.

[8]

D. Duchamp, Prefetching hyperlinks, Proceedings of the second USENIX Symposium on Internet Technologies and Systems, October 1999.

[9]

J. Gwertzman, M. Seltzer, The case for geographical push caching, Proceedings of the Workshop on Hot Operating Systems, 1995.

[10]

A. Iyengar, J. Challenger, Improving web server performance by caching dynamic data, Proceedings of the first USENIX Symposium on Internet Technologies and Systems, 1997.

[11]

B.J. Jansen, A. Spink, J. Bateman, T. Saracevic, Searchers, the subjects they search, and sufficiency: a study of a large sample of EXCITE searches, Proceedings of Webnet 98, 1998.

[12]

R. Karedla, J. Love, B. Wherry, Caching strategies to improve disk system performance, Computer, 1994.

[13]

T.M. Kroeger, D.D.E. Long, J.C. Mogul, Exploring the bounds of web latency reduction from caching and prefetching, Proceedings of the first USENIX Symposium on Internet Technologies and Systems, 1997, pp. 13-22.

[14]

E. Levy-Abegnoli, A. Iyengar, J. Song, Dias: design and performance of a web server accelerator, INFOCOM 99, 1999.

[15]

P. Lorenzetti, L. Rizzo, L. Vicisano, Replacement policies for a proxy cache, 1998, http://www.iet.unipi.it/~luigi/research.html.

[16]

Q. Luo, R. Krishnamurthy, Y. Li, P. Cao, J.F. Naughton, Active Query Caching for Database Web Servers, 1999.

[17]

R. Malpani, J. Lorch, D. Berge, Making World Wide Web caching servers cooperate, Proceedings of the Fourth International WWW Conference, 1995.

[18]

Markatos, E.P., Main memory caching of web documents. Computer Networks and ISDN Systems. v28 i7-11. 893-906.

[19]

E.P. Markatos, C. Chronaki, A top-10 approach to prefetching on the web, Proceedings of the INET 98 Conference, 1998.

[20]

E.P. Markatos. C. Tziviskou, A. Papathanasiou, Effective resource discovery on the World Wide Web, Proceedings of Webnet 98, 1998, pp. 611-616.

[21]

W. Meira Jr., M. Cesario, R. Fonseca, N. Ziv, Integrating WWW caches and search engines, Proceedings of the IEEE Global Telecommunications Internet Mini-Conference, 1999.

[22]

J.C. Mogul, F. Douglis, A. Feldmann, B. Krishnamurthy, Potential benefits of delta-encoding and data compression for HTTP, Proceedings of the ACM SIGCOMM 97, 1997.

Digital Library

[23]

E.J. O'Neil, P.E. O'Neil, G. Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the ACM SIGMOD Conference on Management of Data, 1993, pp. 297-306.

[24]

J. Zhang, P. Cao, K. Beach, Active cache: caching dynamic contents on the web, Proceedings of IFIP International Conference on Distributed Systems Platforms and Open Distributed Processing (Middleware '98), 1998, 373-388.

[25]

Padmanabhan, V.N. and Mogul, J., Using predictive prefetching to improve World Wide Web latency. SIGCOMM Computer Communication Review. v26. 22-36.

Digital Library

[26]

V. Pai, M. Aron, G. Banga, M. Svendsen, P. Druschel, W. Zwaenepoel, E. Nahum, Locality-aware request distribution in cluster-based network servers, Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems, 1998.

Digital Library

[27]

J.E. Pitkow, M. Recker, A simple, yet robust caching algorithm based on dynamic access patterns, Proceedings of the Second International WWW Conference, 1994.

[28]

J.T. Robinson, M.V. Devarakonda, Data cache management using frequency-based replacement, Proceedings of the ACM SIGMETRICS Conference, 1990, pp. 134-142.

[29]

A. Rousskov, V. Soloviev, I. Tatarinov, Static caching for proxy servers, Proceedings of the NLANR Web Cache Workshop, 1997.

[30]

P. Scheuearmann, J. Shim, R. Vingralek, A case for delay-conscious caching of web documents, Sixth International World Wide Web Conference, 1997.

Digital Library

[31]

C. Silverstein, M. Henzinger, H. Marais, M. Moricz, Analysis of a very large AltaVista query log, Technical Report SRC Technical Note 1998-014, 1998.

[32]

A. Spink, B.J. Jansen, J. Bateman, Users' searching behavior on the EXCITE web search engine, Proceedings of Webnet 98, 1998

[33]

M. Taylor, K. Stoffel, J. Saltz, J. Hendler, Using distributed query result caching to evaluate queries for parallel data mining algorithms, Proceedings of the International Conference on Parallel and Distributed Techniques and Applications, 1998.

[34]

Touch, J., Defining high speed protocols: five challenges and an example that survives the challenges. IEEE JSAC. v13 i5. 828-835.

[35]

S. Williams, M. Abrams, C.R. Standbridge, G. Abdulla, E.A. Fox, Removal policies in network caches for World-Wide Web documents, Proceedings of the ACM SIGCOMM 96, 1996.

[36]

A. Wolman, G. Voelker, N. Sharma, N. Cardwell, M. Brown, T. Landray, D. Pinnel, A. Karlin, H. Levy, Organization-based analysis of web-object sharing and caching, Proceedings of the second USENIX Symposium on Internet Technologies and Systems, 1999.

Digital Library

[37]

R.P. Wooster, M. Abrams, Proxy caching that estimates page load delays, Sixth International World Wide Web Conference, 1997.

Cited By

Syed BIndurthi VGupta MShrivastava MVarma V(2019)Inductive Transfer Learning for Detection of Well-Formed Natural Language Search QueriesAdvances in Information Retrieval10.1007/978-3-030-15719-7_6(45-52)Online publication date: 14-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-15719-7_6
Kane ATompa FCamilleri KBonnici A(2017)Small-Term Distribution for Disk-Based SearchProceedings of the 2017 ACM Symposium on Document Engineering10.1145/3103010.3103022(49-58)Online publication date: 31-Aug-2017
https://dl.acm.org/doi/10.1145/3103010.3103022
Kucukyilmaz TCambazoglu BAykanat CBaeza-Yates R(2017)A machine learning approach for result caching in web search enginesInformation Processing and Management: an International Journal10.1016/j.ipm.2017.02.00653:4(834-850)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.ipm.2017.02.006
Show More Cited By

On caching search engine query results

Recommendations

Predictive caching and prefetching of query results in search engines
WWW '03: Proceedings of the 12th international conference on World Wide Web

We study the caching of query result pages in Web search engines. Popular search engines receive millions of queries per day, and efficient policies for caching query results may enable them to lower their response time and reduce their hardware ...
A refreshing perspective of search engine caching
WWW '10: Proceedings of the 19th international conference on World wide web

Commercial Web search engines have to process user queries over huge Web indexes under tight latency constraints. In practice, to achieve low latency, large result caches are employed and a portion of the query traffic is served using previously ...
Caching search engine results over incremental indices
WWW '10: Proceedings of the 19th international conference on World wide web

A Web search engine must update its index periodically to incorporate changes to the Web, and we argue in this work that index updates fundamentally impact the design of search engine result caches. Index updates lead to the problem of cache ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computer Communications

Computer Communications Volume 24, Issue 2

February, 2001

140 pages

ISSN:0140-3664

Issue’s Table of Contents

Copyright © Elsevier Science B.V. © 2001.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 February 2001

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Syed BIndurthi VGupta MShrivastava MVarma V(2019)Inductive Transfer Learning for Detection of Well-Formed Natural Language Search QueriesAdvances in Information Retrieval10.1007/978-3-030-15719-7_6(45-52)Online publication date: 14-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-15719-7_6
Kane ATompa FCamilleri KBonnici A(2017)Small-Term Distribution for Disk-Based SearchProceedings of the 2017 ACM Symposium on Document Engineering10.1145/3103010.3103022(49-58)Online publication date: 31-Aug-2017
https://dl.acm.org/doi/10.1145/3103010.3103022
Kucukyilmaz TCambazoglu BAykanat CBaeza-Yates R(2017)A machine learning approach for result caching in web search enginesInformation Processing and Management: an International Journal10.1016/j.ipm.2017.02.00653:4(834-850)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1016/j.ipm.2017.02.006
Dong XLi RHe HGu XSarem MQiu MLi K(2017)EDSFuture Generation Computer Systems10.1016/j.future.2016.02.01474:C(220-231)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1016/j.future.2016.02.014
Li XQiu TWang NYang XWang BYu G(2017)Refreshment of the shortest path cache with change of single edgeExpert Systems with Applications: An International Journal10.1016/j.eswa.2016.08.01167:C(1-11)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.1016/j.eswa.2016.08.011
Tolosa GFeuerstein EBecchetti LMarchetti-Spaccamela A(2017)Performance improvements for search systems using an integrated cache of lists + intersectionsInformation Retrieval10.1007/s10791-017-9299-520:3(172-198)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10791-017-9299-5
Trinh TWu DHuang J(2017)A New Static Web Caching Mechanism Based on Mutual Dependency Between Result Cache and Posting List CacheWeb Information Systems Engineering – WISE 201710.1007/978-3-319-68786-5_12(148-156)Online publication date: 7-Oct-2017
https://dl.acm.org/doi/10.1007/978-3-319-68786-5_12
Bai XCambazoglu BRussell APerego RSebastiani FAslam JRuthven IZobel J(2016)Improved Caching Techniques for Large-Scale Image Hosting ServicesProceedings of the 39th International ACM SIGIR conference on Research and Development in Information Retrieval10.1145/2911451.2911513(639-648)Online publication date: 7-Jul-2016
https://dl.acm.org/doi/10.1145/2911451.2911513
Tang BYiu MHua K(2016)Exploit Every BitIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2016.251560328:5(1175-1188)Online publication date: 1-May-2016
https://dl.acm.org/doi/10.1109/TKDE.2016.2515603
Figueroa AGómez-Pantoja CHerrera I(2016)Search clicks analysis for discovering temporally anchored questions in community Question AnsweringExpert Systems with Applications: An International Journal10.1016/j.eswa.2015.12.01650:C(89-99)Online publication date: 15-May-2016
https://dl.acm.org/doi/10.1016/j.eswa.2015.12.016
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents