https://wiki.softwareheritage.org/api.php?action=feedcontributions&user=Haltode&feedformat=atomSoftware Heritage Wiki - User contributions [en]2024-03-28T20:31:12ZUser contributionsMediaWiki 1.31.16https://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1128Google Summer of Code 2019/Graph compression2019-12-11T16:53:38Z<p>Haltode: Update GSoC portal link</p>
<hr />
<div>* '''Title:''' Graph compression<br />
<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with 12 billion nodes and 165 billion 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 GSoC project 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.<br />
<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/archive/2019/projects/6283725761937408/ project on the GSoC portal]<br />
<br />
* '''What was done:'''<br />
** Git repo: [https://forge.softwareheritage.org/source/swh-graph/ swh-graph] (list of my [https://wiki.softwareheritage.org/wiki/Google_Summer_of_Code_2019/Graph_compression/Commit_list commits])<br />
** Research on graph compression: evaluate/experiment feasibility and compression rate of multiple techniques<br />
** Docker environment and scripts to automate the entire compression pipeline<br />
** REST API to query the graph<br />
*** Java server side: load the compressed graph, run API endpoints traversal algorithms, unit tests, javadoc<br />
*** Python client side: integration with SWH infrastructure, integration tests<br />
** Automated benchmarking tools with statistical analysis<br />
** General documentation on docker environment, compression steps, graph query use-cases, etc.<br />
<br />
* '''Highlights:'''<br />
** Compression rates: 4.48 bits/edge (transposed graph) and 4.91 bits/edge (direct graph)<br />
** Memory requirements for loading both graphs: 200GB of RAM<br />
** Total compression time: 1 week<br />
** Node successors lookup times: below 2μs<br />
<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00010.html week 2019/34]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression/Commit_list&diff=1117Google Summer of Code 2019/Graph compression/Commit list2019-08-28T12:22:43Z<p>Haltode: </p>
<hr />
<div>* [https://forge.softwareheritage.org/rDGRPHb31d2e86a80cf8b85d4bf51f30be8e463fe994e4 b31d2e86a80cf8b85d4bf51f30be8e463fe994e4]<br />
* [https://forge.softwareheritage.org/rDGRPH0b46253799f43a25a8528926052340f93a1a911b 0b46253799f43a25a8528926052340f93a1a911b]<br />
* [https://forge.softwareheritage.org/rDGRPHc7363b064ae1ed52c271b9831b934cd196589c8e c7363b064ae1ed52c271b9831b934cd196589c8e]<br />
* [https://forge.softwareheritage.org/rDGRPHb6c6e1eec131a002a44e01cef17abb81ec958421 b6c6e1eec131a002a44e01cef17abb81ec958421]<br />
* [https://forge.softwareheritage.org/rDGRPHd5dcbfcdf245777a8753ccc6ac5414e762605abe d5dcbfcdf245777a8753ccc6ac5414e762605abe]<br />
* [https://forge.softwareheritage.org/rDGRPH493a3b007b1f249092dc671abe591327622a058f 493a3b007b1f249092dc671abe591327622a058f]<br />
* [https://forge.softwareheritage.org/rDGRPH7705d1c8b8ccf165fd7bb0fb4ac87dc1050994c0 7705d1c8b8ccf165fd7bb0fb4ac87dc1050994c0]<br />
* [https://forge.softwareheritage.org/rDGRPH101c50f2f10eb01ad08ee831fc70d140fae750fd 101c50f2f10eb01ad08ee831fc70d140fae750fd]<br />
* [https://forge.softwareheritage.org/rDGRPHb1fdd018fd5ad2fd95aa6d073e5058a64d570a2c b1fdd018fd5ad2fd95aa6d073e5058a64d570a2c]<br />
* [https://forge.softwareheritage.org/rDGRPHb0bcbe039d19a404a73052aae68f485328262ce3 b0bcbe039d19a404a73052aae68f485328262ce3]<br />
* [https://forge.softwareheritage.org/rDGRPH2bc36b702416888c2155a88d129b8a07e124c1ac 2bc36b702416888c2155a88d129b8a07e124c1ac]<br />
* [https://forge.softwareheritage.org/rDGRPH468a99dc4dd31a37681970fecf3bdb4413251f4b 468a99dc4dd31a37681970fecf3bdb4413251f4b]<br />
* [https://forge.softwareheritage.org/rDGRPHd9e93fb46f5e6783282ff0160dca489bae9fc946 d9e93fb46f5e6783282ff0160dca489bae9fc946]<br />
* [https://forge.softwareheritage.org/rDGRPH30218b7dc68f6a5eb8f842827d5a5b01fb252e53 30218b7dc68f6a5eb8f842827d5a5b01fb252e53]<br />
* [https://forge.softwareheritage.org/rDGRPHb46335c0e77275a3c0357eb479008ced702a2b29 b46335c0e77275a3c0357eb479008ced702a2b29]<br />
* [https://forge.softwareheritage.org/rDGRPH4c0846228465fb32c6fc2508f4beadee82433c18 4c0846228465fb32c6fc2508f4beadee82433c18]<br />
* [https://forge.softwareheritage.org/rDGRPH87192dfddd4bbce01cedd9942df807977dfd70ef 87192dfddd4bbce01cedd9942df807977dfd70ef]<br />
* [https://forge.softwareheritage.org/rDGRPH6a84a51b6f6a3d62edff4f7b885f63537999cdb6 6a84a51b6f6a3d62edff4f7b885f63537999cdb6]<br />
* [https://forge.softwareheritage.org/rDGRPH9b02f4137cb6154bd7c20ab87edde11ebdd4ae24 9b02f4137cb6154bd7c20ab87edde11ebdd4ae24]<br />
* [https://forge.softwareheritage.org/rDGRPH2da9b1a05395a5dba8cf8317faca869872e2c22d 2da9b1a05395a5dba8cf8317faca869872e2c22d]<br />
* [https://forge.softwareheritage.org/rDGRPH258aaf24354a28553e23f7d890b373dc91640b96 258aaf24354a28553e23f7d890b373dc91640b96]<br />
* [https://forge.softwareheritage.org/rDGRPH9ca54a873d7af567274e151369850879fd414c37 9ca54a873d7af567274e151369850879fd414c37]<br />
* [https://forge.softwareheritage.org/rDGRPH9ea36f08ce24b6d229b4d8dff85693a37433ee89 9ea36f08ce24b6d229b4d8dff85693a37433ee89]<br />
* [https://forge.softwareheritage.org/rDGRPH6aee508c4cdf24789dc6c66a4b9568863a3c403c 6aee508c4cdf24789dc6c66a4b9568863a3c403c]<br />
* [https://forge.softwareheritage.org/rDGRPH13d53c66452a5f3bc9f06bc99adf834e4ebda62b 13d53c66452a5f3bc9f06bc99adf834e4ebda62b]<br />
* [https://forge.softwareheritage.org/rDGRPH22b9258fb2ccaeae5c0ab2efa3553fb19d62084b 22b9258fb2ccaeae5c0ab2efa3553fb19d62084b]<br />
* [https://forge.softwareheritage.org/rDGRPHfb57ec5143a84a79cc22c67cd905da708029de81 fb57ec5143a84a79cc22c67cd905da708029de81]<br />
* [https://forge.softwareheritage.org/rDGRPHf12a5aafff2696e94814d6453ed00f86991a831f f12a5aafff2696e94814d6453ed00f86991a831f]<br />
* [https://forge.softwareheritage.org/rDGRPH88bfedaf98833fdbe236b2d6bdb0da6272b95d30 88bfedaf98833fdbe236b2d6bdb0da6272b95d30]<br />
* [https://forge.softwareheritage.org/rDGRPH1fd382b69889600686f65facd668fc9fa5bf0ce9 1fd382b69889600686f65facd668fc9fa5bf0ce9]<br />
* [https://forge.softwareheritage.org/rDGRPH8ff03d608db64080d3fd45fdb54812fb5d314166 8ff03d608db64080d3fd45fdb54812fb5d314166]<br />
* [https://forge.softwareheritage.org/rDGRPH7e1917a236f32a5003507c9c73a848709982be27 7e1917a236f32a5003507c9c73a848709982be27]<br />
* [https://forge.softwareheritage.org/rDGRPH8f19048ff75e0687a20751b3839ca18547bcba93 8f19048ff75e0687a20751b3839ca18547bcba93]<br />
* [https://forge.softwareheritage.org/rDGRPHba9b3913c5a9a82f5242f6d630d0620da691ec9b ba9b3913c5a9a82f5242f6d630d0620da691ec9b]<br />
* [https://forge.softwareheritage.org/rDGRPHa495498689178f6f10caf1443443ccf73b7a2c35 a495498689178f6f10caf1443443ccf73b7a2c35]<br />
* [https://forge.softwareheritage.org/rDGRPH02e4f44f91e0ecbf6615a6c39bc93a7fa5389cd6 02e4f44f91e0ecbf6615a6c39bc93a7fa5389cd6]<br />
* [https://forge.softwareheritage.org/rDGRPH81b6c0032c8c1649caa3eca95658d8d8eaa5448c 81b6c0032c8c1649caa3eca95658d8d8eaa5448c]<br />
* [https://forge.softwareheritage.org/rDGRPH78f18d06f734897f2f8bd1e1b0d29d613d8c8a39 78f18d06f734897f2f8bd1e1b0d29d613d8c8a39]<br />
* [https://forge.softwareheritage.org/rDGRPHf5d245f4e312a85b9dfce647e8be1b2580b3897f f5d245f4e312a85b9dfce647e8be1b2580b3897f]<br />
* [https://forge.softwareheritage.org/rDGRPH403f1e010c3ee6b85708a3cf46fbe262d2a26061 403f1e010c3ee6b85708a3cf46fbe262d2a26061]<br />
* [https://forge.softwareheritage.org/rDGRPH4013dbc12e435719aa65f0684318a801a2a9d668 4013dbc12e435719aa65f0684318a801a2a9d668]<br />
* [https://forge.softwareheritage.org/rDGRPH223650ed7e6a2e22ea717027beed25a2917767c3 223650ed7e6a2e22ea717027beed25a2917767c3]<br />
* [https://forge.softwareheritage.org/rDGRPHc57819ce34ae7a85ba6deb6944744a5b830c8ed8 c57819ce34ae7a85ba6deb6944744a5b830c8ed8]<br />
* [https://forge.softwareheritage.org/rDGRPHa098482cba3e50473c13987d536e920ab1a7994e a098482cba3e50473c13987d536e920ab1a7994e]<br />
* [https://forge.softwareheritage.org/rDGRPH293eb8a57c9f0418eb00e1339094ab46af2fea42 293eb8a57c9f0418eb00e1339094ab46af2fea42]<br />
* [https://forge.softwareheritage.org/rDGRPH6c1186676c462482e9e30de84696c9be37d436bc 6c1186676c462482e9e30de84696c9be37d436bc]<br />
* [https://forge.softwareheritage.org/rDGRPH9353712815b994c984fa2ac8bb7184047f3c6cd9 9353712815b994c984fa2ac8bb7184047f3c6cd9]<br />
* [https://forge.softwareheritage.org/rDGRPH4ada70da1ead40a9411419de20b725d2b43ef5a2 4ada70da1ead40a9411419de20b725d2b43ef5a2]<br />
* [https://forge.softwareheritage.org/rDGRPH981847b49725196fa41ce8c9965c44553c50ea3f 981847b49725196fa41ce8c9965c44553c50ea3f]<br />
* [https://forge.softwareheritage.org/rDGRPHe309e7f4f3f1f3147d9c31228bc61112500a92d4 e309e7f4f3f1f3147d9c31228bc61112500a92d4]<br />
* [https://forge.softwareheritage.org/rDGRPH442ef0846cb0d66f007df3396ec8a52049940d59 442ef0846cb0d66f007df3396ec8a52049940d59]<br />
* [https://forge.softwareheritage.org/rDGRPHa769e313541d46f3a18de6abde85b62a8256f3cb a769e313541d46f3a18de6abde85b62a8256f3cb]<br />
* [https://forge.softwareheritage.org/rDGRPHb884ff82ee09fd43e3ee801bc0627a0bcb665830 b884ff82ee09fd43e3ee801bc0627a0bcb665830]<br />
* [https://forge.softwareheritage.org/rDGRPH93f1fb8ed6b9f41cf0d53f351df79469aecaf79a 93f1fb8ed6b9f41cf0d53f351df79469aecaf79a]<br />
* [https://forge.softwareheritage.org/rDGRPHa8d4b625d917062c9219838f324b019d8b46994a a8d4b625d917062c9219838f324b019d8b46994a]<br />
* [https://forge.softwareheritage.org/rDGRPHebfa6310c5ab642a8df9ea9f14a8c1328efc1fc9 ebfa6310c5ab642a8df9ea9f14a8c1328efc1fc9]<br />
* [https://forge.softwareheritage.org/rDGRPH0a81a047cfe3bfbfa5b74d6855e57dd1b1ddec75 0a81a047cfe3bfbfa5b74d6855e57dd1b1ddec75]<br />
* [https://forge.softwareheritage.org/rDGRPHfc9dd235c28b12c1f2d569011fabaad194de1572 fc9dd235c28b12c1f2d569011fabaad194de1572]<br />
* [https://forge.softwareheritage.org/rDGRPHfc52d428ce14d56e13709505ccbfe35ee445d70c fc52d428ce14d56e13709505ccbfe35ee445d70c]<br />
* [https://forge.softwareheritage.org/rDGRPH9413a20afdf6aaba570de477a02630f8effb86ec 9413a20afdf6aaba570de477a02630f8effb86ec]<br />
* [https://forge.softwareheritage.org/rDGRPH56dead50c511482b74bfbdc4911b9455f03084cc 56dead50c511482b74bfbdc4911b9455f03084cc]<br />
* [https://forge.softwareheritage.org/rDGRPH313eb76cd39ea10fe4bf0b645fd30346da2ebe15 313eb76cd39ea10fe4bf0b645fd30346da2ebe15]<br />
* [https://forge.softwareheritage.org/rDGRPHd56bfa886d2e41cc29b60efeba7cb8146480f90a d56bfa886d2e41cc29b60efeba7cb8146480f90a]<br />
* [https://forge.softwareheritage.org/rDGRPH832272c8e81ad48403cde27fba4190688c8f48be 832272c8e81ad48403cde27fba4190688c8f48be]<br />
* [https://forge.softwareheritage.org/rDGRPHedf9e6fa4b8680b7379f23519952747aeebb66c4 edf9e6fa4b8680b7379f23519952747aeebb66c4]<br />
* [https://forge.softwareheritage.org/rDGRPH61ee41418867c36cdb4589ba92367b48d6c6140c 61ee41418867c36cdb4589ba92367b48d6c6140c]<br />
* [https://forge.softwareheritage.org/rDGRPH025d694fd0aa1e6ad576398dbd9372bab9954d63 025d694fd0aa1e6ad576398dbd9372bab9954d63]<br />
* [https://forge.softwareheritage.org/rDGRPHcaf250d2c008a41ef02cb0500cb93519fd10fd4e caf250d2c008a41ef02cb0500cb93519fd10fd4e]<br />
* [https://forge.softwareheritage.org/rDGRPH946d235ebdac58baac27a246dc93706645365ead 946d235ebdac58baac27a246dc93706645365ead]<br />
* [https://forge.softwareheritage.org/rDGRPHdaa7cd8d7a0f7f4dd462256a4a13fa74b38344f5 daa7cd8d7a0f7f4dd462256a4a13fa74b38344f5]<br />
* [https://forge.softwareheritage.org/rDGRPH5bd8c806c2ef5911ac021833d6d07d7eecf92268 5bd8c806c2ef5911ac021833d6d07d7eecf92268]<br />
* [https://forge.softwareheritage.org/rDGRPH40914fa836651964554015368226d280a745ac0d 40914fa836651964554015368226d280a745ac0d]<br />
* [https://forge.softwareheritage.org/rDGRPH2cdf7bb658ade4caba3637b5ebdd79dedda9ac51 2cdf7bb658ade4caba3637b5ebdd79dedda9ac51]<br />
* [https://forge.softwareheritage.org/rDGRPH9ab8989c633ad36461c605b92618b226a3c428bf 9ab8989c633ad36461c605b92618b226a3c428bf]<br />
* [https://forge.softwareheritage.org/rDGRPHde6778f217965c684faccf2e95383bd20574e835 de6778f217965c684faccf2e95383bd20574e835]<br />
* [https://forge.softwareheritage.org/rDGRPH01e3b661384484cf14971b903e8e473a299ed442 01e3b661384484cf14971b903e8e473a299ed442]<br />
* [https://forge.softwareheritage.org/rDGRPH0ad569d7e71f2d85ca9047a204d58aabc33395d8 0ad569d7e71f2d85ca9047a204d58aabc33395d8]<br />
* [https://forge.softwareheritage.org/rDGRPH6e9bb13c272c33d66ef8db86680584b0301498c1 6e9bb13c272c33d66ef8db86680584b0301498c1]<br />
* [https://forge.softwareheritage.org/rDGRPH3229cd64175ad5a2c456ab0bce5a611ffb28b303 3229cd64175ad5a2c456ab0bce5a611ffb28b303]<br />
* [https://forge.softwareheritage.org/rDGRPH58abcb3f4e577d20a41b7e6f2e0d98c5ae959dfd 58abcb3f4e577d20a41b7e6f2e0d98c5ae959dfd]<br />
* [https://forge.softwareheritage.org/rDGRPH27a2871994e9c7655b5460373b113915b0a791f0 27a2871994e9c7655b5460373b113915b0a791f0]<br />
* [https://forge.softwareheritage.org/rDGRPHd04c698a7f92e0621f6a8d5eab525b3faaa7fa32 d04c698a7f92e0621f6a8d5eab525b3faaa7fa32]<br />
* [https://forge.softwareheritage.org/rDGRPH072e28513ce5303d30da9841a26cd046ee6b85ec 072e28513ce5303d30da9841a26cd046ee6b85ec]<br />
* [https://forge.softwareheritage.org/rDGRPH51f8878e7f4d40aeeb04c846cdf4098b9c27aa0b 51f8878e7f4d40aeeb04c846cdf4098b9c27aa0b]<br />
* [https://forge.softwareheritage.org/rDGRPH2f59c82262784f29900cf60876e4df9f2eb4653b 2f59c82262784f29900cf60876e4df9f2eb4653b]<br />
* [https://forge.softwareheritage.org/rDGRPH8e99fa365bda1756f773b5f074badc2ebf6fd2ac 8e99fa365bda1756f773b5f074badc2ebf6fd2ac]<br />
* [https://forge.softwareheritage.org/rDGRPHd2fe1900f376864faf1ca26267e6af144459c232 d2fe1900f376864faf1ca26267e6af144459c232]<br />
* [https://forge.softwareheritage.org/rDGRPH1444f74820b45fdecc5470275ca5d2b85d600b0a 1444f74820b45fdecc5470275ca5d2b85d600b0a]<br />
* [https://forge.softwareheritage.org/rDGRPH5fe89bd242ab041d00125eb878d9d36c25933841 5fe89bd242ab041d00125eb878d9d36c25933841]<br />
* [https://forge.softwareheritage.org/rDGRPH096207105ee5e82fc2605b1bce6592c05499d1f7 096207105ee5e82fc2605b1bce6592c05499d1f7]<br />
* [https://forge.softwareheritage.org/rDGRPHbc75822621a63d239fc5d53a0044531b9f514e96 bc75822621a63d239fc5d53a0044531b9f514e96]<br />
* [https://forge.softwareheritage.org/rDGRPH7297e656af6353bd246c99390571ffdb97915fe5 7297e656af6353bd246c99390571ffdb97915fe5]<br />
* [https://forge.softwareheritage.org/rDGRPH5bcfcca2c485cb1974ee95984e7bbeab597655aa 5bcfcca2c485cb1974ee95984e7bbeab597655aa]<br />
* [https://forge.softwareheritage.org/rDGRPH48929cae3397cd4e01e647605bf493b976a50936 48929cae3397cd4e01e647605bf493b976a50936]<br />
* [https://forge.softwareheritage.org/rDGRPH19c3506824e8a3dac7819075d4f3500915ccd236 19c3506824e8a3dac7819075d4f3500915ccd236]<br />
* [https://forge.softwareheritage.org/rDGRPH0c3db69256386134b1b494916d202ceae902e01b 0c3db69256386134b1b494916d202ceae902e01b]<br />
* [https://forge.softwareheritage.org/rDGRPH1d24b57634758ebe3a702038729e790d9ceeb24a 1d24b57634758ebe3a702038729e790d9ceeb24a]<br />
* [https://forge.softwareheritage.org/rDGRPH4b122cb96e453cea09fbaeff5abb6a45f2ac5500 4b122cb96e453cea09fbaeff5abb6a45f2ac5500]<br />
* [https://forge.softwareheritage.org/rDGRPH1e016eec9cacaa35993604c51bc9d2cafe64203f 1e016eec9cacaa35993604c51bc9d2cafe64203f]<br />
* [https://forge.softwareheritage.org/rDGRPH03aeede55f124656c76e8f30e81edb7f0289a6b1 03aeede55f124656c76e8f30e81edb7f0289a6b1]<br />
* [https://forge.softwareheritage.org/rDGRPH1a59cc1d611c0fa6fb7c3606915583426a50114d 1a59cc1d611c0fa6fb7c3606915583426a50114d]<br />
* [https://forge.softwareheritage.org/rDGRPHb702bcbcc505c5c5db10de36251d2e7d9ccafc85 b702bcbcc505c5c5db10de36251d2e7d9ccafc85]<br />
* [https://forge.softwareheritage.org/rDGRPH9ef0634ba95bede3db6ef6b4ad0e8537df815201 9ef0634ba95bede3db6ef6b4ad0e8537df815201]<br />
* [https://forge.softwareheritage.org/rDGRPHc18ac728550e26d3f5317b3d7bc74a7db46b1c1c c18ac728550e26d3f5317b3d7bc74a7db46b1c1c]<br />
* [https://forge.softwareheritage.org/rDGRPHeeff1c1b6b629fa4c51a655c4455a23463505556 eeff1c1b6b629fa4c51a655c4455a23463505556]<br />
* [https://forge.softwareheritage.org/rDGRPH5158e27d0e38dfb6ee5ac3e0cf99d134cdc0d824 5158e27d0e38dfb6ee5ac3e0cf99d134cdc0d824]<br />
* [https://forge.softwareheritage.org/rDGRPH00b71f8a15544f7376e72b6783de4cc6d7c17c1c 00b71f8a15544f7376e72b6783de4cc6d7c17c1c]<br />
* [https://forge.softwareheritage.org/rDGRPH29be5dc9dcf396e25b97d072d1000fb3b5ad5fd4 29be5dc9dcf396e25b97d072d1000fb3b5ad5fd4]<br />
* [https://forge.softwareheritage.org/rDGRPHc3108160f157c82cca3802d0ebc62d33ec293b6a c3108160f157c82cca3802d0ebc62d33ec293b6a]<br />
* [https://forge.softwareheritage.org/rDGRPH0af9c1cdf936853ca1982e4fb7577b2c799955f0 0af9c1cdf936853ca1982e4fb7577b2c799955f0]<br />
* [https://forge.softwareheritage.org/rDGRPH69e2dd06696bce1d30c76f7e3e1de8549ef03417 69e2dd06696bce1d30c76f7e3e1de8549ef03417]<br />
* [https://forge.softwareheritage.org/rDGRPH494624e7cc6246b7ee51b6480abfba8b88879a7e 494624e7cc6246b7ee51b6480abfba8b88879a7e]<br />
* [https://forge.softwareheritage.org/rDGRPH72f5d9f6744f8f2dfa81247d06a995ad34481659 72f5d9f6744f8f2dfa81247d06a995ad34481659]<br />
* [https://forge.softwareheritage.org/rDGRPH3012ced62560afcd53aa367bd3c529b0eda375db 3012ced62560afcd53aa367bd3c529b0eda375db]<br />
* [https://forge.softwareheritage.org/rDGRPHd1118062ac65e05c7e51973b74ebda85409e8b51 d1118062ac65e05c7e51973b74ebda85409e8b51]<br />
* [https://forge.softwareheritage.org/rDGRPHa03efd5ecd1227298216536f34f5642027cc2979 a03efd5ecd1227298216536f34f5642027cc2979]<br />
* [https://forge.softwareheritage.org/rDGRPHe7a80f4b392e3a6c93491d706ba3da55ea8dd8fc e7a80f4b392e3a6c93491d706ba3da55ea8dd8fc]<br />
* [https://forge.softwareheritage.org/rDGRPH66b4068e982685d8ba87b0de649de4f3b7e5695a 66b4068e982685d8ba87b0de649de4f3b7e5695a]<br />
* [https://forge.softwareheritage.org/rDGRPHe98ccac77252af30084016a657fcc27ee513b0b8 e98ccac77252af30084016a657fcc27ee513b0b8]<br />
* [https://forge.softwareheritage.org/rDGRPH0f35f18570acb9602434692195e9a7cea4958569 0f35f18570acb9602434692195e9a7cea4958569]<br />
* [https://forge.softwareheritage.org/rDGRPHce0ca93d412cbbdecab5858f93fd897b3401920b ce0ca93d412cbbdecab5858f93fd897b3401920b]<br />
* [https://forge.softwareheritage.org/rDGRPH91b2ee93b233b43e367ab8021782dec9536dd080 91b2ee93b233b43e367ab8021782dec9536dd080]<br />
* [https://forge.softwareheritage.org/rDGRPHbbe69cd469bba76f195eabe56e6a4d761111ef66 bbe69cd469bba76f195eabe56e6a4d761111ef66]<br />
* [https://forge.softwareheritage.org/rDGRPH0276d1bf474d6e3e46e104717625d108cfa04ada 0276d1bf474d6e3e46e104717625d108cfa04ada]<br />
* [https://forge.softwareheritage.org/rDGRPHa3016cd837cbdbf328cb5703307e02a04b275976 a3016cd837cbdbf328cb5703307e02a04b275976]<br />
* [https://forge.softwareheritage.org/rDGRPH7c1cacd83f17fdcf5f30a903478b5e2bc1a710ac 7c1cacd83f17fdcf5f30a903478b5e2bc1a710ac]<br />
* [https://forge.softwareheritage.org/rDGRPH2bdba36a9ae59cbf290967783c6b0fdd63dc5c4e 2bdba36a9ae59cbf290967783c6b0fdd63dc5c4e]<br />
* [https://forge.softwareheritage.org/rDGRPH3fb9b44ab6026afa57f7fee6087befd4d9215644 3fb9b44ab6026afa57f7fee6087befd4d9215644]<br />
* [https://forge.softwareheritage.org/rDGRPH675d1637c7d0ec128e4d0ccddd892be184c37b27 675d1637c7d0ec128e4d0ccddd892be184c37b27]<br />
* [https://forge.softwareheritage.org/rDGRPH927fc070364246d132ede89b8af31da71406012d 927fc070364246d132ede89b8af31da71406012d]<br />
* [https://forge.softwareheritage.org/rDGRPH0987e9fb6985067707b255aa6d957fe0b62b5d66 0987e9fb6985067707b255aa6d957fe0b62b5d66]<br />
* [https://forge.softwareheritage.org/rDGRPH5d25ebdd188f8ba80659f8e5e0724d236c579ce4 5d25ebdd188f8ba80659f8e5e0724d236c579ce4]<br />
* [https://forge.softwareheritage.org/rDGRPH2d64daeacf61aa3c183e9f2371f6a0ed59032e0a 2d64daeacf61aa3c183e9f2371f6a0ed59032e0a]<br />
* [https://forge.softwareheritage.org/rDGRPH58c2fe6c4dae82a1db0cc4e92c15c00bf02776da 58c2fe6c4dae82a1db0cc4e92c15c00bf02776da]<br />
* [https://forge.softwareheritage.org/rDGRPH1626a831552e313bc7af61766bffc80d00106964 1626a831552e313bc7af61766bffc80d00106964]<br />
* [https://forge.softwareheritage.org/rDGRPH674ccb9b65a9a19de1b7b8ea82be61d41df979aa 674ccb9b65a9a19de1b7b8ea82be61d41df979aa]<br />
* [https://forge.softwareheritage.org/rDGRPH3bb73725d03ec0f0d70811f299a3e369aeaa53ea 3bb73725d03ec0f0d70811f299a3e369aeaa53ea]<br />
* [https://forge.softwareheritage.org/rDGRPH7d06e5c21a62484009efac6714e666f79da91092 7d06e5c21a62484009efac6714e666f79da91092]<br />
* [https://forge.softwareheritage.org/rDGRPH5e877f798d4663b5b68d16e07de74a2a81e30911 5e877f798d4663b5b68d16e07de74a2a81e30911]<br />
* [https://forge.softwareheritage.org/rDGRPHb0fe60222c2713dcd1c366df71b7a0b333c794e6 b0fe60222c2713dcd1c366df71b7a0b333c794e6]<br />
* [https://forge.softwareheritage.org/rDGRPH14a73c2e801f99d4bc551d9abd2b9d98115f5dd3 14a73c2e801f99d4bc551d9abd2b9d98115f5dd3]<br />
* [https://forge.softwareheritage.org/rDGRPHfa669aae82737a1bc4496daf9fc78c03dea0f689 fa669aae82737a1bc4496daf9fc78c03dea0f689]<br />
* [https://forge.softwareheritage.org/rDGRPH006db063cbe7a1797684c6c0df015dfea52777fa 006db063cbe7a1797684c6c0df015dfea52777fa]<br />
* [https://forge.softwareheritage.org/rDGRPH97a72106e6efe1ad828129eb2e2e4f2bd684d1ad 97a72106e6efe1ad828129eb2e2e4f2bd684d1ad]<br />
* [https://forge.softwareheritage.org/rDGRPHdfaaae935f5a40dc8862d00fdbbc6eefb5bdab44 dfaaae935f5a40dc8862d00fdbbc6eefb5bdab44]<br />
* [https://forge.softwareheritage.org/rDGRPH3c61e93a2c02e997b0497f7471ada1e255ca98fc 3c61e93a2c02e997b0497f7471ada1e255ca98fc]<br />
* [https://forge.softwareheritage.org/rDGRPH04f08f96594382623e139700fb0db9b8b6e42832 04f08f96594382623e139700fb0db9b8b6e42832]<br />
* [https://forge.softwareheritage.org/rDGRPHd55bbeed351c36937bea90128395fe830d3b240b d55bbeed351c36937bea90128395fe830d3b240b]<br />
* [https://forge.softwareheritage.org/rDGRPH11430ec4febc86ec0ce2d43bbcd7394c9da3c7a1 11430ec4febc86ec0ce2d43bbcd7394c9da3c7a1]<br />
* [https://forge.softwareheritage.org/rDGRPH5095dcdb74d067e6e7b53fb980b33cc076de5201 5095dcdb74d067e6e7b53fb980b33cc076de5201]<br />
* [https://forge.softwareheritage.org/rDGRPH71195a3bc1d2761c9a1612d74cf014fd19db2339 71195a3bc1d2761c9a1612d74cf014fd19db2339]<br />
* [https://forge.softwareheritage.org/rDGRPH608679a21b95cf45121ed26f81f809d5f5d79b55 608679a21b95cf45121ed26f81f809d5f5d79b55]<br />
* [https://forge.softwareheritage.org/rDGRPH384312b79b405ae868f6aa5fbb0271bad4766a8b 384312b79b405ae868f6aa5fbb0271bad4766a8b]<br />
* [https://forge.softwareheritage.org/rDGRPH4a7eb4500647356c465c64d8e83beead448fe0e2 4a7eb4500647356c465c64d8e83beead448fe0e2]<br />
* [https://forge.softwareheritage.org/rDGRPH5ff51bae7866adfeab85dea292adbedffea304dc 5ff51bae7866adfeab85dea292adbedffea304dc]<br />
* [https://forge.softwareheritage.org/rDGRPH6f96ffc672ca53559d89cf58dab8e5fc41e4e7c1 6f96ffc672ca53559d89cf58dab8e5fc41e4e7c1]<br />
* [https://forge.softwareheritage.org/rDGRPH83b04605553e13e6604d30463986b3a56a6d6e5f 83b04605553e13e6604d30463986b3a56a6d6e5f]<br />
* [https://forge.softwareheritage.org/rDGRPH542f7c68944e89d504d0415c89f3df5757077b75 542f7c68944e89d504d0415c89f3df5757077b75]<br />
* [https://forge.softwareheritage.org/rDGRPH95cc98bd2ef06ff94ffe32c7525028b226185a57 95cc98bd2ef06ff94ffe32c7525028b226185a57]<br />
* [https://forge.softwareheritage.org/rDGRPHa06f5b534e66668731eece4bf0d92fbb4c5a0688 a06f5b534e66668731eece4bf0d92fbb4c5a0688]<br />
* [https://forge.softwareheritage.org/rDGRPH40d8bfa5b7f0d49fc7753784ba9dac49b7cbc912 40d8bfa5b7f0d49fc7753784ba9dac49b7cbc912]<br />
* [https://forge.softwareheritage.org/rDGRPHae3105a94e244c0d37118918a8143ade833d27ee ae3105a94e244c0d37118918a8143ade833d27ee]<br />
* [https://forge.softwareheritage.org/rDGRPHe39500bae4729dbe8c586a0565e3c074b53b0c3c e39500bae4729dbe8c586a0565e3c074b53b0c3c]<br />
* [https://forge.softwareheritage.org/rDGRPHacd95e1f44c65679f32e6b0bffaf1baa124b3ade acd95e1f44c65679f32e6b0bffaf1baa124b3ade]<br />
* [https://forge.softwareheritage.org/rDGRPH87ee23bb8addabfd85a6e0ec1f89336da3868bb0 87ee23bb8addabfd85a6e0ec1f89336da3868bb0]<br />
* [https://forge.softwareheritage.org/rDGRPHa49c34399f4fbe44e97d61f80c515bf70b0a2b83 a49c34399f4fbe44e97d61f80c515bf70b0a2b83]<br />
* [https://forge.softwareheritage.org/rDGRPH63dc317c44bb475dacc011b6482c1e6d2e85865b 63dc317c44bb475dacc011b6482c1e6d2e85865b]<br />
* [https://forge.softwareheritage.org/rDGRPH6621977ddf70437b20e6306a571824d7ab1541fc 6621977ddf70437b20e6306a571824d7ab1541fc]<br />
* [https://forge.softwareheritage.org/rDGRPH3b4ef319c949c8a7191a940c2aacc4faa6c14acc 3b4ef319c949c8a7191a940c2aacc4faa6c14acc]<br />
* [https://forge.softwareheritage.org/rDGRPH6606fdf1fbf50177c1b15e47f33801db2db853d1 6606fdf1fbf50177c1b15e47f33801db2db853d1]<br />
* [https://forge.softwareheritage.org/rDGRPHc523be098e9f8c4ff7868a955e240bbad9930c14 c523be098e9f8c4ff7868a955e240bbad9930c14]<br />
* [https://forge.softwareheritage.org/rDGRPH1788535e8a308ecf72652d5843aa520702dc70e2 1788535e8a308ecf72652d5843aa520702dc70e2]<br />
* [https://forge.softwareheritage.org/rDGRPH5d2c6485095aabe30013afe55d0663670ec61120 5d2c6485095aabe30013afe55d0663670ec61120]<br />
* [https://forge.softwareheritage.org/rDGRPH6c13efd5d7fd9972a58b2e1b998c56ec2825b590 6c13efd5d7fd9972a58b2e1b998c56ec2825b590]<br />
* [https://forge.softwareheritage.org/rDGRPHdef9fed92862a4e768d2f968922566c5039a67f2 def9fed92862a4e768d2f968922566c5039a67f2]<br />
* [https://forge.softwareheritage.org/rDGRPH0b08fec6d5aaec76493d7b8aa0a539a40b788f9f 0b08fec6d5aaec76493d7b8aa0a539a40b788f9f]<br />
* [https://forge.softwareheritage.org/rDGRPH392fd1520494ec008f638e38d96645a539711fbb 392fd1520494ec008f638e38d96645a539711fbb]<br />
* [https://forge.softwareheritage.org/rDGRPH36020e626aa7c44154f417d9eb649b406c14c243 36020e626aa7c44154f417d9eb649b406c14c243]<br />
* [https://forge.softwareheritage.org/rDGRPHa994162aee75226c01312ef4a13a244d18c8e432 a994162aee75226c01312ef4a13a244d18c8e432]<br />
* [https://forge.softwareheritage.org/rDGRPH616c759fcff0809bd4c00434c19bbf2b598be6a4 616c759fcff0809bd4c00434c19bbf2b598be6a4]<br />
* [https://forge.softwareheritage.org/rDGRPH76320b0a8004708e59f1cdfdf3fbc3c47b1e951c 76320b0a8004708e59f1cdfdf3fbc3c47b1e951c]<br />
* [https://forge.softwareheritage.org/rDGRPHa47d54676557cc544d85381c2f7c3a8cfe261bb6 a47d54676557cc544d85381c2f7c3a8cfe261bb6]<br />
* [https://forge.softwareheritage.org/rDGRPHb1d64422d30d70cd9026f207718ff564a09b9831 b1d64422d30d70cd9026f207718ff564a09b9831]<br />
* [https://forge.softwareheritage.org/rDGRPHd5034a602c6ebb0a6530f3906a61ac425f1d4d70 d5034a602c6ebb0a6530f3906a61ac425f1d4d70]<br />
* [https://forge.softwareheritage.org/rDGRPHda493d254e45e528e3a55e59ef9d0bc518eaafe3 da493d254e45e528e3a55e59ef9d0bc518eaafe3]<br />
* [https://forge.softwareheritage.org/rDGRPHbcdce568a02c19bb012e52116de7f63aab2916d9 bcdce568a02c19bb012e52116de7f63aab2916d9]<br />
* [https://forge.softwareheritage.org/rDGRPH35d1b2244765b803d92785caccb253c3036d6019 35d1b2244765b803d92785caccb253c3036d6019]<br />
* [https://forge.softwareheritage.org/rDGRPHd12cc10289f8f89847ec1b7c5e9a44c6339f4fd0 d12cc10289f8f89847ec1b7c5e9a44c6339f4fd0]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression/Commit_list&diff=1113Google Summer of Code 2019/Graph compression/Commit list2019-08-27T19:23:01Z<p>Haltode: </p>
<hr />
<div>* b31d2e8 https://forge.softwareheritage.org/rDGRPHb31d2e86a80cf8b85d4bf51f30be8e463fe994e4<br />
* 0b46253 https://forge.softwareheritage.org/rDGRPH0b46253799f43a25a8528926052340f93a1a911b<br />
* c7363b0 https://forge.softwareheritage.org/rDGRPHc7363b064ae1ed52c271b9831b934cd196589c8e<br />
* b6c6e1e https://forge.softwareheritage.org/rDGRPHb6c6e1eec131a002a44e01cef17abb81ec958421<br />
* d5dcbfc https://forge.softwareheritage.org/rDGRPHd5dcbfcdf245777a8753ccc6ac5414e762605abe<br />
* 493a3b0 https://forge.softwareheritage.org/rDGRPH493a3b007b1f249092dc671abe591327622a058f<br />
* 7705d1c https://forge.softwareheritage.org/rDGRPH7705d1c8b8ccf165fd7bb0fb4ac87dc1050994c0<br />
* 101c50f https://forge.softwareheritage.org/rDGRPH101c50f2f10eb01ad08ee831fc70d140fae750fd<br />
* b1fdd01 https://forge.softwareheritage.org/rDGRPHb1fdd018fd5ad2fd95aa6d073e5058a64d570a2c<br />
* b0bcbe0 https://forge.softwareheritage.org/rDGRPHb0bcbe039d19a404a73052aae68f485328262ce3<br />
* 2bc36b7 https://forge.softwareheritage.org/rDGRPH2bc36b702416888c2155a88d129b8a07e124c1ac<br />
* 468a99d https://forge.softwareheritage.org/rDGRPH468a99dc4dd31a37681970fecf3bdb4413251f4b<br />
* d9e93fb https://forge.softwareheritage.org/rDGRPHd9e93fb46f5e6783282ff0160dca489bae9fc946<br />
* 30218b7 https://forge.softwareheritage.org/rDGRPH30218b7dc68f6a5eb8f842827d5a5b01fb252e53<br />
* b46335c https://forge.softwareheritage.org/rDGRPHb46335c0e77275a3c0357eb479008ced702a2b29<br />
* 4c08462 https://forge.softwareheritage.org/rDGRPH4c0846228465fb32c6fc2508f4beadee82433c18<br />
* 87192df https://forge.softwareheritage.org/rDGRPH87192dfddd4bbce01cedd9942df807977dfd70ef<br />
* 6a84a51 https://forge.softwareheritage.org/rDGRPH6a84a51b6f6a3d62edff4f7b885f63537999cdb6<br />
* 9b02f41 https://forge.softwareheritage.org/rDGRPH9b02f4137cb6154bd7c20ab87edde11ebdd4ae24<br />
* 2da9b1a https://forge.softwareheritage.org/rDGRPH2da9b1a05395a5dba8cf8317faca869872e2c22d<br />
* 258aaf2 https://forge.softwareheritage.org/rDGRPH258aaf24354a28553e23f7d890b373dc91640b96<br />
* 9ca54a8 https://forge.softwareheritage.org/rDGRPH9ca54a873d7af567274e151369850879fd414c37<br />
* 9ea36f0 https://forge.softwareheritage.org/rDGRPH9ea36f08ce24b6d229b4d8dff85693a37433ee89<br />
* 6aee508 https://forge.softwareheritage.org/rDGRPH6aee508c4cdf24789dc6c66a4b9568863a3c403c<br />
* 13d53c6 https://forge.softwareheritage.org/rDGRPH13d53c66452a5f3bc9f06bc99adf834e4ebda62b<br />
* 22b9258 https://forge.softwareheritage.org/rDGRPH22b9258fb2ccaeae5c0ab2efa3553fb19d62084b<br />
* fb57ec5 https://forge.softwareheritage.org/rDGRPHfb57ec5143a84a79cc22c67cd905da708029de81<br />
* f12a5aa https://forge.softwareheritage.org/rDGRPHf12a5aafff2696e94814d6453ed00f86991a831f<br />
* 88bfeda https://forge.softwareheritage.org/rDGRPH88bfedaf98833fdbe236b2d6bdb0da6272b95d30<br />
* 1fd382b https://forge.softwareheritage.org/rDGRPH1fd382b69889600686f65facd668fc9fa5bf0ce9<br />
* 8ff03d6 https://forge.softwareheritage.org/rDGRPH8ff03d608db64080d3fd45fdb54812fb5d314166<br />
* 7e1917a https://forge.softwareheritage.org/rDGRPH7e1917a236f32a5003507c9c73a848709982be27<br />
* 8f19048 https://forge.softwareheritage.org/rDGRPH8f19048ff75e0687a20751b3839ca18547bcba93<br />
* ba9b391 https://forge.softwareheritage.org/rDGRPHba9b3913c5a9a82f5242f6d630d0620da691ec9b<br />
* a495498 https://forge.softwareheritage.org/rDGRPHa495498689178f6f10caf1443443ccf73b7a2c35<br />
* 02e4f44 https://forge.softwareheritage.org/rDGRPH02e4f44f91e0ecbf6615a6c39bc93a7fa5389cd6<br />
* 81b6c00 https://forge.softwareheritage.org/rDGRPH81b6c0032c8c1649caa3eca95658d8d8eaa5448c<br />
* 78f18d0 https://forge.softwareheritage.org/rDGRPH78f18d06f734897f2f8bd1e1b0d29d613d8c8a39<br />
* f5d245f https://forge.softwareheritage.org/rDGRPHf5d245f4e312a85b9dfce647e8be1b2580b3897f<br />
* 403f1e0 https://forge.softwareheritage.org/rDGRPH403f1e010c3ee6b85708a3cf46fbe262d2a26061<br />
* 4013dbc https://forge.softwareheritage.org/rDGRPH4013dbc12e435719aa65f0684318a801a2a9d668<br />
* 223650e https://forge.softwareheritage.org/rDGRPH223650ed7e6a2e22ea717027beed25a2917767c3<br />
* c57819c https://forge.softwareheritage.org/rDGRPHc57819ce34ae7a85ba6deb6944744a5b830c8ed8<br />
* a098482 https://forge.softwareheritage.org/rDGRPHa098482cba3e50473c13987d536e920ab1a7994e<br />
* 293eb8a https://forge.softwareheritage.org/rDGRPH293eb8a57c9f0418eb00e1339094ab46af2fea42<br />
* 6c11866 https://forge.softwareheritage.org/rDGRPH6c1186676c462482e9e30de84696c9be37d436bc<br />
* 9353712 https://forge.softwareheritage.org/rDGRPH9353712815b994c984fa2ac8bb7184047f3c6cd9<br />
* 4ada70d https://forge.softwareheritage.org/rDGRPH4ada70da1ead40a9411419de20b725d2b43ef5a2<br />
* 981847b https://forge.softwareheritage.org/rDGRPH981847b49725196fa41ce8c9965c44553c50ea3f<br />
* e309e7f https://forge.softwareheritage.org/rDGRPHe309e7f4f3f1f3147d9c31228bc61112500a92d4<br />
* 442ef08 https://forge.softwareheritage.org/rDGRPH442ef0846cb0d66f007df3396ec8a52049940d59<br />
* a769e31 https://forge.softwareheritage.org/rDGRPHa769e313541d46f3a18de6abde85b62a8256f3cb<br />
* b884ff8 https://forge.softwareheritage.org/rDGRPHb884ff82ee09fd43e3ee801bc0627a0bcb665830<br />
* 93f1fb8 https://forge.softwareheritage.org/rDGRPH93f1fb8ed6b9f41cf0d53f351df79469aecaf79a<br />
* a8d4b62 https://forge.softwareheritage.org/rDGRPHa8d4b625d917062c9219838f324b019d8b46994a<br />
* ebfa631 https://forge.softwareheritage.org/rDGRPHebfa6310c5ab642a8df9ea9f14a8c1328efc1fc9<br />
* 0a81a04 https://forge.softwareheritage.org/rDGRPH0a81a047cfe3bfbfa5b74d6855e57dd1b1ddec75<br />
* fc9dd23 https://forge.softwareheritage.org/rDGRPHfc9dd235c28b12c1f2d569011fabaad194de1572<br />
* fc52d42 https://forge.softwareheritage.org/rDGRPHfc52d428ce14d56e13709505ccbfe35ee445d70c<br />
* 9413a20 https://forge.softwareheritage.org/rDGRPH9413a20afdf6aaba570de477a02630f8effb86ec<br />
* 56dead5 https://forge.softwareheritage.org/rDGRPH56dead50c511482b74bfbdc4911b9455f03084cc<br />
* 313eb76 https://forge.softwareheritage.org/rDGRPH313eb76cd39ea10fe4bf0b645fd30346da2ebe15<br />
* d56bfa8 https://forge.softwareheritage.org/rDGRPHd56bfa886d2e41cc29b60efeba7cb8146480f90a<br />
* 832272c https://forge.softwareheritage.org/rDGRPH832272c8e81ad48403cde27fba4190688c8f48be<br />
* edf9e6f https://forge.softwareheritage.org/rDGRPHedf9e6fa4b8680b7379f23519952747aeebb66c4<br />
* 61ee414 https://forge.softwareheritage.org/rDGRPH61ee41418867c36cdb4589ba92367b48d6c6140c<br />
* 025d694 https://forge.softwareheritage.org/rDGRPH025d694fd0aa1e6ad576398dbd9372bab9954d63<br />
* caf250d https://forge.softwareheritage.org/rDGRPHcaf250d2c008a41ef02cb0500cb93519fd10fd4e<br />
* 946d235 https://forge.softwareheritage.org/rDGRPH946d235ebdac58baac27a246dc93706645365ead<br />
* daa7cd8 https://forge.softwareheritage.org/rDGRPHdaa7cd8d7a0f7f4dd462256a4a13fa74b38344f5<br />
* 5bd8c80 https://forge.softwareheritage.org/rDGRPH5bd8c806c2ef5911ac021833d6d07d7eecf92268<br />
* 40914fa https://forge.softwareheritage.org/rDGRPH40914fa836651964554015368226d280a745ac0d<br />
* 2cdf7bb https://forge.softwareheritage.org/rDGRPH2cdf7bb658ade4caba3637b5ebdd79dedda9ac51<br />
* 9ab8989 https://forge.softwareheritage.org/rDGRPH9ab8989c633ad36461c605b92618b226a3c428bf<br />
* de6778f https://forge.softwareheritage.org/rDGRPHde6778f217965c684faccf2e95383bd20574e835<br />
* 01e3b66 https://forge.softwareheritage.org/rDGRPH01e3b661384484cf14971b903e8e473a299ed442<br />
* 0ad569d https://forge.softwareheritage.org/rDGRPH0ad569d7e71f2d85ca9047a204d58aabc33395d8<br />
* 6e9bb13 https://forge.softwareheritage.org/rDGRPH6e9bb13c272c33d66ef8db86680584b0301498c1<br />
* 3229cd6 https://forge.softwareheritage.org/rDGRPH3229cd64175ad5a2c456ab0bce5a611ffb28b303<br />
* 58abcb3 https://forge.softwareheritage.org/rDGRPH58abcb3f4e577d20a41b7e6f2e0d98c5ae959dfd<br />
* 27a2871 https://forge.softwareheritage.org/rDGRPH27a2871994e9c7655b5460373b113915b0a791f0<br />
* d04c698 https://forge.softwareheritage.org/rDGRPHd04c698a7f92e0621f6a8d5eab525b3faaa7fa32<br />
* 072e285 https://forge.softwareheritage.org/rDGRPH072e28513ce5303d30da9841a26cd046ee6b85ec<br />
* 51f8878 https://forge.softwareheritage.org/rDGRPH51f8878e7f4d40aeeb04c846cdf4098b9c27aa0b<br />
* 2f59c82 https://forge.softwareheritage.org/rDGRPH2f59c82262784f29900cf60876e4df9f2eb4653b<br />
* 8e99fa3 https://forge.softwareheritage.org/rDGRPH8e99fa365bda1756f773b5f074badc2ebf6fd2ac<br />
* d2fe190 https://forge.softwareheritage.org/rDGRPHd2fe1900f376864faf1ca26267e6af144459c232<br />
* 1444f74 https://forge.softwareheritage.org/rDGRPH1444f74820b45fdecc5470275ca5d2b85d600b0a<br />
* 5fe89bd https://forge.softwareheritage.org/rDGRPH5fe89bd242ab041d00125eb878d9d36c25933841<br />
* 0962071 https://forge.softwareheritage.org/rDGRPH096207105ee5e82fc2605b1bce6592c05499d1f7<br />
* bc75822 https://forge.softwareheritage.org/rDGRPHbc75822621a63d239fc5d53a0044531b9f514e96<br />
* 7297e65 https://forge.softwareheritage.org/rDGRPH7297e656af6353bd246c99390571ffdb97915fe5<br />
* 5bcfcca https://forge.softwareheritage.org/rDGRPH5bcfcca2c485cb1974ee95984e7bbeab597655aa<br />
* 48929ca https://forge.softwareheritage.org/rDGRPH48929cae3397cd4e01e647605bf493b976a50936<br />
* 19c3506 https://forge.softwareheritage.org/rDGRPH19c3506824e8a3dac7819075d4f3500915ccd236<br />
* 0c3db69 https://forge.softwareheritage.org/rDGRPH0c3db69256386134b1b494916d202ceae902e01b<br />
* 1d24b57 https://forge.softwareheritage.org/rDGRPH1d24b57634758ebe3a702038729e790d9ceeb24a<br />
* 4b122cb https://forge.softwareheritage.org/rDGRPH4b122cb96e453cea09fbaeff5abb6a45f2ac5500<br />
* 1e016ee https://forge.softwareheritage.org/rDGRPH1e016eec9cacaa35993604c51bc9d2cafe64203f<br />
* 03aeede https://forge.softwareheritage.org/rDGRPH03aeede55f124656c76e8f30e81edb7f0289a6b1<br />
* 1a59cc1 https://forge.softwareheritage.org/rDGRPH1a59cc1d611c0fa6fb7c3606915583426a50114d<br />
* b702bcb https://forge.softwareheritage.org/rDGRPHb702bcbcc505c5c5db10de36251d2e7d9ccafc85<br />
* 9ef0634 https://forge.softwareheritage.org/rDGRPH9ef0634ba95bede3db6ef6b4ad0e8537df815201<br />
* c18ac72 https://forge.softwareheritage.org/rDGRPHc18ac728550e26d3f5317b3d7bc74a7db46b1c1c<br />
* eeff1c1 https://forge.softwareheritage.org/rDGRPHeeff1c1b6b629fa4c51a655c4455a23463505556<br />
* 5158e27 https://forge.softwareheritage.org/rDGRPH5158e27d0e38dfb6ee5ac3e0cf99d134cdc0d824<br />
* 00b71f8 https://forge.softwareheritage.org/rDGRPH00b71f8a15544f7376e72b6783de4cc6d7c17c1c<br />
* 29be5dc https://forge.softwareheritage.org/rDGRPH29be5dc9dcf396e25b97d072d1000fb3b5ad5fd4<br />
* c310816 https://forge.softwareheritage.org/rDGRPHc3108160f157c82cca3802d0ebc62d33ec293b6a<br />
* 0af9c1c https://forge.softwareheritage.org/rDGRPH0af9c1cdf936853ca1982e4fb7577b2c799955f0<br />
* 69e2dd0 https://forge.softwareheritage.org/rDGRPH69e2dd06696bce1d30c76f7e3e1de8549ef03417<br />
* 494624e https://forge.softwareheritage.org/rDGRPH494624e7cc6246b7ee51b6480abfba8b88879a7e<br />
* 72f5d9f https://forge.softwareheritage.org/rDGRPH72f5d9f6744f8f2dfa81247d06a995ad34481659<br />
* 3012ced https://forge.softwareheritage.org/rDGRPH3012ced62560afcd53aa367bd3c529b0eda375db<br />
* d111806 https://forge.softwareheritage.org/rDGRPHd1118062ac65e05c7e51973b74ebda85409e8b51<br />
* a03efd5 https://forge.softwareheritage.org/rDGRPHa03efd5ecd1227298216536f34f5642027cc2979<br />
* e7a80f4 https://forge.softwareheritage.org/rDGRPHe7a80f4b392e3a6c93491d706ba3da55ea8dd8fc<br />
* 66b4068 https://forge.softwareheritage.org/rDGRPH66b4068e982685d8ba87b0de649de4f3b7e5695a<br />
* e98ccac https://forge.softwareheritage.org/rDGRPHe98ccac77252af30084016a657fcc27ee513b0b8<br />
* 0f35f18 https://forge.softwareheritage.org/rDGRPH0f35f18570acb9602434692195e9a7cea4958569<br />
* ce0ca93 https://forge.softwareheritage.org/rDGRPHce0ca93d412cbbdecab5858f93fd897b3401920b<br />
* 91b2ee9 https://forge.softwareheritage.org/rDGRPH91b2ee93b233b43e367ab8021782dec9536dd080<br />
* bbe69cd https://forge.softwareheritage.org/rDGRPHbbe69cd469bba76f195eabe56e6a4d761111ef66<br />
* 0276d1b https://forge.softwareheritage.org/rDGRPH0276d1bf474d6e3e46e104717625d108cfa04ada<br />
* a3016cd https://forge.softwareheritage.org/rDGRPHa3016cd837cbdbf328cb5703307e02a04b275976<br />
* 7c1cacd https://forge.softwareheritage.org/rDGRPH7c1cacd83f17fdcf5f30a903478b5e2bc1a710ac<br />
* 2bdba36 https://forge.softwareheritage.org/rDGRPH2bdba36a9ae59cbf290967783c6b0fdd63dc5c4e<br />
* 3fb9b44 https://forge.softwareheritage.org/rDGRPH3fb9b44ab6026afa57f7fee6087befd4d9215644<br />
* 675d163 https://forge.softwareheritage.org/rDGRPH675d1637c7d0ec128e4d0ccddd892be184c37b27<br />
* 927fc07 https://forge.softwareheritage.org/rDGRPH927fc070364246d132ede89b8af31da71406012d<br />
* 0987e9f https://forge.softwareheritage.org/rDGRPH0987e9fb6985067707b255aa6d957fe0b62b5d66<br />
* 5d25ebd https://forge.softwareheritage.org/rDGRPH5d25ebdd188f8ba80659f8e5e0724d236c579ce4<br />
* 2d64dae https://forge.softwareheritage.org/rDGRPH2d64daeacf61aa3c183e9f2371f6a0ed59032e0a<br />
* 58c2fe6 https://forge.softwareheritage.org/rDGRPH58c2fe6c4dae82a1db0cc4e92c15c00bf02776da<br />
* 1626a83 https://forge.softwareheritage.org/rDGRPH1626a831552e313bc7af61766bffc80d00106964<br />
* 674ccb9 https://forge.softwareheritage.org/rDGRPH674ccb9b65a9a19de1b7b8ea82be61d41df979aa<br />
* 3bb7372 https://forge.softwareheritage.org/rDGRPH3bb73725d03ec0f0d70811f299a3e369aeaa53ea<br />
* 7d06e5c https://forge.softwareheritage.org/rDGRPH7d06e5c21a62484009efac6714e666f79da91092<br />
* 5e877f7 https://forge.softwareheritage.org/rDGRPH5e877f798d4663b5b68d16e07de74a2a81e30911<br />
* b0fe602 https://forge.softwareheritage.org/rDGRPHb0fe60222c2713dcd1c366df71b7a0b333c794e6<br />
* 14a73c2 https://forge.softwareheritage.org/rDGRPH14a73c2e801f99d4bc551d9abd2b9d98115f5dd3<br />
* fa669aa https://forge.softwareheritage.org/rDGRPHfa669aae82737a1bc4496daf9fc78c03dea0f689<br />
* 006db06 https://forge.softwareheritage.org/rDGRPH006db063cbe7a1797684c6c0df015dfea52777fa<br />
* 97a7210 https://forge.softwareheritage.org/rDGRPH97a72106e6efe1ad828129eb2e2e4f2bd684d1ad<br />
* dfaaae9 https://forge.softwareheritage.org/rDGRPHdfaaae935f5a40dc8862d00fdbbc6eefb5bdab44<br />
* 3c61e93 https://forge.softwareheritage.org/rDGRPH3c61e93a2c02e997b0497f7471ada1e255ca98fc<br />
* 04f08f9 https://forge.softwareheritage.org/rDGRPH04f08f96594382623e139700fb0db9b8b6e42832<br />
* d55bbee https://forge.softwareheritage.org/rDGRPHd55bbeed351c36937bea90128395fe830d3b240b<br />
* 11430ec https://forge.softwareheritage.org/rDGRPH11430ec4febc86ec0ce2d43bbcd7394c9da3c7a1<br />
* 5095dcd https://forge.softwareheritage.org/rDGRPH5095dcdb74d067e6e7b53fb980b33cc076de5201<br />
* 71195a3 https://forge.softwareheritage.org/rDGRPH71195a3bc1d2761c9a1612d74cf014fd19db2339<br />
* 608679a https://forge.softwareheritage.org/rDGRPH608679a21b95cf45121ed26f81f809d5f5d79b55<br />
* 384312b https://forge.softwareheritage.org/rDGRPH384312b79b405ae868f6aa5fbb0271bad4766a8b<br />
* 4a7eb45 https://forge.softwareheritage.org/rDGRPH4a7eb4500647356c465c64d8e83beead448fe0e2<br />
* 5ff51ba https://forge.softwareheritage.org/rDGRPH5ff51bae7866adfeab85dea292adbedffea304dc<br />
* 6f96ffc https://forge.softwareheritage.org/rDGRPH6f96ffc672ca53559d89cf58dab8e5fc41e4e7c1<br />
* 83b0460 https://forge.softwareheritage.org/rDGRPH83b04605553e13e6604d30463986b3a56a6d6e5f<br />
* 542f7c6 https://forge.softwareheritage.org/rDGRPH542f7c68944e89d504d0415c89f3df5757077b75<br />
* 95cc98b https://forge.softwareheritage.org/rDGRPH95cc98bd2ef06ff94ffe32c7525028b226185a57<br />
* a06f5b5 https://forge.softwareheritage.org/rDGRPHa06f5b534e66668731eece4bf0d92fbb4c5a0688<br />
* 40d8bfa https://forge.softwareheritage.org/rDGRPH40d8bfa5b7f0d49fc7753784ba9dac49b7cbc912<br />
* ae3105a https://forge.softwareheritage.org/rDGRPHae3105a94e244c0d37118918a8143ade833d27ee<br />
* e39500b https://forge.softwareheritage.org/rDGRPHe39500bae4729dbe8c586a0565e3c074b53b0c3c<br />
* acd95e1 https://forge.softwareheritage.org/rDGRPHacd95e1f44c65679f32e6b0bffaf1baa124b3ade<br />
* 87ee23b https://forge.softwareheritage.org/rDGRPH87ee23bb8addabfd85a6e0ec1f89336da3868bb0<br />
* a49c343 https://forge.softwareheritage.org/rDGRPHa49c34399f4fbe44e97d61f80c515bf70b0a2b83<br />
* 63dc317 https://forge.softwareheritage.org/rDGRPH63dc317c44bb475dacc011b6482c1e6d2e85865b<br />
* 6621977 https://forge.softwareheritage.org/rDGRPH6621977ddf70437b20e6306a571824d7ab1541fc<br />
* 3b4ef31 https://forge.softwareheritage.org/rDGRPH3b4ef319c949c8a7191a940c2aacc4faa6c14acc<br />
* 6606fdf https://forge.softwareheritage.org/rDGRPH6606fdf1fbf50177c1b15e47f33801db2db853d1<br />
* c523be0 https://forge.softwareheritage.org/rDGRPHc523be098e9f8c4ff7868a955e240bbad9930c14<br />
* 1788535 https://forge.softwareheritage.org/rDGRPH1788535e8a308ecf72652d5843aa520702dc70e2<br />
* 5d2c648 https://forge.softwareheritage.org/rDGRPH5d2c6485095aabe30013afe55d0663670ec61120<br />
* 6c13efd https://forge.softwareheritage.org/rDGRPH6c13efd5d7fd9972a58b2e1b998c56ec2825b590<br />
* def9fed https://forge.softwareheritage.org/rDGRPHdef9fed92862a4e768d2f968922566c5039a67f2<br />
* 0b08fec https://forge.softwareheritage.org/rDGRPH0b08fec6d5aaec76493d7b8aa0a539a40b788f9f<br />
* 392fd15 https://forge.softwareheritage.org/rDGRPH392fd1520494ec008f638e38d96645a539711fbb<br />
* 36020e6 https://forge.softwareheritage.org/rDGRPH36020e626aa7c44154f417d9eb649b406c14c243<br />
* a994162 https://forge.softwareheritage.org/rDGRPHa994162aee75226c01312ef4a13a244d18c8e432<br />
* 616c759 https://forge.softwareheritage.org/rDGRPH616c759fcff0809bd4c00434c19bbf2b598be6a4<br />
* 76320b0 https://forge.softwareheritage.org/rDGRPH76320b0a8004708e59f1cdfdf3fbc3c47b1e951c<br />
* a47d546 https://forge.softwareheritage.org/rDGRPHa47d54676557cc544d85381c2f7c3a8cfe261bb6<br />
* b1d6442 https://forge.softwareheritage.org/rDGRPHb1d64422d30d70cd9026f207718ff564a09b9831<br />
* d5034a6 https://forge.softwareheritage.org/rDGRPHd5034a602c6ebb0a6530f3906a61ac425f1d4d70<br />
* da493d2 https://forge.softwareheritage.org/rDGRPHda493d254e45e528e3a55e59ef9d0bc518eaafe3<br />
* bcdce56 https://forge.softwareheritage.org/rDGRPHbcdce568a02c19bb012e52116de7f63aab2916d9<br />
* 35d1b22 https://forge.softwareheritage.org/rDGRPH35d1b2244765b803d92785caccb253c3036d6019<br />
* d12cc10 https://forge.softwareheritage.org/rDGRPHd12cc10289f8f89847ec1b7c5e9a44c6339f4fd0</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1112Google Summer of Code 2019/Graph compression2019-08-27T12:08:10Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with 12 billion nodes and 165 billion 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 GSoC project 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.<br />
<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
<br />
* '''What was done:'''<br />
** Git repo: [https://forge.softwareheritage.org/source/swh-graph/ swh-graph] (list of my [https://wiki.softwareheritage.org/wiki/Google_Summer_of_Code_2019/Graph_compression/Commit_list commits])<br />
** Research on graph compression: evaluate/experiment feasibility and compression rate of multiple techniques<br />
** Docker environment and scripts to automate the entire compression pipeline<br />
** REST API to query the graph<br />
*** Java server side: load the compressed graph, run API endpoints traversal algorithms, unit tests, javadoc<br />
*** Python client side: integration with SWH infrastructure, integration tests<br />
** Automated benchmarking tools with statistical analysis<br />
** General documentation on docker environment, compression steps, graph query use-cases, etc.<br />
<br />
* '''Highlights:'''<br />
** Compression rates: 4.48 bits/edge (transposed graph) and 4.91 bits/edge (direct graph)<br />
** Memory requirements for loading both graphs: 200GB of RAM<br />
** Total compression time: 1 week<br />
** Node successors lookup times: below 2μs<br />
<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00010.html week 2019/34]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression/Commit_list&diff=1111Google Summer of Code 2019/Graph compression/Commit list2019-08-27T12:07:46Z<p>Haltode: Created page with "* https://forge.softwareheritage.org/rDGRPHb31d2e86a80cf8b85d4bf51f30be8e463fe994e4 * https://forge.softwareheritage.org/rDGRPH0b46253799f43a25a8528926052340f93a1a911b * https..."</p>
<hr />
<div>* https://forge.softwareheritage.org/rDGRPHb31d2e86a80cf8b85d4bf51f30be8e463fe994e4<br />
* https://forge.softwareheritage.org/rDGRPH0b46253799f43a25a8528926052340f93a1a911b<br />
* https://forge.softwareheritage.org/rDGRPHc7363b064ae1ed52c271b9831b934cd196589c8e<br />
* https://forge.softwareheritage.org/rDGRPHb6c6e1eec131a002a44e01cef17abb81ec958421<br />
* https://forge.softwareheritage.org/rDGRPHd5dcbfcdf245777a8753ccc6ac5414e762605abe<br />
* https://forge.softwareheritage.org/rDGRPH493a3b007b1f249092dc671abe591327622a058f<br />
* https://forge.softwareheritage.org/rDGRPH7705d1c8b8ccf165fd7bb0fb4ac87dc1050994c0<br />
* https://forge.softwareheritage.org/rDGRPH101c50f2f10eb01ad08ee831fc70d140fae750fd<br />
* https://forge.softwareheritage.org/rDGRPHb1fdd018fd5ad2fd95aa6d073e5058a64d570a2c<br />
* https://forge.softwareheritage.org/rDGRPHb0bcbe039d19a404a73052aae68f485328262ce3<br />
* https://forge.softwareheritage.org/rDGRPH2bc36b702416888c2155a88d129b8a07e124c1ac<br />
* https://forge.softwareheritage.org/rDGRPH468a99dc4dd31a37681970fecf3bdb4413251f4b<br />
* https://forge.softwareheritage.org/rDGRPHd9e93fb46f5e6783282ff0160dca489bae9fc946<br />
* https://forge.softwareheritage.org/rDGRPH30218b7dc68f6a5eb8f842827d5a5b01fb252e53<br />
* https://forge.softwareheritage.org/rDGRPHb46335c0e77275a3c0357eb479008ced702a2b29<br />
* https://forge.softwareheritage.org/rDGRPH4c0846228465fb32c6fc2508f4beadee82433c18<br />
* https://forge.softwareheritage.org/rDGRPH87192dfddd4bbce01cedd9942df807977dfd70ef<br />
* https://forge.softwareheritage.org/rDGRPH6a84a51b6f6a3d62edff4f7b885f63537999cdb6<br />
* https://forge.softwareheritage.org/rDGRPH9b02f4137cb6154bd7c20ab87edde11ebdd4ae24<br />
* https://forge.softwareheritage.org/rDGRPH2da9b1a05395a5dba8cf8317faca869872e2c22d<br />
* https://forge.softwareheritage.org/rDGRPH258aaf24354a28553e23f7d890b373dc91640b96<br />
* https://forge.softwareheritage.org/rDGRPH9ca54a873d7af567274e151369850879fd414c37<br />
* https://forge.softwareheritage.org/rDGRPH9ea36f08ce24b6d229b4d8dff85693a37433ee89<br />
* https://forge.softwareheritage.org/rDGRPH6aee508c4cdf24789dc6c66a4b9568863a3c403c<br />
* https://forge.softwareheritage.org/rDGRPH13d53c66452a5f3bc9f06bc99adf834e4ebda62b<br />
* https://forge.softwareheritage.org/rDGRPH22b9258fb2ccaeae5c0ab2efa3553fb19d62084b<br />
* https://forge.softwareheritage.org/rDGRPHfb57ec5143a84a79cc22c67cd905da708029de81<br />
* https://forge.softwareheritage.org/rDGRPHf12a5aafff2696e94814d6453ed00f86991a831f<br />
* https://forge.softwareheritage.org/rDGRPH88bfedaf98833fdbe236b2d6bdb0da6272b95d30<br />
* https://forge.softwareheritage.org/rDGRPH1fd382b69889600686f65facd668fc9fa5bf0ce9<br />
* https://forge.softwareheritage.org/rDGRPH8ff03d608db64080d3fd45fdb54812fb5d314166<br />
* https://forge.softwareheritage.org/rDGRPH7e1917a236f32a5003507c9c73a848709982be27<br />
* https://forge.softwareheritage.org/rDGRPH8f19048ff75e0687a20751b3839ca18547bcba93<br />
* https://forge.softwareheritage.org/rDGRPHba9b3913c5a9a82f5242f6d630d0620da691ec9b<br />
* https://forge.softwareheritage.org/rDGRPHa495498689178f6f10caf1443443ccf73b7a2c35<br />
* https://forge.softwareheritage.org/rDGRPH02e4f44f91e0ecbf6615a6c39bc93a7fa5389cd6<br />
* https://forge.softwareheritage.org/rDGRPH81b6c0032c8c1649caa3eca95658d8d8eaa5448c<br />
* https://forge.softwareheritage.org/rDGRPH78f18d06f734897f2f8bd1e1b0d29d613d8c8a39<br />
* https://forge.softwareheritage.org/rDGRPHf5d245f4e312a85b9dfce647e8be1b2580b3897f<br />
* https://forge.softwareheritage.org/rDGRPH403f1e010c3ee6b85708a3cf46fbe262d2a26061<br />
* https://forge.softwareheritage.org/rDGRPH4013dbc12e435719aa65f0684318a801a2a9d668<br />
* https://forge.softwareheritage.org/rDGRPH223650ed7e6a2e22ea717027beed25a2917767c3<br />
* https://forge.softwareheritage.org/rDGRPHc57819ce34ae7a85ba6deb6944744a5b830c8ed8<br />
* https://forge.softwareheritage.org/rDGRPHa098482cba3e50473c13987d536e920ab1a7994e<br />
* https://forge.softwareheritage.org/rDGRPH293eb8a57c9f0418eb00e1339094ab46af2fea42<br />
* https://forge.softwareheritage.org/rDGRPH6c1186676c462482e9e30de84696c9be37d436bc<br />
* https://forge.softwareheritage.org/rDGRPH9353712815b994c984fa2ac8bb7184047f3c6cd9<br />
* https://forge.softwareheritage.org/rDGRPH4ada70da1ead40a9411419de20b725d2b43ef5a2<br />
* https://forge.softwareheritage.org/rDGRPH981847b49725196fa41ce8c9965c44553c50ea3f<br />
* https://forge.softwareheritage.org/rDGRPHe309e7f4f3f1f3147d9c31228bc61112500a92d4<br />
* https://forge.softwareheritage.org/rDGRPH442ef0846cb0d66f007df3396ec8a52049940d59<br />
* https://forge.softwareheritage.org/rDGRPHa769e313541d46f3a18de6abde85b62a8256f3cb<br />
* https://forge.softwareheritage.org/rDGRPHb884ff82ee09fd43e3ee801bc0627a0bcb665830<br />
* https://forge.softwareheritage.org/rDGRPH93f1fb8ed6b9f41cf0d53f351df79469aecaf79a<br />
* https://forge.softwareheritage.org/rDGRPHa8d4b625d917062c9219838f324b019d8b46994a<br />
* https://forge.softwareheritage.org/rDGRPHebfa6310c5ab642a8df9ea9f14a8c1328efc1fc9<br />
* https://forge.softwareheritage.org/rDGRPH0a81a047cfe3bfbfa5b74d6855e57dd1b1ddec75<br />
* https://forge.softwareheritage.org/rDGRPHfc9dd235c28b12c1f2d569011fabaad194de1572<br />
* https://forge.softwareheritage.org/rDGRPHfc52d428ce14d56e13709505ccbfe35ee445d70c<br />
* https://forge.softwareheritage.org/rDGRPH9413a20afdf6aaba570de477a02630f8effb86ec<br />
* https://forge.softwareheritage.org/rDGRPH56dead50c511482b74bfbdc4911b9455f03084cc<br />
* https://forge.softwareheritage.org/rDGRPH313eb76cd39ea10fe4bf0b645fd30346da2ebe15<br />
* https://forge.softwareheritage.org/rDGRPHd56bfa886d2e41cc29b60efeba7cb8146480f90a<br />
* https://forge.softwareheritage.org/rDGRPHedf9e6fa4b8680b7379f23519952747aeebb66c4<br />
* https://forge.softwareheritage.org/rDGRPH61ee41418867c36cdb4589ba92367b48d6c6140c<br />
* https://forge.softwareheritage.org/rDGRPH025d694fd0aa1e6ad576398dbd9372bab9954d63<br />
* https://forge.softwareheritage.org/rDGRPHcaf250d2c008a41ef02cb0500cb93519fd10fd4e<br />
* https://forge.softwareheritage.org/rDGRPH946d235ebdac58baac27a246dc93706645365ead<br />
* https://forge.softwareheritage.org/rDGRPHdaa7cd8d7a0f7f4dd462256a4a13fa74b38344f5<br />
* https://forge.softwareheritage.org/rDGRPH5bd8c806c2ef5911ac021833d6d07d7eecf92268<br />
* https://forge.softwareheritage.org/rDGRPH40914fa836651964554015368226d280a745ac0d<br />
* https://forge.softwareheritage.org/rDGRPH2cdf7bb658ade4caba3637b5ebdd79dedda9ac51<br />
* https://forge.softwareheritage.org/rDGRPH9ab8989c633ad36461c605b92618b226a3c428bf<br />
* https://forge.softwareheritage.org/rDGRPHde6778f217965c684faccf2e95383bd20574e835<br />
* https://forge.softwareheritage.org/rDGRPH01e3b661384484cf14971b903e8e473a299ed442<br />
* https://forge.softwareheritage.org/rDGRPH0ad569d7e71f2d85ca9047a204d58aabc33395d8<br />
* https://forge.softwareheritage.org/rDGRPH6e9bb13c272c33d66ef8db86680584b0301498c1<br />
* https://forge.softwareheritage.org/rDGRPH3229cd64175ad5a2c456ab0bce5a611ffb28b303<br />
* https://forge.softwareheritage.org/rDGRPH27a2871994e9c7655b5460373b113915b0a791f0<br />
* https://forge.softwareheritage.org/rDGRPHd04c698a7f92e0621f6a8d5eab525b3faaa7fa32<br />
* https://forge.softwareheritage.org/rDGRPH072e28513ce5303d30da9841a26cd046ee6b85ec<br />
* https://forge.softwareheritage.org/rDGRPH51f8878e7f4d40aeeb04c846cdf4098b9c27aa0b<br />
* https://forge.softwareheritage.org/rDGRPH2f59c82262784f29900cf60876e4df9f2eb4653b<br />
* https://forge.softwareheritage.org/rDGRPH8e99fa365bda1756f773b5f074badc2ebf6fd2ac<br />
* https://forge.softwareheritage.org/rDGRPHd2fe1900f376864faf1ca26267e6af144459c232<br />
* https://forge.softwareheritage.org/rDGRPH1444f74820b45fdecc5470275ca5d2b85d600b0a<br />
* https://forge.softwareheritage.org/rDGRPH5fe89bd242ab041d00125eb878d9d36c25933841<br />
* https://forge.softwareheritage.org/rDGRPH096207105ee5e82fc2605b1bce6592c05499d1f7<br />
* https://forge.softwareheritage.org/rDGRPHbc75822621a63d239fc5d53a0044531b9f514e96<br />
* https://forge.softwareheritage.org/rDGRPH7297e656af6353bd246c99390571ffdb97915fe5<br />
* https://forge.softwareheritage.org/rDGRPH5bcfcca2c485cb1974ee95984e7bbeab597655aa<br />
* https://forge.softwareheritage.org/rDGRPH48929cae3397cd4e01e647605bf493b976a50936<br />
* https://forge.softwareheritage.org/rDGRPH19c3506824e8a3dac7819075d4f3500915ccd236<br />
* https://forge.softwareheritage.org/rDGRPH0c3db69256386134b1b494916d202ceae902e01b<br />
* https://forge.softwareheritage.org/rDGRPH1d24b57634758ebe3a702038729e790d9ceeb24a<br />
* https://forge.softwareheritage.org/rDGRPH4b122cb96e453cea09fbaeff5abb6a45f2ac5500<br />
* https://forge.softwareheritage.org/rDGRPH1e016eec9cacaa35993604c51bc9d2cafe64203f<br />
* https://forge.softwareheritage.org/rDGRPH03aeede55f124656c76e8f30e81edb7f0289a6b1<br />
* https://forge.softwareheritage.org/rDGRPH1a59cc1d611c0fa6fb7c3606915583426a50114d<br />
* https://forge.softwareheritage.org/rDGRPHb702bcbcc505c5c5db10de36251d2e7d9ccafc85<br />
* https://forge.softwareheritage.org/rDGRPH9ef0634ba95bede3db6ef6b4ad0e8537df815201<br />
* https://forge.softwareheritage.org/rDGRPHc18ac728550e26d3f5317b3d7bc74a7db46b1c1c<br />
* https://forge.softwareheritage.org/rDGRPHeeff1c1b6b629fa4c51a655c4455a23463505556<br />
* https://forge.softwareheritage.org/rDGRPH5158e27d0e38dfb6ee5ac3e0cf99d134cdc0d824<br />
* https://forge.softwareheritage.org/rDGRPH00b71f8a15544f7376e72b6783de4cc6d7c17c1c<br />
* https://forge.softwareheritage.org/rDGRPH29be5dc9dcf396e25b97d072d1000fb3b5ad5fd4<br />
* https://forge.softwareheritage.org/rDGRPHc3108160f157c82cca3802d0ebc62d33ec293b6a<br />
* https://forge.softwareheritage.org/rDGRPH0af9c1cdf936853ca1982e4fb7577b2c799955f0<br />
* https://forge.softwareheritage.org/rDGRPH69e2dd06696bce1d30c76f7e3e1de8549ef03417<br />
* https://forge.softwareheritage.org/rDGRPH494624e7cc6246b7ee51b6480abfba8b88879a7e<br />
* https://forge.softwareheritage.org/rDGRPH72f5d9f6744f8f2dfa81247d06a995ad34481659<br />
* https://forge.softwareheritage.org/rDGRPH3012ced62560afcd53aa367bd3c529b0eda375db<br />
* https://forge.softwareheritage.org/rDGRPHd1118062ac65e05c7e51973b74ebda85409e8b51<br />
* https://forge.softwareheritage.org/rDGRPHa03efd5ecd1227298216536f34f5642027cc2979<br />
* https://forge.softwareheritage.org/rDGRPHe7a80f4b392e3a6c93491d706ba3da55ea8dd8fc<br />
* https://forge.softwareheritage.org/rDGRPH66b4068e982685d8ba87b0de649de4f3b7e5695a<br />
* https://forge.softwareheritage.org/rDGRPHe98ccac77252af30084016a657fcc27ee513b0b8<br />
* https://forge.softwareheritage.org/rDGRPH0f35f18570acb9602434692195e9a7cea4958569<br />
* https://forge.softwareheritage.org/rDGRPHce0ca93d412cbbdecab5858f93fd897b3401920b<br />
* https://forge.softwareheritage.org/rDGRPH91b2ee93b233b43e367ab8021782dec9536dd080<br />
* https://forge.softwareheritage.org/rDGRPHbbe69cd469bba76f195eabe56e6a4d761111ef66<br />
* https://forge.softwareheritage.org/rDGRPH0276d1bf474d6e3e46e104717625d108cfa04ada<br />
* https://forge.softwareheritage.org/rDGRPHa3016cd837cbdbf328cb5703307e02a04b275976<br />
* https://forge.softwareheritage.org/rDGRPH7c1cacd83f17fdcf5f30a903478b5e2bc1a710ac<br />
* https://forge.softwareheritage.org/rDGRPH2bdba36a9ae59cbf290967783c6b0fdd63dc5c4e<br />
* https://forge.softwareheritage.org/rDGRPH3fb9b44ab6026afa57f7fee6087befd4d9215644<br />
* https://forge.softwareheritage.org/rDGRPH675d1637c7d0ec128e4d0ccddd892be184c37b27<br />
* https://forge.softwareheritage.org/rDGRPH927fc070364246d132ede89b8af31da71406012d<br />
* https://forge.softwareheritage.org/rDGRPH0987e9fb6985067707b255aa6d957fe0b62b5d66<br />
* https://forge.softwareheritage.org/rDGRPH5d25ebdd188f8ba80659f8e5e0724d236c579ce4<br />
* https://forge.softwareheritage.org/rDGRPH2d64daeacf61aa3c183e9f2371f6a0ed59032e0a<br />
* https://forge.softwareheritage.org/rDGRPH58c2fe6c4dae82a1db0cc4e92c15c00bf02776da<br />
* https://forge.softwareheritage.org/rDGRPH1626a831552e313bc7af61766bffc80d00106964<br />
* https://forge.softwareheritage.org/rDGRPH674ccb9b65a9a19de1b7b8ea82be61d41df979aa<br />
* https://forge.softwareheritage.org/rDGRPH3bb73725d03ec0f0d70811f299a3e369aeaa53ea<br />
* https://forge.softwareheritage.org/rDGRPH7d06e5c21a62484009efac6714e666f79da91092<br />
* https://forge.softwareheritage.org/rDGRPH5e877f798d4663b5b68d16e07de74a2a81e30911<br />
* https://forge.softwareheritage.org/rDGRPHb0fe60222c2713dcd1c366df71b7a0b333c794e6<br />
* https://forge.softwareheritage.org/rDGRPH14a73c2e801f99d4bc551d9abd2b9d98115f5dd3<br />
* https://forge.softwareheritage.org/rDGRPHfa669aae82737a1bc4496daf9fc78c03dea0f689<br />
* https://forge.softwareheritage.org/rDGRPH006db063cbe7a1797684c6c0df015dfea52777fa<br />
* https://forge.softwareheritage.org/rDGRPH97a72106e6efe1ad828129eb2e2e4f2bd684d1ad<br />
* https://forge.softwareheritage.org/rDGRPHdfaaae935f5a40dc8862d00fdbbc6eefb5bdab44<br />
* https://forge.softwareheritage.org/rDGRPH3c61e93a2c02e997b0497f7471ada1e255ca98fc<br />
* https://forge.softwareheritage.org/rDGRPH04f08f96594382623e139700fb0db9b8b6e42832<br />
* https://forge.softwareheritage.org/rDGRPHd55bbeed351c36937bea90128395fe830d3b240b<br />
* https://forge.softwareheritage.org/rDGRPH11430ec4febc86ec0ce2d43bbcd7394c9da3c7a1<br />
* https://forge.softwareheritage.org/rDGRPH5095dcdb74d067e6e7b53fb980b33cc076de5201<br />
* https://forge.softwareheritage.org/rDGRPH71195a3bc1d2761c9a1612d74cf014fd19db2339<br />
* https://forge.softwareheritage.org/rDGRPH608679a21b95cf45121ed26f81f809d5f5d79b55<br />
* https://forge.softwareheritage.org/rDGRPH384312b79b405ae868f6aa5fbb0271bad4766a8b<br />
* https://forge.softwareheritage.org/rDGRPH4a7eb4500647356c465c64d8e83beead448fe0e2<br />
* https://forge.softwareheritage.org/rDGRPH5ff51bae7866adfeab85dea292adbedffea304dc<br />
* https://forge.softwareheritage.org/rDGRPH6f96ffc672ca53559d89cf58dab8e5fc41e4e7c1<br />
* https://forge.softwareheritage.org/rDGRPH83b04605553e13e6604d30463986b3a56a6d6e5f<br />
* https://forge.softwareheritage.org/rDGRPH542f7c68944e89d504d0415c89f3df5757077b75<br />
* https://forge.softwareheritage.org/rDGRPH95cc98bd2ef06ff94ffe32c7525028b226185a57<br />
* https://forge.softwareheritage.org/rDGRPHa06f5b534e66668731eece4bf0d92fbb4c5a0688<br />
* https://forge.softwareheritage.org/rDGRPH40d8bfa5b7f0d49fc7753784ba9dac49b7cbc912<br />
* https://forge.softwareheritage.org/rDGRPHae3105a94e244c0d37118918a8143ade833d27ee<br />
* https://forge.softwareheritage.org/rDGRPHe39500bae4729dbe8c586a0565e3c074b53b0c3c<br />
* https://forge.softwareheritage.org/rDGRPHacd95e1f44c65679f32e6b0bffaf1baa124b3ade<br />
* https://forge.softwareheritage.org/rDGRPH87ee23bb8addabfd85a6e0ec1f89336da3868bb0<br />
* https://forge.softwareheritage.org/rDGRPHa49c34399f4fbe44e97d61f80c515bf70b0a2b83<br />
* https://forge.softwareheritage.org/rDGRPH63dc317c44bb475dacc011b6482c1e6d2e85865b<br />
* https://forge.softwareheritage.org/rDGRPH6621977ddf70437b20e6306a571824d7ab1541fc<br />
* https://forge.softwareheritage.org/rDGRPH3b4ef319c949c8a7191a940c2aacc4faa6c14acc<br />
* https://forge.softwareheritage.org/rDGRPH6606fdf1fbf50177c1b15e47f33801db2db853d1<br />
* https://forge.softwareheritage.org/rDGRPHc523be098e9f8c4ff7868a955e240bbad9930c14<br />
* https://forge.softwareheritage.org/rDGRPH1788535e8a308ecf72652d5843aa520702dc70e2<br />
* https://forge.softwareheritage.org/rDGRPH5d2c6485095aabe30013afe55d0663670ec61120<br />
* https://forge.softwareheritage.org/rDGRPH6c13efd5d7fd9972a58b2e1b998c56ec2825b590<br />
* https://forge.softwareheritage.org/rDGRPHdef9fed92862a4e768d2f968922566c5039a67f2<br />
* https://forge.softwareheritage.org/rDGRPH0b08fec6d5aaec76493d7b8aa0a539a40b788f9f<br />
* https://forge.softwareheritage.org/rDGRPH392fd1520494ec008f638e38d96645a539711fbb<br />
* https://forge.softwareheritage.org/rDGRPH36020e626aa7c44154f417d9eb649b406c14c243<br />
* https://forge.softwareheritage.org/rDGRPHa994162aee75226c01312ef4a13a244d18c8e432<br />
* https://forge.softwareheritage.org/rDGRPH616c759fcff0809bd4c00434c19bbf2b598be6a4<br />
* https://forge.softwareheritage.org/rDGRPH76320b0a8004708e59f1cdfdf3fbc3c47b1e951c<br />
* https://forge.softwareheritage.org/rDGRPHa47d54676557cc544d85381c2f7c3a8cfe261bb6<br />
* https://forge.softwareheritage.org/rDGRPHb1d64422d30d70cd9026f207718ff564a09b9831<br />
* https://forge.softwareheritage.org/rDGRPHd5034a602c6ebb0a6530f3906a61ac425f1d4d70<br />
* https://forge.softwareheritage.org/rDGRPHda493d254e45e528e3a55e59ef9d0bc518eaafe3<br />
* https://forge.softwareheritage.org/rDGRPHbcdce568a02c19bb012e52116de7f63aab2916d9<br />
* https://forge.softwareheritage.org/rDGRPH35d1b2244765b803d92785caccb253c3036d6019<br />
* https://forge.softwareheritage.org/rDGRPHd12cc10289f8f89847ec1b7c5e9a44c6339f4fd0</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1102Google Summer of Code 2019/Graph compression2019-08-23T18:31:20Z<p>Haltode: Add weekly report 2019/34</p>
<hr />
<div>* '''Title:''' Graph compression<br />
<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with 12 billion nodes and 165 billion 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 GSoC project 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.<br />
<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
<br />
* '''What was done:'''<br />
** Git repo: [https://forge.softwareheritage.org/source/swh-graph/ swh-graph] (list of my [https://forge.softwareheritage.org/people/commits/257/ commits])<br />
** Research on graph compression: evaluate/experiment feasibility and compression rate of multiple techniques<br />
** Docker environment and scripts to automate the entire compression pipeline<br />
** REST API to query the graph<br />
*** Java server side: load the compressed graph, run API endpoints traversal algorithms, unit tests, javadoc<br />
*** Python client side: integration with SWH infrastructure, integration tests<br />
** Automated benchmarking tools with statistical analysis<br />
** General documentation on docker environment, compression steps, graph query use-cases, etc.<br />
<br />
* '''Highlights:'''<br />
** Compression rates: 4.48 bits/edge (transposed graph) and 4.91 bits/edge (direct graph)<br />
** Memory requirements for loading both graphs: 200GB of RAM<br />
** Total compression time: 1 week<br />
** Node successors lookup times: below 2μs<br />
<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00010.html week 2019/34]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1097Google Summer of Code 2019/Graph compression2019-08-22T12:01:43Z<p>Haltode: Add 'highlights' section</p>
<hr />
<div>* '''Title:''' Graph compression<br />
<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with 12 billion nodes and 165 billion 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 GSoC project 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.<br />
<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
<br />
* '''What was done:'''<br />
** Git repo: [https://forge.softwareheritage.org/source/swh-graph/ swh-graph] (list of my [https://forge.softwareheritage.org/people/commits/257/ commits])<br />
** Research on graph compression: evaluate/experiment feasibility and compression rate of multiple techniques<br />
** Docker environment and scripts to automate the entire compression pipeline<br />
** REST API to query the graph<br />
*** Java server side: load the compressed graph, run API endpoints traversal algorithms, unit tests, javadoc<br />
*** Python client side: integration with SWH infrastructure, integration tests<br />
** Automated benchmarking tools with statistical analysis<br />
** General documentation on docker environment, compression steps, graph query use-cases, etc.<br />
<br />
* '''Highlights:'''<br />
** Compression rates: 4.48 bits/edge (transposed graph) and 4.91 bits/edge (direct graph)<br />
** Memory requirements for loading both graphs: 200GB of RAM<br />
** Total compression time: 1 week<br />
** Node successors lookup times: below 2μs<br />
<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1096Google Summer of Code 2019/Graph compression2019-08-22T11:54:51Z<p>Haltode: Add 'what was done' section</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with 12 billion nodes and 165 billion 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 GSoC project 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.<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
* '''What was done:'''<br />
** Git repo: [https://forge.softwareheritage.org/source/swh-graph/ swh-graph] (list of my [https://forge.softwareheritage.org/people/commits/257/ commits])<br />
** Research on graph compression: evaluate/experiment feasibility and compression rate of multiple techniques<br />
** Docker environment and scripts to automate the entire compression pipeline<br />
** REST API to query the graph<br />
*** Java server side: load the compressed graph, run API endpoints traversal algorithms, unit tests, javadoc<br />
*** Python client side: integration with SWH infrastructure, integration tests<br />
** Automated benchmarking tools with statistical analysis<br />
** General documentation on docker environment, compression steps, graph query use-cases, etc.<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1095Google Summer of Code 2019/Graph compression2019-08-21T19:14:23Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with 12 billion nodes and 165 billion 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 GSoC project 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.<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
* '''Code:'''<br />
** [https://forge.softwareheritage.org/source/swh-graph/ swh-graph git]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1091Google Summer of Code 2019/Graph compression2019-08-21T08:54:07Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault 'haltode' Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
* '''Code:'''<br />
** [https://forge.softwareheritage.org/source/swh-graph/ swh-graph git]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1090Google Summer of Code 2019/Graph compression2019-08-21T08:23:38Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
** [https://summerofcode.withgoogle.com/projects/#4670175868092416 project on the GSoC portal]<br />
* '''Code:'''<br />
** [https://forge.softwareheritage.org/source/swh-graph/ swh-graph git]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1089Google Summer of Code 2019/Graph compression2019-08-19T12:03:59Z<p>Haltode: Add swh-graph git repo</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Code:'''<br />
** [https://forge.softwareheritage.org/source/swh-graph/ swh-graph git]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1086Google Summer of Code 2019/Graph compression2019-08-16T18:09:01Z<p>Haltode: Add weekly report 2019/33</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00006.html week 2019/33]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1084Google Summer of Code 2019/Graph compression2019-08-10T21:02:18Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00003.html week 2019/32]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1083Google Summer of Code 2019/Graph compression2019-08-10T21:01:53Z<p>Haltode: Add weekly report 2019/32</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00004.html week 2019/32]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1082Google Summer of Code 2019/Graph compression2019-08-03T08:25:51Z<p>Haltode: Add weekly report 2019/31</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
** August 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-08/msg00000.html week 2019/31]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1077Google Summer of Code 2019/Graph compression2019-07-19T06:58:49Z<p>Haltode: Add weekly report 2019/29</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00009.html week 2019/29]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1074Google Summer of Code 2019/Graph compression2019-07-12T20:33:08Z<p>Haltode: Add weekly report 2019/28</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00005.html week 2019/28]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1065Google Summer of Code 2019/Graph compression2019-07-05T14:02:27Z<p>Haltode: Add weekly report 2019/27</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
** July 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-07/msg00001.html week 2019/27]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1064Google Summer of Code 2019/Graph compression2019-06-28T15:16:58Z<p>Haltode: Add weekly report 2019/26</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00031.html week 2019/26]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1061Google Summer of Code 2019/Graph compression2019-06-21T09:18:12Z<p>Haltode: Add weekly report 2019/25</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00023.html week 2019/25]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1058Google Summer of Code 2019/Graph compression2019-06-14T07:17:11Z<p>Haltode: Add weekly report 2019/24</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00013.html week 2019/24]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1057Google Summer of Code 2019/Graph compression2019-06-12T03:54:18Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~10 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1056Google Summer of Code 2019/Graph compression2019-06-10T10:51:32Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
** June 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1055Google Summer of Code 2019/Graph compression2019-06-10T05:07:48Z<p>Haltode: Add weekly report 2019/23</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-06/msg00007.html week 2019/23]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1053Google Summer of Code 2019/Graph compression2019-06-03T09:14:30Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May 2019<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1052Google Summer of Code 2019/Graph compression2019-06-03T09:14:19Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** May<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
*** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1051Google Summer of Code 2019/Graph compression2019-05-31T10:33:06Z<p>Haltode: Add weekly report 2019/22</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00015.html week 2019/22]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1047Google Summer of Code 2019/Graph compression2019-05-24T12:44:27Z<p>Haltode: Add weekly recap III</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00005.html week 2019/21]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1044Google Summer of Code 2019/Graph compression2019-05-20T05:27:15Z<p>Haltode: Add weekly recap II</p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00002.html week 2019/20]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1043Google Summer of Code 2019/Graph compression2019-05-16T03:35:07Z<p>Haltode: </p>
<hr />
<div>* '''Title:''' Graph compression<br />
* '''Description:''' The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree Merkle] DAG made of nodes like revisions, releases, directories, etc. It is a very big graph, with ~17 B nodes and ~160 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 GSoC project 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.<br />
* '''Student:''' Thibault Allançon<br />
** [https://forge.softwareheritage.org/p/haltode/ forge activity]<br />
* '''Mentors:'''<br />
** [[User:StefanoZacchiroli|Stefano Zacchiroli]]<br />
** Antoine Pietri<br />
* '''Activity reports:'''<br />
** [https://haltode.fr/gsoc2019/march.html March 2019]<br />
** [https://haltode.fr/gsoc2019/april.html April 2019]<br />
** [https://sympa.inria.fr/sympa/arc/swh-devel/2019-05/msg00000.html week 2019/19]<br />
<br />
== Links ==<br />
<br />
* [https://forge.softwareheritage.org/source/graph-compression/ source code repository]<br />
* see project [https://summerofcode.withgoogle.com/projects/#4670175868092416 on the GSoC portal]<br />
<br />
<br />
[[Category:Google Summer of Code]]<br />
[[Category:Google Summer of Code 2019]]</div>Haltodehttps://wiki.softwareheritage.org/index.php?title=Google_Summer_of_Code_2019/Graph_compression&diff=1025Google Summer of Code 2019/Graph compression2019-05-09T08:49:12Z<p>Haltode: Add graph compression subject</p>
<hr />
<div>= Subject =<br />
<br />
[https://www.softwareheritage.org/ 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.<br />
<br />
The Software Heritage [https://docs.softwareheritage.org/devel/swh-model/data-model.html data model] is a big [https://en.wikipedia.org/wiki/Merkle_tree 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 GSoC 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.</div>Haltode