Space-Efficient Data Structures for Top-k Completion
Virtually every modern search application, either desktop, web, or mobile, features some kind of query auto-completion. In its basic form, the problem consists in retrieving from a string set a small number of completions, i.e. strings beginning with a given pre x, that have the highest scores according to some static ranking. In this paper, the authors focus on the case where the string set is so large that compression is needed to t the data structure in memory. This is a compelling case for web search engines and social networks, where it is necessary to index hundreds of millions of distinct queries to guarantee a reasonable coverage; and for mobile devices, where the amount of memory is limited.