Show simple item record

Authordc.contributor.authorArroyuelo, Diego 
Authordc.contributor.authorOyarzún, Mauricio 
Authordc.contributor.authorGonzález, Senén 
Authordc.contributor.authorSepúlveda, Víctor 
Admission datedc.date.accessioned2019-05-31T15:20:02Z
Available datedc.date.available2019-05-31T15:20:02Z
Publication datedc.date.issued2018
Cita de ítemdc.identifier.citationInformation Processing and Management, Volumen 54, Issue 6, 2018, Pages 1308-1324
Identifierdc.identifier.issn03064573
Identifierdc.identifier.other10.1016/j.ipm.2018.05.007
Identifierdc.identifier.urihttps://repositorio.uchile.cl/handle/2250/169432
Abstractdc.description.abstractText search engines are a fundamental tool nowadays. Their efficiency relies on a popular and simple data structure: inverted indexes. They store an inverted list per term of the vocabulary. The inverted list of a given term stores, among other things, the document identifiers (docIDs) of the documents that contain the term. Currently, inverted indexes can be stored efficiently using integer compression schemes. Previous research also studied how an optimized document ordering can be used to assign docIDs to the document database. This yields important improvements in index compression and query processing time. In this paper we show that using a hybrid compression approach on the inverted lists is more effective in this scenario, with two main contributions: • First, we introduce a document reordering approach that aims at generating runs of consecutive docIDs in a properly-selected subset of inverted lists of the index. • Second, we introduce hybrid compression approaches that combine gap and run-length encodings within inverted lists, in order to take advantage not only from small gaps, but also from long runs of consecutive docIDs generated by our document reordering approach. Our experimental results indicate a reduction of about 10%–30% in the space usage of the whole index (just regarding docIDs), compared with the most efficient state-of-the-art results. Also, decompression speed is up to 1.22 times faster if the runs of consecutive docIDs must be explicitly decompressed, and up to 4.58 times faster if implicit decompression of these runs is allowed (e.g., representing the runs as intervals in the output). Finally, we also improve the query processing time of AND queries (by up to 12%), WAND queries (by up to 23%), and full (non-ranked) OR queries (by up to 86%), outperforming the best existing approaches.
Lenguagedc.language.isoen
Publisherdc.publisherElsevier Ltd
Type of licensedc.rightsAttribution-NonCommercial-NoDerivs 3.0 Chile
Link to Licensedc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/cl/
Sourcedc.sourceInformation Processing and Management
Keywordsdc.subjectIndex compression for information retrieval
Keywordsdc.subjectReordered document collections
Títulodc.titleHybrid compression of inverted lists for reordered document collections
Document typedc.typeArtículo de revista
Catalogueruchile.catalogadorjmm
Indexationuchile.indexArtículo de publicación SCOPUS
uchile.cosechauchile.cosechaSI


Files in this item

Icon

This item appears in the following Collection(s)

Show simple item record

Attribution-NonCommercial-NoDerivs 3.0 Chile
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile