Fecha: viernes 13 de julio de 2018.
Hora: 10:00.
Lugar: Seminario del Departamento de Informática e Ingeniería de Sistemas
Universal indexes for highly repetitive document collections
Antonio Fariña
The analysis of textual information in a Big Data context is particularly challenging, due to the huge amounts of unstructured data available. Compression techniques can help alleviate this problem. In this talk, I will introduce new techniques for compressing inverted indexes that exploit the existing near-copy regularity, based on run-length, Lempel–Ziv, or grammar compression of the differential inverted lists, instead of the usual practice of gap-encoding them. Indexing highly repetitive collections has become a relevant problem with the emergence of large repositories of versioned documents, among other applications. These collections may reach huge sizes, but are formed mostly of documents that are near-copies of others. Traditional techniques for indexing these collections fail to properly exploit their regularities in order to reduce space. I will show that, in this highly repetitive setting, our compression methods significantly reduce the space obtained with classical techniques, at the price of moderate slowdowns. Moreover, our best methods are universal, that is, they do not need to know the versioning structure of the collection, nor that a clear versioning structure even exists. I will also introduce compressed self-indexes, which represent the text collection plus the index structure in an integrated form, in the comparison. I will show that these techniques can compress much further although they are orders of magnitude slower.
Bio: Antonio Fariña is an Associate Professor at the University of A Coruña (UDC). He is a member of the Laboratorio de Bases de Datos (LBD, http://lbd.udc.es/MainPage.do) and specializes in data structures and compression techniques to handle text documents and unstructured data. Other areas of interest include algorithms, searching in metric spaces, and Geographic Information Systems. For more information, please visit his web page at http://lbd.udc.es/ShowResearcherInformation.do?id=8.
Acknowledgements: TIN2016-78011-C4-3-R "Datos 4.0: Retos y Soluciones - UZ", COS2MOS (http://cos2mos.unizar.es) group.
