Compressing Web Graphs as Texts
Universidade do Chile –
The need to run different kinds of algorithms over large Web graphs motivates
the research for compressed graph representations that permit accessing
without decompressing them. At this point there exist a few such compression
proposals, some of them very effective in practice. In this talk we introduce
a novel approach to graph compression, based on regarding the graph as a text
and using existing techniques for text compression/indexing. This permits
accessing the graph efficiently without decompressing it, and in addition
brings in new functionalities over the compressed graph. Our experimental
results show that our technique has the potential of being competitive with
the best alternative techniques, yet not fully satisfactory.
Then we introduce a second approach, where we go back to pure compression.
By far the best current result is the technique by Boldi and Vigna,
which takes advantage of several particular properties of Web graphs. We show
that the same properties can be exploited with a different and
elegant technique, built on Re-Pair compression, which achieves about the same
space but much faster navigation of the graph. Moreover, the technique has the
potential of adapting well to secondary memory.
Finally, we comment on ongoing work to combine those approaches. The
successful scheme can be enriched with succinct data structures so as to
permit further graph traversal operations.
Date: 2007-Sep-28 Time: 16:30:00 Room: 336
For more information:
Workshop “Metabolism and mathematical models: Two for a tango” – 2nd Edition
Title: Workshop Metabolism and mathematical models: Two for a tango – 2nd Edition
Dates: October 25-26, 2022
Location: This workshop will be held in a virtual way
The topic of this workshop is metabolism in general, with a special focus, although not exclusive, on parasitology. Besides an exploration of the biological, biochemical and biomedical aspects, the workshop will also aim at presenting some of the mathematical modelling, algorithmic theory and software development that have become crucial to explore such aspects.
This workshop is being organised in the context of two projects, both with the Inria European Team Erable. One of the projects involves a partnership with the University of São Paulo (USP), in São Paulo, Brazil, more specifically the Institute of Mathematics and Statistics (IME) and the Institute of Biomedical Sciences – Inria Associated Team Capoeira – and the other involves the Inesc-ID/IST in Portugal, ETH in Zürich and EMBL in Heidelberg – H2020 Twinning Project Olissipo.
The workshop is open to all members of these two projects but also, importantly, to the community in general.
The program and more details are available here.