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

Emerging: Big Data

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:
3 April 2020 - 1:15pm
Short Link:
Type:
Paper Code:
Document Year:
Cite

Document Files

submitted.pdf

(1)

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: Apr. 04, 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

(5)

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: Apr. 04, 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

(5)

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: Apr. 04, 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

(4)

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: Apr. 04, 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

(8)

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: Apr. 04, 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

(9)

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: Apr. 04, 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

(13)

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: Apr. 04, 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

(8)

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: Apr. 04, 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

(12)

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: Apr. 04, 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

Edge minimization in de Bruijn graphs

Uwe Baier

This paper introduces the de Bruijn graph edge minimization problem, which is related to the compression of de Bruijn graphs: find the order-k de Bruijn graph with minimum edge count among all orders. We describe an efficient algorithm that solves this problem. Since the edge minimization problem is connected to the BWT compression technique called "tunneling", the paper also describes a way to minimize the length of a tunneled BWT in such a way that useful properties for sequence analysis are preserved.

Paper Details

Authors:
Uwe Baier
Thomas Büchler, Enno Ohlebusch, Pascal Weber
Submitted On:
24 March 2020 - 5:56am
Short Link:
Type:
Event:
Presenter's Name:
Session:
Document Year:
Cite

Document Files

slides_dcc_20.pdf

(7)

Keywords

Additional Categories

Subscribe

Send Author a Private Message
[1] Thomas Büchler, Enno Ohlebusch, Pascal Weber, "Edge minimization in de Bruijn graphs", IEEE SigPort, 2020. [Online]. Available: http://sigport.org/5023. Accessed: Apr. 04, 2020.
@article{5023-20,
url = {http://sigport.org/5023},
author = {Thomas Büchler; Enno Ohlebusch; Pascal Weber },
publisher = {IEEE SigPort},
title = {Edge minimization in de Bruijn graphs},
year = {2020} }
TY - EJOUR
T1 - Edge minimization in de Bruijn graphs
AU - Thomas Büchler; Enno Ohlebusch; Pascal Weber
PY - 2020
PB - IEEE SigPort
UR - http://sigport.org/5023
ER -
Thomas Büchler, Enno Ohlebusch, Pascal Weber. (2020). Edge minimization in de Bruijn graphs. IEEE SigPort. http://sigport.org/5023
Thomas Büchler, Enno Ohlebusch, Pascal Weber, 2020. Edge minimization in de Bruijn graphs. Available at: http://sigport.org/5023.
Thomas Büchler, Enno Ohlebusch, Pascal Weber. (2020). "Edge minimization in de Bruijn graphs." Web.
1. Thomas Büchler, Enno Ohlebusch, Pascal Weber. Edge minimization in de Bruijn graphs [Internet]. IEEE SigPort; 2020. Available from : http://sigport.org/5023

Pages