Abstract
Caching posting lists can reduce the amount of disk I/O required to evaluate a query. Current methods use optimisation procedures for maximising the cache hit ratio. A recent method selects posting lists for static caching in a greedy manner and obtains higher hit rates than standard cache eviction policies such as LRU and LFU. However, a greedy method does not formally guarantee an optimal solution. We investigate whether the use of methods guaranteed, in theory, to find an approximately optimal solution would yield higher hit rates. Thus, we cast the selection of posting lists for caching as an integer linear programming problem and perform a series of experiments using heuristics from combinatorial optimisation (CCO) to find optimal solutions. Using simulated query logs we find that CCO yields comparable results to a greedy baseline using cache sizes between 200 and 1000 MB, with modest improvements for queries of length two to three.
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
Similar content being viewed by others
References
Azzopardi, L., de Rijke, M.: Automatic construction of known-item finding test beds. In: SIGIR, pp. 603–604 (2006)
Azzopardi, L., de Rijke, M., Balog, K.: Building simulated queries for known-item topics: an analysis using six european languages. In: SIGIR, pp. 455–462 (2007)
Baeza-Yates, R., Gionis, A., Junqueira, F., Murdock, V., Plachouras, V., Silvestri, F.: The impact of caching on search engines. In: SIGIR, pp. 183–190. ACM (2007)
Baeza-Yates, R., Gionis, A., Junqueira, F.P., Murdock, V., Plachouras, V., Silvestri, F.: Design trade-offs for search engine caching. TWEB 2(4), 20 (2008)
Baeza-Yates, R., Saint-Jean, F.: A three level search engine index based in query log distribution. In: Nascimento, M.A., de Moura, E.S., Oliveira, A.L. (eds.) SPIRE 2003. LNCS, vol. 2857, pp. 56–65. Springer, Heidelberg (2003)
Broder, A.Z., Carmel, D., Herscovici, M., Soffer, A., Zien, J.: Efficient query evaluation using a two-level retrieval process. In: IKM, pp. 426–434. ACM (2003)
Thomas, H.C., Charles, E.L., Ronald, L.R., Clifford, S.: Introduction to Algorithms. MIT Press, Cambridge (2001)
Dantzig, G.B.: Discrete-variable extremum problems. Oper. Res. 5(2), 266–288 (1957)
Grotschel, M., Lovász, L.: Combinatorial optimization. Handb. Comb. 2, 1541–1597 (1995)
Liu, Z., Nain, P., Niclausse, N., Towsley, D.: Static caching of web servers. In: PWEI, pp. 179–190. ISOP (1997)
Long, X., Suel, T.: Three-level caching for efficient query processing in large web search engines. WWW 9(4), 369–395 (2006)
Papadakis, M., Tzitzikas, Y.: Answering keyword queries through cached subqueries in best match retrieval models. In: JIIS, pp. 1–40 (2014)
Saraiva, P.C., Silva de Moura, E., Ziviani, N., Meira, W., Fonseca, R., Riberio-Neto, B.: Rank-preserving two-level caching for scalable search engines. In: SIGIR, pp. 51–58. ACM (2001)
Tolosa, G., Becchetti, L., Feuerstein, E., Marchetti-Spaccamela, A.: Performance improvements for search systems using an integrated cache of lists+intersections. In: Moura, E., Crochemore, M. (eds.) SPIRE 2014. LNCS, vol. 8799, pp. 227–235. Springer, Heidelberg (2014)
Zhang, J., Long, X., Suel,T.: Performance of compressed inverted list caching in search engines. In: WWW, pp. 387–396. ACM (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Petersen, C., Simonsen, J.G., Lioma, C. (2015). The Impact of Using Combinatorial Optimisation for Static Caching of Posting Lists. In: Zuccon, G., Geva, S., Joho, H., Scholer, F., Sun, A., Zhang, P. (eds) Information Retrieval Technology. AIRS 2015. Lecture Notes in Computer Science(), vol 9460. Springer, Cham. https://doi.org/10.1007/978-3-319-28940-3_36
Download citation
DOI: https://doi.org/10.1007/978-3-319-28940-3_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-28939-7
Online ISBN: 978-3-319-28940-3
eBook Packages: Computer ScienceComputer Science (R0)