The impact of using combinatorial optimisation for static caching of posting lists

TY - GEN

T1 - The impact of using combinatorial optimisation for static caching of posting lists

AU - Petersen, Casper

AU - Simonsen, Jakob Grue

AU - Lioma, Christina

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-319-28940-3_36

DO - 10.1007/978-3-319-28940-3_36

M3 - Article in proceedings

SN - 978-3-319-28939-7

T3 - Lecture notes in computer science

SP - 420

EP - 425

BT - Information retrieval technology

A2 - Zuccon, Guido

A2 - Geva, Shlomo

A2 - Joho, Hideo

A2 - Scholer, Falk

A2 - Sun, Aixin

A2 - Zhang, Peng

PB - Springer

T2 - Asia Information Retrieval Societies Conference

Y2 - 2 December 2015 through 4 December 2015

ER -