Improved techniques for result caching in web search engines Export

@inproceedings{citeulike:4731368, abstract = {Query processing is a major cost factor in operating large web search engines. In this paper, we study query result caching, one of the main techniques used to optimize query processing performance. Our first contribution is a study of result caching as a weighted caching problem. Most previous work has focused on optimizing cache hit ratios, but given that processing costs of queries can vary very significantly we argue that total cost savings also need to be considered. We describe and evaluate several algorithms for weighted result caching, and study the impact of Zipf-based query distributions on result caching. Our second and main contribution is a new set of feature-based cache eviction policies that achieve significant improvements over all previous methods, substantially narrowing the existing performance gap to the theoretically optimal (clairvoyant) method. Finally, using the same approach, we also obtain performance gains for the related problem of inverted list caching.}, address = {New York, NY, USA}, author = {Gan, Qingqing and Suel, Torsten}, booktitle = {WWW '09: Proceedings of the 18th international conference on World wide web}, citeulike-article-id = {4731368}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1526709.1526768}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1526709.1526768}, doi = {10.1145/1526709.1526768}, isbn = {978-1-60558-487-4}, keywords = {cache, search, www}, location = {Madrid, Spain}, pages = {431--440}, posted-at = {2009-06-03 11:29:26}, priority = {2}, publisher = {ACM}, title = {Improved techniques for result caching in web search engines}, url = {http://dx.doi.org/10.1145/1526709.1526768}, year = {2009} }

TY - CONF ID - citeulike:4731368 L3 - citeulike-article-id:4731368 N2 - Query processing is a major cost factor in operating large web search engines. In this paper, we study query result caching, one of the main techniques used to optimize query processing performance. Our first contribution is a study of result caching as a weighted caching problem. Most previous work has focused on optimizing cache hit ratios, but given that processing costs of queries can vary very significantly we argue that total cost savings also need to be considered. We describe and evaluate several algorithms for weighted result caching, and study the impact of Zipf-based query distributions on result caching. Our second and main contribution is a new set of feature-based cache eviction policies that achieve significant improvements over all previous methods, substantially narrowing the existing performance gap to the theoretically optimal (clairvoyant) method. Finally, using the same approach, we also obtain performance gains for the related problem of inverted list caching. CY - Madrid, Spain SN - 978-1-60558-487-4 AD - New York, NY, USA EP - 440 TI - Improved techniques for result caching in web search engines PB - ACM T2 - WWW '09: Proceedings of the 18th international conference on World wide web SP - 431 KW - cache KW - search KW - www AU - Gan, Qingqing AU - Suel, Torsten PY - 2009/// UR - http://dx.doi.org/10.1145/1526709.1526768 ER -