Compressing and Querying Integer Dictionaries Under Linearities and Repetitions
We revisit the fundamental problem of compressing an integer dictionary that supports efficient <inline-formula> <tex-math notation="LaTeX">${\mathsf {rank}}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\maths...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2022-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9945936/ |
| _version_ | 1828098834771738624 |
|---|---|
| author | Paolo Ferragina Giovanni Manzini Giorgio Vinciguerra |
| author_facet | Paolo Ferragina Giovanni Manzini Giorgio Vinciguerra |
| author_sort | Paolo Ferragina |
| collection | DOAJ |
| description | We revisit the fundamental problem of compressing an integer dictionary that supports efficient <inline-formula> <tex-math notation="LaTeX">${\mathsf {rank}}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {select}}$ </tex-math></inline-formula> 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. |
| first_indexed | 2024-04-11T08:08:09Z |
| format | Article |
| id | doaj.art-7b37a85fe5084574834e9a5cb4e3d59b |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-11T08:08:09Z |
| publishDate | 2022-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-7b37a85fe5084574834e9a5cb4e3d59b2022-12-22T04:35:27ZengIEEEIEEE Access2169-35362022-01-011011883111884810.1109/ACCESS.2022.32215209945936Compressing and Querying Integer Dictionaries Under Linearities and RepetitionsPaolo Ferragina0https://orcid.org/0000-0003-1353-360XGiovanni Manzini1https://orcid.org/0000-0002-5047-0196Giorgio Vinciguerra2https://orcid.org/0000-0003-0328-7791Department of Computer Science, University of Pisa, Pisa, ItalyDepartment of Computer Science, University of Pisa, Pisa, ItalyDepartment of Computer Science, University of Pisa, Pisa, ItalyWe revisit the fundamental problem of compressing an integer dictionary that supports efficient <inline-formula> <tex-math notation="LaTeX">${\mathsf {rank}}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">${\mathsf {select}}$ </tex-math></inline-formula> 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.https://ieeexplore.ieee.org/document/9945936/Compressed data structuresdata compressionentropy |
| spellingShingle | Paolo Ferragina Giovanni Manzini Giorgio Vinciguerra Compressing and Querying Integer Dictionaries Under Linearities and Repetitions IEEE Access Compressed data structures data compression entropy |
| title | Compressing and Querying Integer Dictionaries Under Linearities and Repetitions |
| title_full | Compressing and Querying Integer Dictionaries Under Linearities and Repetitions |
| title_fullStr | Compressing and Querying Integer Dictionaries Under Linearities and Repetitions |
| title_full_unstemmed | Compressing and Querying Integer Dictionaries Under Linearities and Repetitions |
| title_short | Compressing and Querying Integer Dictionaries Under Linearities and Repetitions |
| title_sort | compressing and querying integer dictionaries under linearities and repetitions |
| topic | Compressed data structures data compression entropy |
| url | https://ieeexplore.ieee.org/document/9945936/ |
| work_keys_str_mv | AT paoloferragina compressingandqueryingintegerdictionariesunderlinearitiesandrepetitions AT giovannimanzini compressingandqueryingintegerdictionariesunderlinearitiesandrepetitions AT giorgiovinciguerra compressingandqueryingintegerdictionariesunderlinearitiesandrepetitions |