Istituto di Scienza e Tecnologie dell'Informazione     
Gog S., Venturini R. Succinct data structures in information retrieval: theory and practice. In: SIGIR'16 - 39th International ACM SIGIR conference on Research and Development in Information Retrieval (Pisa, Italy, 17-21 July 2016). Proceedings, pp. 1231 - 1233. ACM, 2016.
Succinct data structures are used today in many information retrieval applications, e.g., posting lists representation, language model representation, indexing (social) graphs, query auto-completion, document retrieval and indexing dictionary of strings, just to mention the most recent ones. These new kind of data structures mimic the operations of their classical counterparts within a comparable time complexity but require much less space. With the availability of several libraries for basic succinct structures - like SDSL, Succinct, Facebook?s Folly, and Sux - it is relatively easy to directly profit from advances in this field. In this tutorial we will introduce this field of research by presenting the most important succinct data structures to represent set of integers, set of points, trees, graphs and strings together with their most important applications to Information Retrieval problems. The introduction of the succinct data structures will be sustained with a practical session with programming handouts to solve. This will allow the attendees to directly experiment with implementations of these solutions on real datasets and understand the potential benefits they can bring on their own projects.
URL: http://dl.acm.org/citation.cfm?id=2914802
DOI: 10.1145/2911451.2914802
Subject Indexing
H.3.3 INFORMATION STORAGE AND RETRIEVAL. Information Search and Retrieval

Icona documento 1) 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