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

Emerging: Big Data

Adaptive Stream-based Entropy Coding

Shinichi Yamagiwa

Fast data streams are applied by various applications such as multimedia, communication and sensory devices. The amount of data is getting larger and the transfer speed is also getting higher. To address this kind of fast applications, a high performance stream-based data compression mechanism is demanded.

Paper Details

Authors:
Shinichi Yamagiwa
Eisaku Hayakawa, Koichi Marumo
Submitted On:
24 April 2020 - 2:53pm
Short Link:
Type:
Event:
Session:

Document Files

DCC2020_poster_submitted.pdf

(56)

Keywords

Subscribe

Send Author a Private Message
[1] Eisaku Hayakawa, Koichi Marumo, "Adaptive Stream-based Entropy Coding", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5107. Accessed: Aug. 07, 2020.
@article{5107-20,
url = {http://sigport.org/5107},
author = {Eisaku Hayakawa; Koichi Marumo },
publisher = {IEEE SigPort},
title = {Adaptive Stream-based Entropy Coding},
year = {2020} }
TY - EJOUR
T1 - Adaptive Stream-based Entropy Coding
AU - Eisaku Hayakawa; Koichi Marumo
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5107
ER -
Eisaku Hayakawa, Koichi Marumo. (2020). Adaptive Stream-based Entropy Coding. IEEE SigPort. http://sigport.org/5107
Eisaku Hayakawa, Koichi Marumo, 2020. Adaptive Stream-based Entropy Coding. Available at: http://sigport.org/5107.
Eisaku Hayakawa, Koichi Marumo. (2020). "Adaptive Stream-based Entropy Coding." Web.
1. Eisaku Hayakawa, Koichi Marumo. Adaptive Stream-based Entropy Coding [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5107

Compact Representation of Graphs with Small Bandwidth and Treedepth

Shahin Kamali

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:
Shahin Kamali
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

(48)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] , "Compact Representation of Graphs with Small Bandwidth and Treedepth", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5089. Accessed: Aug. 07, 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

Compressed Quadratization of Higher Order Binary Optimization Problems

Avradip Mandal

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space $\ising$ or in Boolean space $\bool$. Many naturally occurring problem instances are higher-order in nature.

Paper Details

Authors:
Avradip Mandal
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima
Submitted On:
31 March 2020 - 4:52pm
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

Hobo2QuboDCC-poster.pdf

(43)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima, "Compressed Quadratization of Higher Order Binary Optimization Problems", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5087. Accessed: Aug. 07, 2020.
@article{5087-20,
url = {http://sigport.org/5087},
author = {Avradip Mandal; Arnab Roy; Sarvagya Upadhyay; Hayato Ushijima },
publisher = {IEEE SigPort},
title = {Compressed Quadratization of Higher Order Binary Optimization Problems},
year = {2020} }
TY - EJOUR
T1 - Compressed Quadratization of Higher Order Binary Optimization Problems
AU - Avradip Mandal; Arnab Roy; Sarvagya Upadhyay; Hayato Ushijima
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5087
ER -
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima. (2020). Compressed Quadratization of Higher Order Binary Optimization Problems. IEEE SigPort. http://sigport.org/5087
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima, 2020. Compressed Quadratization of Higher Order Binary Optimization Problems. Available at: http://sigport.org/5087.
Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima. (2020). "Compressed Quadratization of Higher Order Binary Optimization Problems." Web.
1. Avradip Mandal, Arnab Roy, Sarvagya Upadhyay, Hayato Ushijima. Compressed Quadratization of Higher Order Binary Optimization Problems [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5087

Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach

Faisal Abu Khzam
Amer Haj Ahmad

Paper Details

Authors:
Faisal Abu Khzam
Amer Haj Ahmad
Faisal N. Abu-Khzam, Amer Haj Ahmad, Rana H. Mouawi
Submitted On:
30 March 2020 - 7:31am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

ConciseFuzzyRepresentaion_of_ BigGraphs_Poster.pdf

(42)

Keywords

Subscribe

Send Author a Private Message
[1] Faisal N. Abu-Khzam, Amer Haj Ahmad, Rana H. Mouawi, "Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5056. Accessed: Aug. 07, 2020.
@article{5056-20,
url = {http://sigport.org/5056},
author = {Faisal N. Abu-Khzam; Amer Haj Ahmad; Rana H. Mouawi },
publisher = {IEEE SigPort},
title = {Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach},
year = {2020} }
TY - EJOUR
T1 - Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach
AU - Faisal N. Abu-Khzam; Amer Haj Ahmad; Rana H. Mouawi
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5056
ER -
Faisal N. Abu-Khzam, Amer Haj Ahmad, Rana H. Mouawi. (2020). Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach. IEEE SigPort. http://sigport.org/5056
Faisal N. Abu-Khzam, Amer Haj Ahmad, Rana H. Mouawi, 2020. Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach. Available at: http://sigport.org/5056.
Faisal N. Abu-Khzam, Amer Haj Ahmad, Rana H. Mouawi. (2020). "Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach." Web.
1. Faisal N. Abu-Khzam, Amer Haj Ahmad, Rana H. Mouawi. Concise Fuzzy Representation of Big Graphs: A Dimensionality Reduction Approach [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5056

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

Dominik Koeppl

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:
Dominik Koeppl
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

(63)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[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: Aug. 07, 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

On dynamic succinct graph representations

Miguel Coimbra
Guillermo de Bernardo

Paper Details

Authors:
Miguel Coimbra
Guillermo de Bernardo
Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro
Submitted On:
27 March 2020 - 3:05pm
Short Link:
Type:
Event:
Presenter's Name:
Paper Code:
Session:
Document Year:
Cite

Document Files

Slides-On_Dynamic_Succinct_Graph_Representations

(52)

Keywords

Subscribe

Send Author a Private Message
[1] Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro, " On dynamic succinct graph representations", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5038. Accessed: Aug. 07, 2020.
@article{5038-20,
url = {http://sigport.org/5038},
author = {Miguel E. Coimbra; Alexandre P. Francisco; Luís M. S. Russo; Guillermo de Bernardo; Susana Ladra; Gonzalo Navarro },
publisher = {IEEE SigPort},
title = { On dynamic succinct graph representations},
year = {2020} }
TY - EJOUR
T1 - On dynamic succinct graph representations
AU - Miguel E. Coimbra; Alexandre P. Francisco; Luís M. S. Russo; Guillermo de Bernardo; Susana Ladra; Gonzalo Navarro
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5038
ER -
Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro. (2020). On dynamic succinct graph representations. IEEE SigPort. http://sigport.org/5038
Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro, 2020. On dynamic succinct graph representations. Available at: http://sigport.org/5038.
Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro. (2020). " On dynamic succinct graph representations." Web.
1. Miguel E. Coimbra, Alexandre P. Francisco, Luís M. S. Russo, Guillermo de Bernardo, Susana Ladra, Gonzalo Navarro. On dynamic succinct graph representations [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5038

Pattern search in grammar-compressed graphs

Rita Hartel

Paper Details

Authors:
Rita Hartel
Stefan Böttcher, Rita Hartel, Sven Peeters
Submitted On:
26 March 2020 - 6:50am
Short Link:
Type:
Event:
Presenter's Name:
Paper Code:
Session:

Document Files

DCC20.pdf

(45)

Keywords

Subscribe

Send Author a Private Message
[1] Stefan Böttcher, Rita Hartel, Sven Peeters, "Pattern search in grammar-compressed graphs", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5033. Accessed: Aug. 07, 2020.
@article{5033-20,
url = {http://sigport.org/5033},
author = {Stefan Böttcher; Rita Hartel; Sven Peeters },
publisher = {IEEE SigPort},
title = {Pattern search in grammar-compressed graphs},
year = {2020} }
TY - EJOUR
T1 - Pattern search in grammar-compressed graphs
AU - Stefan Böttcher; Rita Hartel; Sven Peeters
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5033
ER -
Stefan Böttcher, Rita Hartel, Sven Peeters. (2020). Pattern search in grammar-compressed graphs. IEEE SigPort. http://sigport.org/5033
Stefan Böttcher, Rita Hartel, Sven Peeters, 2020. Pattern search in grammar-compressed graphs. Available at: http://sigport.org/5033.
Stefan Böttcher, Rita Hartel, Sven Peeters. (2020). "Pattern search in grammar-compressed graphs." Web.
1. Stefan Böttcher, Rita Hartel, Sven Peeters. Pattern search in grammar-compressed graphs [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5033

Re-Pair in Small Space

Dominik Koeppl

Re-Pair is a grammar compression scheme with favorably good compression rates. The computation of Re-Pair comes with the cost of maintaining large frequency tables, which makes it hard to compute Re-Pair on large scale data sets. As a solution for this problem we present, given a text of length n whose characters are drawn from an integer alphabet, an O(n^2) time algorithm computing Re-Pair in n lg max(n, τ) bits of working space including the text space, where τ is the number of terminals and non-terminals.

Paper Details

Authors:
Dominik Koeppl
Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto
Submitted On:
31 March 2020 - 1:53am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

Poster

(54)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto, "Re-Pair in Small Space", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5032. Accessed: Aug. 07, 2020.
@article{5032-20,
url = {http://sigport.org/5032},
author = {Dominik Köppl; Tomohiro I; Isamu Furuya; Yoshimasa Takabatake; Kensuke Sakai; Keisuke Goto },
publisher = {IEEE SigPort},
title = {Re-Pair in Small Space},
year = {2020} }
TY - EJOUR
T1 - Re-Pair in Small Space
AU - Dominik Köppl; Tomohiro I; Isamu Furuya; Yoshimasa Takabatake; Kensuke Sakai; Keisuke Goto
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5032
ER -
Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto. (2020). Re-Pair in Small Space. IEEE SigPort. http://sigport.org/5032
Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto, 2020. Re-Pair in Small Space. Available at: http://sigport.org/5032.
Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto. (2020). "Re-Pair in Small Space." Web.
1. Dominik Köppl, Tomohiro I, Isamu Furuya, Yoshimasa Takabatake, Kensuke Sakai, Keisuke Goto. Re-Pair in Small Space [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5032

Practical Repetition-Aware Grammar Compression

Isamu Furuya

The goal of grammar compression is to construct a small sized context free grammar which uniquely generates the input text data. Among grammar compression methods, RePair is known for its good practical compression performance. MR-RePair was recently proposed as an improvement to RePair for constructing small-sized context free grammar for repetitive text data. However, a compact encoding scheme has not been discussed for MR-RePair. We propose a practical encoding method for MR-RePair and show its effectiveness through comparative experiments.

Paper Details

Authors:
Isamu Furuya
Submitted On:
25 March 2020 - 8:36pm
Short Link:
Type:
Event:
Session:
Document Year:
Cite

Document Files

main.pdf

(48)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] , "Practical Repetition-Aware Grammar Compression", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5030. Accessed: Aug. 07, 2020.
@article{5030-20,
url = {http://sigport.org/5030},
author = { },
publisher = {IEEE SigPort},
title = {Practical Repetition-Aware Grammar Compression},
year = {2020} }
TY - EJOUR
T1 - Practical Repetition-Aware Grammar Compression
AU -
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5030
ER -
. (2020). Practical Repetition-Aware Grammar Compression. IEEE SigPort. http://sigport.org/5030
, 2020. Practical Repetition-Aware Grammar Compression. Available at: http://sigport.org/5030.
. (2020). "Practical Repetition-Aware Grammar Compression." Web.
1. . Practical Repetition-Aware Grammar Compression [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5030

Towards Better Compressed Representations

Michal Ganczorz

We introduce the problem of computing a parsing where each phrase is of length at most m and which minimizes the zeroth order entropy of parsing. Based on the recent theoretical results we devise a heuristic for this problem. The solution has straightforward application in succinct text representations and gives practical improvements. Moreover the proposed heuristic yields structure which size can be bounded both by |S|H_{m-1}(S) and by |S|/m(H_0(S) + ... + H_{m-1}(S)),where H_{k}(S) is the k-th order empirical entropy of S.

Paper Details

Authors:
Michal Ganczorz
Michał Gańczorz
Submitted On:
25 March 2020 - 1:11pm
Short Link:
Type:
Event:
Presenter's Name:
Paper Code:
Session:

Document Files

poster_dcc.pdf

(54)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Michał Gańczorz, "Towards Better Compressed Representations", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5029. Accessed: Aug. 07, 2020.
@article{5029-20,
url = {http://sigport.org/5029},
author = {Michał Gańczorz },
publisher = {IEEE SigPort},
title = {Towards Better Compressed Representations},
year = {2020} }
TY - EJOUR
T1 - Towards Better Compressed Representations
AU - Michał Gańczorz
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5029
ER -
Michał Gańczorz. (2020). Towards Better Compressed Representations. IEEE SigPort. http://sigport.org/5029
Michał Gańczorz, 2020. Towards Better Compressed Representations. Available at: http://sigport.org/5029.
Michał Gańczorz. (2020). "Towards Better Compressed Representations." Web.
1. Michał Gańczorz. Towards Better Compressed Representations [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5029

Pages