PUMA
Istituto di Scienza e Tecnologie dell'Informazione     
Hsu P., Ottaviano G. Space-efficient data structures for top-k completion. In: WWW 2013 - 22st International Conference on World Wide Web (Rio De Janeiro, Brazil, 13-17 May 2013). Proceedings, pp. 583 - 594. ACM, 2013.
 
 
Abstract
(English)
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 be- ginning with a given prefix, that have the highest scores according to some static ranking. In this paper, we focus on the case where the string set is so large that compres- sion is needed to fit 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. We present three different trie-based data structures to address this problem, each one with different space/time/ complexity trade-offs. Experiments on large-scale datasets show that it is possible to compress the string sets, including the scores, down to spaces competitive with the gzip'ed data, while supporting efficient retrieval of completions at about a microsecond per completion.
URL: http://dl.acm.org/citation.cfm?id=2488440
Subject Top-k completion
Scored string sets
Tries
Compression
H.3.3 Information Search and Retrieval
E.1 Data Structures. Trees


Icona documento 1) Download Document PDF
Icona documento 2) Download Document PDF


Icona documento Open access Icona documento Restricted Icona documento Private

 


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional