Cost-Aware Strategies for Query Result Caching in Web Search Engines

Download

index.pdf

Date

2011-05-01

Author

Ozcan, Rifat
Altıngövde, İsmail Sengör
Ulusoy, Ozgor

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

227
views

0
downloads

Search engines and large-scale IR systems need to cache query results for efficiency and scalability purposes. Static and dynamic caching techniques (as well as their combinations) are employed to effectively cache query results. In this study, we propose cost-aware strategies for static and dynamic caching setups. Our research is motivated by two key observations: (i) query processing costs may significantly vary among different queries, and (ii) the processing cost of a query is not proportional to its popularity (i.e., frequency in the previous logs). The first observation implies that cache misses have different, that is, nonuniform, costs in this context. The latter observation implies that typical caching policies, solely based on query popularity, can not always minimize the total cost. Therefore, we propose to explicitly incorporate the query costs into the caching policies. Simulation results using two large Web crawl datasets and a real query log reveal that the proposed approach improves overall system performance in terms of the average query execution time.

Subject Keywords

Computer Networks and Communications

URI

https://hdl.handle.net/11511/41560

Journal

ACM TRANSACTIONS ON THE WEB

DOI

https://doi.org/10.1145/1961659.1961663

Collections

Department of Computer Engineering, Article

Suggestions

OpenMETU
Core

Second Chance: A Hybrid Approach for Dynamic Result Caching and Prefetching in Search Engines Ozcan, Rifat; Altıngövde, İsmail Sengör; Barla Cambazoglu, B.; ULUSOY, ÖZGÜR (Association for Computing Machinery (ACM), 2013-12-01) Web search engines are known to cache the results of previously issued queries. The stored results typically contain the document summaries and some data that is used to construct the final search result page returned to the user. An alternative strategy is to store in the cache only the result document IDs, which take much less space, allowing results of more queries to be cached. These two strategies lead to an interesting trade-off between the hit rate and the average query response latency. In this work...
Cache-Based Query Processing for Search Engines Cambazoglu, B. Barla; Altıngövde, İsmail Sengör; Ozcan, Rifat; Ulusoy, Ozgur (Association for Computing Machinery (ACM), 2012-11-01) In practice, a search engine may fail to serve a query due to various reasons such as hardware/network failures, excessive query load, lack of matching documents, or service contract limitations (e.g., the query rate limits for third-party users of a search service). In this kind of scenarios, where the backend search system is unable to generate answers to queries, approximate answers can be generated by exploiting the previously computed query results available in the result cache of the search engine. In...
Exploiting Navigational Queries for Result Presentation and Caching in Web Search Engines Ozcan, Rifat; Altıngövde, İsmail Sengör; Ulusoy, Ozgur (Wiley, 2011-04-01) Caching of query results is an important mechanism for efficiency and scalability of web search engines. Query results are cached and presented in terms of pages, which typically include 10 results each. In navigational queries, users seek a particular website, which would be typically listed at the top ranks (maybe, first or second) by the search engine, if found. For this type of query, caching and presenting results in the 10-per-page manner may waste cache space and network bandwidth. In this article, w...
A Cost-Aware Strategy for Query Result Caching in Web Search Engines Altıngövde, İsmail Sengör; Ulusoy, Oezguer (2009-01-01) Search engines and large scale IR systems need to cache query results for efficiency and scalability purposes. In this study, we propose to explicitly incorporate the query costs in the static caching policy. To this end, a query’s cost is represented by its execution time, which involves CPU time to decompress the postings and compute the query-document similarities to obtain the final top-N answers. Simulation results using a large Web crawl data and a real query log reveal that the proposed strategy impr...
Energy-aware routing algorithms for wireless ad hoc networks with heterogeneous power supplies Vazifehdan, Javad; Prasad, R. Venkatesha; Onur, Ertan; Niemegeers, Ignas (Elsevier BV, 2011-10-27) Although many energy-aware routing schemes have been proposed for wireless ad hoc networks, they are not optimized for networks with heterogeneous power supplies, where nodes may run on battery or be connected to the mains (grid network). In this paper, we propose several energy-aware routing algorithms for such ad hoc networks. The proposed algorithms feature directing the traffic load dynamically towards mains-powered devices keeping the hop count of selected routes minimal. We unify these algorithms into...

Citation Formats

R. Ozcan, İ. S. Altıngövde, and O. Ulusoy, “Cost-Aware Strategies for Query Result Caching in Web Search Engines,” ACM TRANSACTIONS ON THE WEB, pp. 0–0, 2011, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/41560.