Sorry, you need to enable JavaScript to visit this website.

compressed data structures

Compressing and Randomly Accessing Sequences


In this paper we consider the problem of storing sequences of symbols in
a compressed format, while supporting random access to the symbols without
decompression. Although this is a well-studied problem when the data is
textual, the kind of sequences we look at are not textual, and we argue
that traditional compression methods used in the text algorithms community
(such as compressors targeting $k$-th order empirical entropy) do not
perform as well on these sequential data, and simpler methods such

Paper Details

Authors:
Laith Ali Abdulsahib, Diego Arroyuelo, Rajeev Raman
Submitted On:
21 April 2020 - 10:31am
Short Link:
Type:
Event:
Presenter's Name:
Paper Code:
Session:
Document Year:
Cite

Document Files

main.pdf

(37)

Keywords

Additional Categories

Subscribe

[1] Laith Ali Abdulsahib, Diego Arroyuelo, Rajeev Raman, "Compressing and Randomly Accessing Sequences", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5109. Accessed: Jul. 13, 2020.
@article{5109-20,
url = {http://sigport.org/5109},
author = {Laith Ali Abdulsahib; Diego Arroyuelo; Rajeev Raman },
publisher = {IEEE SigPort},
title = {Compressing and Randomly Accessing Sequences},
year = {2020} }
TY - EJOUR
T1 - Compressing and Randomly Accessing Sequences
AU - Laith Ali Abdulsahib; Diego Arroyuelo; Rajeev Raman
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5109
ER -
Laith Ali Abdulsahib, Diego Arroyuelo, Rajeev Raman. (2020). Compressing and Randomly Accessing Sequences. IEEE SigPort. http://sigport.org/5109
Laith Ali Abdulsahib, Diego Arroyuelo, Rajeev Raman, 2020. Compressing and Randomly Accessing Sequences. Available at: http://sigport.org/5109.
Laith Ali Abdulsahib, Diego Arroyuelo, Rajeev Raman. (2020). "Compressing and Randomly Accessing Sequences." Web.
1. Laith Ali Abdulsahib, Diego Arroyuelo, Rajeev Raman. Compressing and Randomly Accessing Sequences [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5109

Compact Representation of Graphs with Small Bandwidth and Treedepth


We consider the problem of compact representation of graphs with small bandwidth as well as graphs with small treedepth. These parameters capture structural properties of graphs that come in useful in certain applications.

Paper Details

Authors:
Submitted On:
22 April 2020 - 1:50pm
Short Link:
Type:
Event:
Presenter's Name:
Paper Code:
Session:
Document Year:
Cite

Document Files

DCC-2020-Paper-204.pdf

(39)

Keywords

Additional Categories

Subscribe

[1] , "Compact Representation of Graphs with Small Bandwidth and Treedepth", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5089. Accessed: Jul. 13, 2020.
@article{5089-20,
url = {http://sigport.org/5089},
author = { },
publisher = {IEEE SigPort},
title = {Compact Representation of Graphs with Small Bandwidth and Treedepth},
year = {2020} }
TY - EJOUR
T1 - Compact Representation of Graphs with Small Bandwidth and Treedepth
AU -
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5089
ER -
. (2020). Compact Representation of Graphs with Small Bandwidth and Treedepth. IEEE SigPort. http://sigport.org/5089
, 2020. Compact Representation of Graphs with Small Bandwidth and Treedepth. Available at: http://sigport.org/5089.
. (2020). "Compact Representation of Graphs with Small Bandwidth and Treedepth." Web.
1. . Compact Representation of Graphs with Small Bandwidth and Treedepth [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5089

c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches


Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ, a keyword dictionary is a data structure built on K that provides locate, prefix search, and update operations on K. Under the assumption that α = w / lg σ characters fit into a single machine word w, we propose a keyword dictionary that represents K in n lg σ + O(k lg n) bits of space, supporting all operations in O(m / α + lg α) expected time on an input string of length m in the word RAM model.

Paper Details

Authors:
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda
Submitted On:
31 March 2020 - 1:42am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

Video Presentation

Slides

(51)

Keywords

Additional Categories

Subscribe

[1] Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, "c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5049. Accessed: Jul. 13, 2020.
@article{5049-20,
url = {http://sigport.org/5049},
author = {Kazuya Tsuruta; Dominik Köppl; Shunsuke Kanda; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda },
publisher = {IEEE SigPort},
title = {c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches},
year = {2020} }
TY - EJOUR
T1 - c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches
AU - Kazuya Tsuruta; Dominik Köppl; Shunsuke Kanda; Yuto Nakashima; Shunsuke Inenaga; Hideo Bannai; Masayuki Takeda
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5049
ER -
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. (2020). c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches. IEEE SigPort. http://sigport.org/5049
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, 2020. c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches. Available at: http://sigport.org/5049.
Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. (2020). "c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches." Web.
1. Kazuya Tsuruta, Dominik Köppl, Shunsuke Kanda, Yuto Nakashima, Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda. c-trie++: A Dynamic Trie Tailored for Fast Prefix Searches [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5049

Revisiting compact RDF stores based on k2-trees

Paper Details

Authors:
Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña
Submitted On:
26 March 2020 - 7:19am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

base-newlogo.pdf

(25)

Keywords

Additional Categories

Subscribe

[1] Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña, "Revisiting compact RDF stores based on k2-trees", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5014. Accessed: Jul. 13, 2020.
@article{5014-20,
url = {http://sigport.org/5014},
author = {Nieves R. Brisaboa; Ana Cerdeira-Pena; Guillermo de Bernardo; Antonio Fariña },
publisher = {IEEE SigPort},
title = {Revisiting compact RDF stores based on k2-trees},
year = {2020} }
TY - EJOUR
T1 - Revisiting compact RDF stores based on k2-trees
AU - Nieves R. Brisaboa; Ana Cerdeira-Pena; Guillermo de Bernardo; Antonio Fariña
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5014
ER -
Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña. (2020). Revisiting compact RDF stores based on k2-trees. IEEE SigPort. http://sigport.org/5014
Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña, 2020. Revisiting compact RDF stores based on k2-trees. Available at: http://sigport.org/5014.
Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña. (2020). "Revisiting compact RDF stores based on k2-trees." Web.
1. Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, Antonio Fariña. Revisiting compact RDF stores based on k2-trees [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5014