We revisit the fundamental problem of compressing an integer dictionary that supports efficient rank and select operations by exploiting simultaneously two kinds of regularities arising in real data: repetitiveness and approximate linearity. We attack this problem by proposing two novel compressed indexing approaches that extend the classic Lempel-Ziv compression scheme and the more recent block tree data structure with new algorithms and data structures that allow them to also capture regularities in terms of the approximate linearity in the data. Finally, we corroborate these theoretical results with a wide set of experiments on real and synthetic datasets, which allow us to show that our approaches achieve new interesting space-time trade-offs that characterise them as more robust in most practical scenarios compared to the known data structures that exploit only one of the two regularities.

Compressing and Querying Integer Dictionaries Under Linearities and Repetitions

Ferragina P.;
2022-01-01

Abstract

We revisit the fundamental problem of compressing an integer dictionary that supports efficient rank and select operations by exploiting simultaneously two kinds of regularities arising in real data: repetitiveness and approximate linearity. We attack this problem by proposing two novel compressed indexing approaches that extend the classic Lempel-Ziv compression scheme and the more recent block tree data structure with new algorithms and data structures that allow them to also capture regularities in terms of the approximate linearity in the data. Finally, we corroborate these theoretical results with a wide set of experiments on real and synthetic datasets, which allow us to show that our approaches achieve new interesting space-time trade-offs that characterise them as more robust in most practical scenarios compared to the known data structures that exploit only one of the two regularities.
2022
File in questo prodotto:
File Dimensione Formato  
Compressing_and_Querying_Integer_Dictionaries_Under_Linearities_and_Repetitions.pdf

non disponibili

Licenza: Copyright dell'editore
Dimensione 5.17 MB
Formato Adobe PDF
5.17 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11382/566786
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
social impact