Documents
Presentation Slides
Presentation Slides
On dynamic succinct graph representations
- Citation Author(s):
- Submitted by:
- Miguel Coimbra
- Last updated:
- 27 March 2020 - 3:05pm
- Document Type:
- Presentation Slides
- Document Year:
- 2020
- Event:
- Presenters:
- Miguel Coimbra
- Paper Code:
- 170
- Categories:
Comments
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.