# On dynamic succinct graph representations

## k2-trees-simple-template_no-sound.pdf

### Thanks for your inspiring

Thanks for your inspiring talk!
The topic is very similar to "Revisiting compact RDF stores based on k2-trees" (https://sigport.org/documents/revisiting-compact-rdf-stores-based-k2-trees),
but this time the focus is set on the dynamic setting.
Here, dynamic means that you allow adding/deleting edges, which is reflected by flipping a 1 or 0 in the binary matrix represented by the k^2 tree.
Supporting vertex insertion/deletion seems hard, though?

If I've correctly understood your video, the main point was to adapt the "dynamizing" technique of Munro et al. to k^2 trees?

I've collected some small questions:

Silde 11: Is ε a constant less than one? For your data structure, the gist seems tho following:
The smaller the epsilon, the faster the insertion. However, all times (except the List operation) and the space becomes worse with smaller ε.

Slide 13: What is the job of the lookup hash table? You already represent the graph completely with the adjacency lists.

Slide 19: How are the static k^2 trees represented? Do you use a naive representation?

Slide 22: It could be nice to have the references for [2],[3] and [7] available.

For the evaluation, what ε did you choose?

Slide 36: The time in the valgrind plot is in what unit?

### We are glad to draw interest

We are glad to draw interest from fellow researchers, feel free to ask further questions.

>>> The topic is very similar to "Revisiting compact RDF stores based on k2-trees" (https://sigport.org/documents/revisiting-compact-rdf-stores-based-k2-trees),
>>> but this time the focus is set on the dynamic setting.
>>> Here, dynamic means that you allow adding/deleting edges, which is reflected by flipping a 1 or 0 in the binary matrix represented by the k^2 tree.
Supporting vertex insertion/deletion seems hard, though?

>>> If I've correctly understood your video, the main point was to adapt the "dynamizing" technique of Munro et al. to k^2 trees?

That is correct.

>>> I've collected some small questions:

>>> Silde 11: Is ε a constant less than one? For your data structure, the gist seems tho following:
The smaller the epsilon, the faster the insertion. However, all times (except the List operation) and the space becomes worse with smaller ε.

>>> Slide 13: What is the job of the lookup hash table? You already represent the graph completely with the adjacency lists.

The hash table is used just for looking up edges in (expected) constant time in E0.

>>> Slide 19: How are the static k^2 trees represented? Do you use a naive representation?

We use the representation provided by the authors of k2-trees.
We just change the code so that some internal auxiliary data structures could be shared among the different trees in the collection.

>>> Slide 22: It could be nice to have the references for [2],[3] and [7] available.

[2] - Nieves R. Brisaboa, Susana Ladra, and Gonzalo Navarro, “Compact representation of web graphs with extended functionality,” Information Systems, vol. 39, pp. 152–174, 2014.

[3] - Nieves R. Brisaboa, Ana Cerdeira-Pena, Guillermo de Bernardo, and Gonzalo Navarro, “Compressed representation of dynamic binary relations with applications,” Information Systems, vol. 69, pp. 106–123, 2017.

[7] - Diego Arroyuelo, Guillermo de Bernardo, Travis Gagie, and Gonzalo Navarro, “Faster dynamic compressed d-ary relations,” in String Processing and Information Retrieval (SPIRE), 2019, pp. 419–433.

>>> For the evaluation, what ε did you choose?

We evaluated with epsilon equal to 0.25.

>>> Slide 36: The time in the valgrind plot is in what unit?

It is the number of processor instructions executed, obtained with valgrind.

Best.

### Paper Details

Authors:
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
Type:
Presentation Slides
Event:
Presenter's Name:
Miguel Coimbra
Paper Code:
170
Session:
Session 8
Document Year:
2020

(54)

### Subscribe

[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. 10, 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