The impact of using combinatorial optimisation for static caching of posting lists
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- The Impact of using Combinatorial Optimisation for Static Caching of Posting Lists
Accepteret manuskript, 303 KB, PDF-dokument
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 and 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 nd optimal solutions. Using simulated query logs we nd 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.
Originalsprog | Engelsk |
---|---|
Titel | Information retrieval technology : 11th Asia Information Retrieval Societies Conference, AIRS 2015, Brisbane, QLD, Australia, December 2-4, 2015. Proceedings |
Redaktører | Guido Zuccon, Shlomo Geva, Hideo Joho, Falk Scholer, Aixin Sun, Peng Zhang |
Antal sider | 6 |
Forlag | Springer |
Publikationsdato | 2015 |
Sider | 420-425 |
ISBN (Trykt) | 978-3-319-28939-7 |
ISBN (Elektronisk) | 978-3-319-28940-3 |
DOI | |
Status | Udgivet - 2015 |
Begivenhed | Asia Information Retrieval Societies Conference - Brisbane, Australien Varighed: 2 dec. 2015 → 4 dec. 2015 |
Konference
Konference | Asia Information Retrieval Societies Conference |
---|---|
Land | Australien |
By | Brisbane |
Periode | 02/12/2015 → 04/12/2015 |
Navn | Lecture notes in computer science |
---|---|
Vol/bind | 9460 |
ISSN | 0302-9743 |
Antal downloads er baseret på statistik fra Google Scholar og www.ku.dk
Ingen data tilgængelig
ID: 162751793