Difference between revisions of "Graph compression on the development history of software (internship)"

From Software Heritage Wiki
Jump to: navigation, search
(Graph compression on the development history of software)
Line 30: Line 30:
'''Internship mentors''':
'''Internship mentors''':
* Francesca Bassi <francesca.bassi@l2s.centralesupelec.fr>
* Stefano Zacchiroli <zack@upsilon.cc>
* Stefano Zacchiroli <zack@upsilon.cc>

Revision as of 13:10, 2 October 2018

Graph compression on the development history of software

Context: Software Heritage is an ambitious research project whose goal is to collect, preserve in the very long term, and share the whole publicly accessible Free/Open Source Software (FOSS) in source code form.

Description: The Software Heritage data model is a big Merkle DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~100 B edges, which makes it hard to fit in memory using naive approaches. Graph compression techniques have been successfully used to compress the Web graph (which is slightly larger than the Software Heritage one) and make it fit in memory. The goal of this internship is review existing graph compression techniques and apply the most appropriate one to the Software Heritage case, enabling in-memory processing of its Merkle DAG.

Desirable skills to obtain this internship:

  • familiarity with system programming
  • familiarity with basic graph algorithms
  • C development
  • working knowledge of basic compression techniques from information theory would be a plus

Workplace: Inria Paris

Environnement: you will work shoulder to shoulder with all members of the Software Heritage team, and you will have a chance to witness from within the construction of the ultimate source code archive.

Internship mentors:

  • Francesca Bassi <francesca.bassi@l2s.centralesupelec.fr>
  • Stefano Zacchiroli <zack@upsilon.cc>