Autor:
Navarro, Gonzalo

Foto de perfil
E-mails conocidos
Universidad de Chile
gnavarro@dcc.uchile.cl
Fecha de nacimiento
Proyectos de investigación
Unidades organizativas
Puesto de trabajo
Apellidos
Navarro
Nombre de pila
Gonzalo
Nombre
Nombres alternativos
Afiliaciones conocidas
University of Chile, Chile
Universidad de Chile, Chile
gnavarro@dcc.uchile.cl
University of Chile
Páginas web conocidas
Página completa del ítem
Notificar un error en este autor

Filtros

20171
Restablecer filtros

Ajustes

Resultados de la búsqueda

Mostrando 1 - 1 de 1
  • Miniatura
    Artículo
    Universal indexes for highly repetitive document collections
    Claude, Francisco; Fariña, Antonio; Martínez-Prieto, Miguel A.; Navarro, Gonzalo. Actas de las XXII Jornadas de Ingeniería del Software y Bases de Datos (JISBD 2017), 2017-07-19.
    Abstract ======== 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. We introduce new techniques for compressing inverted indexes that exploit this near-copy regularity. They are based on run-length, Lempel-Ziv, or grammar compression of the differential inverted lists, instead of the usual practice of gap-encoding them. We 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. We also introduce compressed self-indexes in the comparison. These are designed for general strings (not only natural language texts) and represent the text collection plus the index structure (not an inverted index) in integrated form. We show that these techniques can compress much further, using a small fraction of the space required by our new inverted indexes. Yet, they are orders of magnitude slower. Publication Details =================== Francisco Claude, Antonio Fariña, Miguel A. Martínez-Prieto, Gonzalo Navarro. Universal indexes for highly repetitive document collections Information Systems, 61, pp. 1-23, 2016, DOI: http://dx.doi.org/10.1016/j.is.2016.04.002 Citations Google Scholar: 3 (2 self-citations)