Partitioned Elias-Fano indexes (Contributo in atti di convegno)

Type
Label
  • Partitioned Elias-Fano indexes (Contributo in atti di convegno) (literal)
Anno
  • 2014-01-01T00:00:00+01:00 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi
  • 10.1145/2600428.2609615 (literal)
Alternative label
  • Ottaviano G., Venturini R. (2014)
    Partitioned Elias-Fano indexes
    in SIGIR 2014 - 37th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Gold Coast, QLD, Australia, 6-11 July 2014
    (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori
  • Ottaviano G., Venturini R. (literal)
Pagina inizio
  • 273 (literal)
Pagina fine
  • 282 (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url
  • http://dl.acm.org/citation.cfm?doid=2600428.2609615 (literal)
Note
  • Scopu (literal)
  • PuMa (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni
  • Department of Computer Science, University of Pisa, Italy - CNR-ISTI, Pisa, Italy; CNR-ISTI, Pisa, Italy; (literal)
Titolo
  • Partitioned Elias-Fano indexes (literal)
Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#isbn
  • 978-1-4503-2257-7 (literal)
Abstract
  • The Elias-Fano representation of monotone sequences has been recently applied to the compression of inverted indexes, showing excellent query performance thanks to its efficient random access and search operations. While its space occupancy is competitive with some state-of-the-art methods such as -??-Golomb codes and PForDelta, it fails to exploit the local clustering that inverted lists usually exhibit, namely the presence of long subsequences of close identifiers. In this paper we describe a new representation based on partitioning the list into chunks and encoding both the chunks and their endpoints with Elias-Fano, hence forming a two-level data structure. This partitioning enables the encoding to better adapt to the local statistics of the chunk, thus exploiting clustering and improving compression. We present two partition strategies, respectively with fixed and variable-length chunks. For the latter case we introduce a linear-time optimization algorithm which identifies the minimum-space partition up to an arbitrarily small approximation factor. We show that our partitioned Elias-Fano indexes offer significantly better compression than plain Elias-Fano, while preserving their query time eficiency. Furthermore, compared with other state-of-the-art compressed encodings, our indexes exhibit the best compression ratio/query time trade-off. Copyright 2014 ACM. (literal)
Prodotto di
Autore CNR
Insieme di parole chiave

Incoming links:


Prodotto
Autore CNR di
Insieme di parole chiave di
data.CNR.it