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

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

Documents

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.
Original languageEnglish
Title of host publicationInformation retrieval technology : 11th Asia Information Retrieval Societies Conference, AIRS 2015, Brisbane, QLD, Australia, December 2-4, 2015. Proceedings
EditorsGuido Zuccon, Shlomo Geva, Hideo Joho, Falk Scholer, Aixin Sun, Peng Zhang
Number of pages6
PublisherSpringer
Publication date2015
Pages420-425
ISBN (Print)978-3-319-28939-7
ISBN (Electronic)978-3-319-28940-3
DOIs
Publication statusPublished - 2015
EventAsia Information Retrieval Societies Conference - Brisbane, Australia
Duration: 2 Dec 20154 Dec 2015

Conference

ConferenceAsia Information Retrieval Societies Conference
LandAustralia
ByBrisbane
Periode02/12/201504/12/2015
SeriesLecture notes in computer science
Volume9460
ISSN0302-9743

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 162751793