diff --git a/java/pom.xml b/java/pom.xml
index cd1eece..0b2172e 100644
--- a/java/pom.xml
+++ b/java/pom.xml
@@ -1,269 +1,274 @@
 <?xml version="1.0" encoding="UTF-8"?>
 
 <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
          xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
   <modelVersion>4.0.0</modelVersion>
 
   <groupId>org.softwareheritage.graph</groupId>
   <artifactId>swh-graph</artifactId>
   <version>${git.closest.tag.name}</version>
 
   <name>swh-graph</name>
   <url>https://forge.softwareheritage.org/source/swh-graph/</url>
 
   <properties>
     <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
     <maven.compiler.release>11</maven.compiler.release>
   </properties>
 
   <dependencies>
     <dependency>
       <groupId>ch.qos.logback</groupId>
       <artifactId>logback-classic</artifactId>
       <version>1.2.3</version>
     </dependency>
     <dependency>
       <groupId>org.junit.jupiter</groupId>
       <artifactId>junit-jupiter-api</artifactId>
       <version>5.7.0</version>
       <scope>test</scope>
     </dependency>
     <dependency>
         <groupId>org.junit.jupiter</groupId>
         <artifactId>junit-jupiter-engine</artifactId>
         <version>5.7.0</version>
         <scope>test</scope>
     </dependency>
     <dependency>
       <groupId>org.hamcrest</groupId>
       <artifactId>hamcrest</artifactId>
       <version>2.1</version>
       <scope>test</scope>
     </dependency>
     <dependency>
       <groupId>io.javalin</groupId>
       <artifactId>javalin</artifactId>
       <version>3.0.0</version>
     </dependency>
     <dependency>
       <groupId>org.slf4j</groupId>
       <artifactId>slf4j-simple</artifactId>
       <version>1.7.26</version>
     </dependency>
     <dependency>
       <groupId>com.fasterxml.jackson.core</groupId>
       <artifactId>jackson-databind</artifactId>
       <version>2.9.8</version>
     </dependency>
     <dependency>
       <groupId>it.unimi.dsi</groupId>
       <artifactId>webgraph-big</artifactId>
-      <version>3.6.5</version>
+      <version>3.6.6</version>
     </dependency>
     <dependency>
       <groupId>it.unimi.dsi</groupId>
       <artifactId>fastutil</artifactId>
       <version>8.4.4</version>
     </dependency>
     <dependency>
       <groupId>it.unimi.dsi</groupId>
       <artifactId>dsiutils</artifactId>
-      <version>2.6.16</version>
+      <version>2.6.17</version>
+    </dependency>
+    <dependency>
+        <groupId>it.unimi.dsi</groupId>
+        <artifactId>sux4j</artifactId>
+        <version>5.2.3</version>
     </dependency>
     <dependency>
       <groupId>it.unimi.dsi</groupId>
       <artifactId>law</artifactId>
       <version>2.7.1</version>
       <exclusions>
         <exclusion>
           <groupId>org.apache.hadoop</groupId>
           <artifactId>hadoop-common</artifactId>
         </exclusion>
         <exclusion>
           <groupId>org.umlgraph</groupId>
           <artifactId>umlgraph</artifactId>
         </exclusion>
         <exclusion>
           <groupId>org.eclipse.jetty.aggregate</groupId>
           <artifactId>jetty-all</artifactId>
         </exclusion>
         <exclusion>
           <groupId>it.unimi.di</groupId>
           <artifactId>mg4j</artifactId>
         </exclusion>
         <exclusion>
           <groupId>it.unimi.di</groupId>
           <artifactId>mg4j-big</artifactId>
         </exclusion>
       </exclusions>
     </dependency>
     <dependency>
       <groupId>com.martiansoftware</groupId>
       <artifactId>jsap</artifactId>
       <version>2.1</version>
     </dependency>
     <dependency>
       <groupId>net.sf.py4j</groupId>
       <artifactId>py4j</artifactId>
       <version>0.10.8.1</version>
     </dependency>
     <dependency>
       <groupId>commons-codec</groupId>
       <artifactId>commons-codec</artifactId>
       <version>1.11</version>
     </dependency>
   </dependencies>
 
   <build>
     <pluginManagement><!-- lock down plugins versions to avoid using Maven defaults (may be moved to parent pom) -->
       <plugins>
         <!-- clean lifecycle, see https://maven.apache.org/ref/current/maven-core/lifecycles.html#clean_Lifecycle -->
         <plugin>
           <artifactId>maven-clean-plugin</artifactId>
           <version>3.1.0</version>
         </plugin>
         <!-- default lifecycle, jar packaging: see https://maven.apache.org/ref/current/maven-core/default-bindings.html#Plugin_bindings_for_jar_packaging -->
         <plugin>
           <artifactId>maven-resources-plugin</artifactId>
           <version>3.0.2</version>
         </plugin>
         <plugin>
           <artifactId>maven-compiler-plugin</artifactId>
           <version>3.8.0</version>
           <configuration>
             <source>11</source>
             <target>11</target>
             <compilerArgs>
               <arg>-verbose</arg>
               <arg>-Xlint:all</arg>
             </compilerArgs>
           </configuration>
         </plugin>
         <plugin>
           <artifactId>maven-surefire-plugin</artifactId>
           <version>2.22.2</version>
         </plugin>
         <plugin>
             <artifactId>maven-failsafe-plugin</artifactId>
             <version>2.22.2</version>
         </plugin>
         <plugin>
           <artifactId>maven-jar-plugin</artifactId>
           <version>3.0.2</version>
         </plugin>
         <plugin>
           <artifactId>maven-install-plugin</artifactId>
           <version>2.5.2</version>
         </plugin>
         <plugin>
           <artifactId>maven-deploy-plugin</artifactId>
           <version>2.8.2</version>
         </plugin>
         <!-- site lifecycle, see https://maven.apache.org/ref/current/maven-core/lifecycles.html#site_Lifecycle -->
         <plugin>
           <artifactId>maven-site-plugin</artifactId>
           <version>3.7.1</version>
         </plugin>
         <plugin>
           <artifactId>maven-project-info-reports-plugin</artifactId>
           <version>3.0.0</version>
         </plugin>
         <plugin>
           <artifactId>maven-assembly-plugin</artifactId>
           <version>3.3.0</version>
           <configuration>
             <archive>
               <manifest>
                 <mainClass>org.softwareheritage.graph.server.App</mainClass>
               </manifest>
             </archive>
             <descriptorRefs>
               <descriptorRef>jar-with-dependencies</descriptorRef>
             </descriptorRefs>
             <appendAssemblyId>false</appendAssemblyId>
           </configuration>
           <executions>
             <execution>
               <id>make-assembly</id> <!-- this is used for inheritance merges -->
               <phase>package</phase> <!-- bind to the packaging phase -->
               <goals>
                 <goal>single</goal>
               </goals>
             </execution>
           </executions>
       </plugin>
       <!-- Spotless code formatting tool -->
       <plugin>
         <groupId>com.diffplug.spotless</groupId>
         <artifactId>spotless-maven-plugin</artifactId>
         <version>2.4.1</version>
         <configuration>
           <formats>
             <format>
               <includes>
                 <include>*.md</include>
                 <include>.gitignore</include>
               </includes>
               <trimTrailingWhitespace/>
               <endWithNewline/>
               <indent>
                 <spaces>true</spaces>
                 <spacesPerTab>4</spacesPerTab>
               </indent>
             </format>
           </formats>
           <java>
             <removeUnusedImports/>
             <eclipse>
                 <version>4.16.0</version>
                 <file>.coding-style.xml</file>
             </eclipse>
           </java>
         </configuration>
       </plugin>
       </plugins>
     </pluginManagement>
     <plugins>
       <plugin>
         <groupId>pl.project13.maven</groupId>
         <artifactId>git-commit-id-plugin</artifactId>
         <version>3.0.1</version>
         <executions>
           <execution>
             <id>get-the-git-infos</id>
             <goals>
               <goal>revision</goal>
             </goals>
             <phase>initialize</phase>
           </execution>
         </executions>
         <configuration>
           <verbose>true</verbose>
           <offline>true</offline>
           <useNativeGit>true</useNativeGit>
           <gitDescribe>
             <always>true</always>
             <match>v*</match>
           </gitDescribe>
           <replacementProperties>
             <replacementProperty>
               <property>git.closest.tag.name</property>
               <token>^v</token>
               <value></value>
               <regex>true</regex>
             </replacementProperty>
           </replacementProperties>
         </configuration>
       </plugin>
     </plugins>
   </build>
   <reporting>
     <plugins>
       <plugin>
         <groupId>org.apache.maven.plugins</groupId>
         <artifactId>maven-javadoc-plugin</artifactId>
         <version>3.1.1</version>
       </plugin>
     </plugins>
   </reporting>
 </project>
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java b/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java
index 6f9c00e..27019fa 100644
--- a/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java
+++ b/java/src/main/java/org/softwareheritage/graph/maps/LabelMapBuilder.java
@@ -1,307 +1,307 @@
 package org.softwareheritage.graph.maps;
 
 import com.martiansoftware.jsap.*;
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
 import it.unimi.dsi.big.webgraph.labelling.ArcLabelledImmutableGraph;
 import it.unimi.dsi.big.webgraph.labelling.BitStreamArcLabelledImmutableGraph;
 import it.unimi.dsi.fastutil.BigArrays;
 import it.unimi.dsi.fastutil.Size64;
 import it.unimi.dsi.fastutil.bytes.ByteArrays;
 import it.unimi.dsi.fastutil.io.BinIO;
 import it.unimi.dsi.fastutil.io.FastBufferedInputStream;
 import it.unimi.dsi.fastutil.longs.LongBigArrays;
 import it.unimi.dsi.fastutil.objects.Object2LongFunction;
 import it.unimi.dsi.io.OutputBitStream;
 import it.unimi.dsi.logging.ProgressLogger;
 import it.unimi.dsi.big.webgraph.BVGraph;
 import it.unimi.dsi.big.webgraph.ImmutableGraph;
 import it.unimi.dsi.big.webgraph.NodeIterator;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 import org.softwareheritage.graph.labels.DirEntry;
 import org.softwareheritage.graph.labels.SwhLabel;
 
 import java.io.*;
 import java.lang.reflect.Array;
 import java.nio.charset.StandardCharsets;
 import java.util.*;
 import java.util.concurrent.TimeUnit;
 
 public class LabelMapBuilder {
     final static String SORT_BUFFER_SIZE = "40%";
     final static Logger logger = LoggerFactory.getLogger(LabelMapBuilder.class);
 
     String graphPath;
     String debugPath;
     String tmpDir;
     ImmutableGraph graph;
 
-    Object2LongFunction<String> swhIdMph;
+    Object2LongFunction<byte[]> swhIdMph;
     long[][] orderMap;
-    Object2LongFunction<String> filenameMph;
+    Object2LongFunction<byte[]> filenameMph;
     long numFilenames;
     int totalLabelWidth;
 
     public LabelMapBuilder(String graphPath, String debugPath, String tmpDir) {
         this.graphPath = graphPath;
         this.debugPath = debugPath;
         this.tmpDir = tmpDir;
     }
 
     private static JSAPResult parse_args(String[] args) {
         JSAPResult config = null;
         try {
             SimpleJSAP jsap = new SimpleJSAP(LabelMapBuilder.class.getName(), "",
                     new Parameter[]{
                             new FlaggedOption("graphPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.REQUIRED, 'g',
                                     "graph", "Basename of the compressed graph"),
                             new FlaggedOption("debugPath", JSAP.STRING_PARSER, JSAP.NO_DEFAULT, JSAP.NOT_REQUIRED, 'd',
                                     "debug-path", "Store the intermediate representation here for debug"),
 
                             new FlaggedOption("tmpDir", JSAP.STRING_PARSER, "tmp", JSAP.NOT_REQUIRED, 't', "tmp",
                                     "Temporary directory path"),});
 
             config = jsap.parse(args);
             if (jsap.messagePrinted()) {
                 System.exit(1);
             }
         } catch (JSAPException e) {
             e.printStackTrace();
         }
         return config;
     }
 
     public static void main(String[] args) throws IOException {
         JSAPResult config = parse_args(args);
         String graphPath = config.getString("graphPath");
         String tmpDir = config.getString("tmpDir");
         String debugPath = config.getString("debugPath");
 
         LabelMapBuilder builder = new LabelMapBuilder(graphPath, debugPath, tmpDir);
         builder.computeLabelMap();
     }
 
     @SuppressWarnings("unchecked") // Suppress warning for Object2LongFunction cast
-    static Object2LongFunction<String> loadMPH(String mphBasename) throws IOException {
-        Object2LongFunction<String> mphMap = null;
+    static Object2LongFunction<byte[]> loadMPH(String mphBasename) throws IOException {
+        Object2LongFunction<byte[]> mphMap = null;
         try {
-            mphMap = (Object2LongFunction<String>) BinIO.loadObject(mphBasename + ".mph");
+            mphMap = (Object2LongFunction<byte[]>) BinIO.loadObject(mphBasename + ".mph");
         } catch (ClassNotFoundException e) {
             logger.error("unknown class object in .mph file: " + e);
             System.exit(2);
         }
         return mphMap;
     }
 
-    static long getMPHSize(Object2LongFunction<String> mph) {
+    static long getMPHSize(Object2LongFunction<byte[]> mph) {
         return (mph instanceof Size64) ? ((Size64) mph).size64() : mph.size();
     }
 
     void computeLabelMap() throws IOException {
         /*
          * Pass the intermediate representation to sort(1) so that we see the labels in the order they will
          * appear in the label file.
          */
         logger.info("Loading graph and MPH functions...");
         loadGraph();
 
         logger.info("Hashing the input labels...");
 
         ProcessBuilder processBuilder = new ProcessBuilder();
         processBuilder.command("sort", "-k1,1n", "-k2,2n", // Numerical sort
                 "--numeric-sort", "--buffer-size", SORT_BUFFER_SIZE, "--temporary-directory", tmpDir);
         Process sort = processBuilder.start();
         BufferedOutputStream sort_stdin = new BufferedOutputStream(sort.getOutputStream());
         BufferedInputStream sort_stdout = new BufferedInputStream(sort.getInputStream());
 
         final FastBufferedInputStream fbis = new FastBufferedInputStream(System.in);
         hashLabelStream(fbis, sort_stdin);
         sort_stdin.close();
 
         logger.info("Writing label map to file...");
         writeLabels(sort_stdout);
 
         logger.info("Done");
     }
 
     void loadGraph() throws IOException {
         graph = BVGraph.loadMapped(graphPath);
 
         swhIdMph = loadMPH(graphPath);
 
         orderMap = LongBigArrays.newBigArray(getMPHSize(swhIdMph));
         BinIO.loadLongs(graphPath + ".order", orderMap);
 
         filenameMph = loadMPH(graphPath + "-labels");
         numFilenames = getMPHSize(filenameMph);
         totalLabelWidth = DirEntry.labelWidth(numFilenames);
     }
 
     void hashLabelStream(FastBufferedInputStream input, BufferedOutputStream output) throws IOException {
         // Compute intermediate representation and write it on :
         // "<src node id> <dst node id> <label ids>\n"
         ProgressLogger plInter = new ProgressLogger(logger, 10, TimeUnit.SECONDS);
         plInter.itemsName = "edges";
         plInter.expectedUpdates = graph.numArcs();
         plInter.start("Hashing the label stream");
 
         var charset = StandardCharsets.US_ASCII;
         byte[] array = new byte[1024];
         for (long line = 0;; line++) {
             int start = 0, len;
             while ((len = input.readLine(array, start, array.length - start,
                     FastBufferedInputStream.ALL_TERMINATORS)) == array.length - start) {
                 start += len;
                 array = ByteArrays.grow(array, array.length + 1);
             }
             if (len == -1)
                 break; // EOF
             final int lineLength = start + len;
 
             // Skip whitespace at the start of the line.
             int offset = 0;
             while (offset < lineLength && array[offset] >= 0 && array[offset] <= ' ')
                 offset++;
             if (offset == lineLength) {
                 continue;
             }
             if (array[0] == '#')
                 continue;
 
             // Scan source id.
             start = offset;
             while (offset < lineLength && (array[offset] < 0 || array[offset] > ' '))
                 offset++;
-            final String ss = new String(array, start, offset - start, charset);
+            final byte[] ss = Arrays.copyOfRange(array, start, offset);
 
             // Skip whitespace between identifiers.
             while (offset < lineLength && array[offset] >= 0 && array[offset] <= ' ')
                 offset++;
             if (offset == lineLength) {
                 logger.error("Error at line " + line + ": no target");
                 continue;
             }
 
             // Scan target ID
             start = offset;
             while (offset < lineLength && (array[offset] < 0 || array[offset] > ' '))
                 offset++;
-            final String ts = new String(array, start, offset - start, charset);
+            final byte[] ts = Arrays.copyOfRange(array, start, offset);
 
             // Skip whitespace between identifiers.
             while (offset < lineLength && array[offset] >= 0 && array[offset] <= ' ')
                 offset++;
             if (offset == lineLength)
                 continue; // No label, skip
 
             // Scan label
             start = offset;
             while (offset < lineLength && (array[offset] < 0 || array[offset] > ' '))
                 offset++;
-            final String ls = new String(array, start, offset - start, charset);
+            final byte[] ls = Arrays.copyOfRange(array, start, offset);
 
             // Skip whitespace between identifiers.
             while (offset < lineLength && array[offset] >= 0 && array[offset] <= ' ')
                 offset++;
             // Scan permission
             int permission = 0;
             if (offset < lineLength) {
                 start = offset;
                 while (offset < lineLength && (array[offset] < 0 || array[offset] > ' '))
                     offset++;
                 permission = Integer.parseInt(new String(array, start, offset - start, charset));
             }
 
             // System.err.format("DEBUG: read %s %s %s %d\n", ss, ts, ls, permission);
 
             long s = swhIdMph.getLong(ss);
             long t = swhIdMph.getLong(ts);
             long filenameId = filenameMph.getLong(ls);
 
             long srcNode = BigArrays.get(orderMap, s);
             long dstNode = BigArrays.get(orderMap, t);
 
             output.write((srcNode + "\t" + dstNode + "\t" + filenameId + "\t" + permission + "\n")
                     .getBytes(StandardCharsets.US_ASCII));
             plInter.lightUpdate();
         }
         plInter.done();
     }
 
     void writeLabels(InputStream sortedMapping) throws IOException {
         // Get the sorted output and write the labels and label offsets
         ProgressLogger plLabels = new ProgressLogger(logger, 10, TimeUnit.SECONDS);
         plLabels.itemsName = "nodes";
         plLabels.expectedUpdates = graph.numNodes();
 
         FileWriter debugFile = null;
         if (debugPath != null) {
             debugFile = new FileWriter(debugPath);
         }
 
         OutputBitStream labels = new OutputBitStream(
                 new File(graphPath + "-labelled" + BitStreamArcLabelledImmutableGraph.LABELS_EXTENSION));
         OutputBitStream offsets = new OutputBitStream(
                 new File(graphPath + "-labelled" + BitStreamArcLabelledImmutableGraph.LABEL_OFFSETS_EXTENSION));
         offsets.writeGamma(0);
 
         Scanner mapLines = new Scanner(sortedMapping, StandardCharsets.US_ASCII);
 
         NodeIterator it = graph.nodeIterator();
         long labelSrcNode = -1;
         long labelDstNode = -1;
         long labelFilenameId = -1;
         int labelPermission = -1;
 
         ArrayList<DirEntry> labelBuffer = new ArrayList<>(128);
         while (it.hasNext()) {
             long srcNode = it.nextLong();
 
             int bits = 0;
             LazyLongIterator s = it.successors();
             long dstNode;
             while ((dstNode = s.nextLong()) >= 0) {
                 while (labelSrcNode <= srcNode && labelDstNode <= dstNode) {
                     if (labelSrcNode == srcNode && labelDstNode == dstNode) {
                         labelBuffer.add(new DirEntry(labelFilenameId, labelPermission));
 
                         if (debugFile != null) {
                             debugFile.write(labelSrcNode + " " + labelDstNode + " " + labelFilenameId + " "
                                     + labelPermission + "\n");
                         }
                     }
 
                     if (!mapLines.hasNext())
                         break;
 
                     String line = mapLines.nextLine();
                     String[] parts = line.split("\\t");
                     labelSrcNode = Long.parseLong(parts[0]);
                     labelDstNode = Long.parseLong(parts[1]);
                     labelFilenameId = Long.parseLong(parts[2]);
                     labelPermission = Integer.parseInt(parts[3]);
                 }
 
                 SwhLabel l = new SwhLabel("edgelabel", totalLabelWidth, labelBuffer.toArray(new DirEntry[0]));
                 labelBuffer.clear();
                 bits += l.toBitStream(labels, -1);
             }
             offsets.writeGamma(bits);
             plLabels.lightUpdate();
         }
 
         labels.close();
         offsets.close();
         plLabels.done();
         if (debugFile != null) {
             debugFile.close();
         }
 
         PrintWriter pw = new PrintWriter(new FileWriter((new File(graphPath)).getName() + "-labelled.properties"));
         pw.println(ImmutableGraph.GRAPHCLASS_PROPERTY_KEY + " = " + BitStreamArcLabelledImmutableGraph.class.getName());
         pw.println(BitStreamArcLabelledImmutableGraph.LABELSPEC_PROPERTY_KEY + " = " + SwhLabel.class.getName()
                 + "(DirEntry," + totalLabelWidth + ")");
         pw.println(ArcLabelledImmutableGraph.UNDERLYINGGRAPH_PROPERTY_KEY + " = " + graphPath);
         pw.close();
     }
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java b/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java
index 7ade2f1..3c9f6ef 100644
--- a/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java
+++ b/java/src/main/java/org/softwareheritage/graph/maps/NodeMapBuilder.java
@@ -1,217 +1,217 @@
 package org.softwareheritage.graph.maps;
 
 import it.unimi.dsi.bits.LongArrayBitVector;
 import it.unimi.dsi.fastutil.BigArrays;
 import it.unimi.dsi.fastutil.Size64;
 import it.unimi.dsi.fastutil.io.BinIO;
 import it.unimi.dsi.fastutil.longs.LongBigArrays;
 import it.unimi.dsi.fastutil.longs.LongBigList;
 import it.unimi.dsi.fastutil.objects.Object2LongFunction;
 import it.unimi.dsi.io.FastBufferedReader;
 import it.unimi.dsi.io.LineIterator;
 import it.unimi.dsi.logging.ProgressLogger;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
 import org.softwareheritage.graph.Graph;
 import org.softwareheritage.graph.Node;
 import org.softwareheritage.graph.SWHID;
 
 import java.io.*;
 import java.nio.charset.StandardCharsets;
 import java.util.Scanner;
 import java.util.concurrent.TimeUnit;
 
 /**
  * Create maps needed at runtime by the graph service, in particular:
  * <p>
  * <ul>
  * <li>SWHID → WebGraph long node id</li>
  * <li>WebGraph long node id → SWHID (converse of the former)</li>
  * <li>WebGraph long node id → SWH node type (enum)</li>
  * </ul>
  *
  * @author The Software Heritage developers
  */
 public class NodeMapBuilder {
 
     final static String SORT_BUFFER_SIZE = "40%";
 
     final static Logger logger = LoggerFactory.getLogger(NodeMapBuilder.class);
 
     /**
      * Main entrypoint.
      *
      * @param args command line arguments
      */
     public static void main(String[] args) throws IOException {
         if (args.length != 2) {
             logger.error("Usage: COMPRESSED_GRAPH_BASE_NAME TEMP_DIR < NODES_CSV");
             System.exit(1);
         }
         String graphPath = args[0];
         String tmpDir = args[1];
 
         logger.info("starting maps generation...");
         precomputeNodeIdMap(graphPath, tmpDir);
         logger.info("maps generation completed");
     }
 
     /**
      * Computes and dumps on disk mapping files.
      *
      * @param graphPath path of the compressed graph
      */
     // Suppress warning for Object2LongFunction cast
     @SuppressWarnings("unchecked")
     static void precomputeNodeIdMap(String graphPath, String tmpDir) throws IOException {
         ProgressLogger plSWHID2Node = new ProgressLogger(logger, 10, TimeUnit.SECONDS);
         ProgressLogger plNode2SWHID = new ProgressLogger(logger, 10, TimeUnit.SECONDS);
         plSWHID2Node.itemsName = "swhid→node";
         plNode2SWHID.itemsName = "node→swhid";
 
         /*
          * avg speed for swhid→node is sometime skewed due to write to the sort pipe hanging when sort is
          * sorting; hence also desplay local speed
          */
         plSWHID2Node.displayLocalSpeed = true;
 
         // first half of SWHID->node mapping: SWHID -> WebGraph MPH (long)
-        Object2LongFunction<String> mphMap = null;
+        Object2LongFunction<byte[]> mphMap = null;
         try {
             logger.info("loading MPH function...");
-            mphMap = (Object2LongFunction<String>) BinIO.loadObject(graphPath + ".mph");
+            mphMap = (Object2LongFunction<byte[]>) BinIO.loadObject(graphPath + ".mph");
             logger.info("MPH function loaded");
         } catch (ClassNotFoundException e) {
             logger.error("unknown class object in .mph file: " + e);
             System.exit(2);
         }
         long nbIds = (mphMap instanceof Size64) ? ((Size64) mphMap).size64() : mphMap.size();
         plSWHID2Node.expectedUpdates = nbIds;
         plNode2SWHID.expectedUpdates = nbIds;
 
         // second half of SWHID->node mapping: WebGraph MPH (long) -> BFS order (long)
         long[][] bfsMap = LongBigArrays.newBigArray(nbIds);
         logger.info("loading BFS order file...");
         long loaded = BinIO.loadLongs(graphPath + ".order", bfsMap);
         logger.info("BFS order file loaded");
         if (loaded != nbIds) {
             logger.error("graph contains " + nbIds + " nodes, but read " + loaded);
             System.exit(2);
         }
 
         /*
          * Create mapping SWHID -> WebGraph node id, by sequentially reading nodes, hashing them with MPH,
          * and permuting according to BFS order
          */
         FastBufferedReader buffer = new FastBufferedReader(new InputStreamReader(System.in, StandardCharsets.US_ASCII));
         LineIterator swhidIterator = new LineIterator(buffer);
 
         /*
          * The WebGraph node id -> SWHID mapping can be obtained from the SWHID->node one by numerically
          * sorting on node id and sequentially writing obtained SWHIDs to a binary map. Delegates the
          * sorting job to /usr/bin/sort via pipes
          */
         ProcessBuilder processBuilder = new ProcessBuilder();
         processBuilder.command("sort", "--numeric-sort", "--key", "2", "--buffer-size", SORT_BUFFER_SIZE,
                 "--temporary-directory", tmpDir);
         Process sort = processBuilder.start();
         BufferedOutputStream sort_stdin = new BufferedOutputStream(sort.getOutputStream());
         BufferedInputStream sort_stdout = new BufferedInputStream(sort.getInputStream());
 
         // for the binary format of swhidToNodeMap, see Python module swh.graph.swhid:SwhidToIntMap
         // for the binary format of nodeToSwhidMap, see Python module swh.graph.swhid:IntToSwhidMap
         try (DataOutputStream swhidToNodeMap = new DataOutputStream(
                 new BufferedOutputStream(new FileOutputStream(graphPath + Graph.SWHID_TO_NODE)));
                 BufferedOutputStream nodeToSwhidMap = new BufferedOutputStream(
                         new FileOutputStream(graphPath + Graph.NODE_TO_SWHID))) {
 
             /*
              * background handler for sort output, it will be fed SWHID/node pairs while swhidToNodeMap is being
              * filled, and will itself fill nodeToSwhidMap as soon as data from sort is ready
              */
             SortOutputHandler outputHandler = new SortOutputHandler(sort_stdout, nodeToSwhidMap, plNode2SWHID);
             outputHandler.start();
 
             /*
              * Type map from WebGraph node ID to SWH type. Used at runtime by pure Java graph traversals to
              * efficiently check edge restrictions.
              */
             final int log2NbTypes = (int) Math.ceil(Math.log(Node.Type.values().length) / Math.log(2));
             final int nbBitsPerNodeType = log2NbTypes;
             LongArrayBitVector nodeTypesBitVector = LongArrayBitVector.ofLength(nbBitsPerNodeType * nbIds);
             LongBigList nodeTypesMap = nodeTypesBitVector.asLongBigList(nbBitsPerNodeType);
 
             plSWHID2Node.start("filling swhid2node map");
             for (long iNode = 0; iNode < nbIds && swhidIterator.hasNext(); iNode++) {
                 String swhidStr = swhidIterator.next().toString();
                 SWHID swhid = new SWHID(swhidStr);
                 byte[] swhidBin = swhid.toBytes();
 
-                long mphId = mphMap.getLong(swhidStr);
+                long mphId = mphMap.getLong(swhidStr.getBytes(StandardCharsets.US_ASCII));
                 long nodeId = BigArrays.get(bfsMap, mphId);
 
                 swhidToNodeMap.write(swhidBin, 0, swhidBin.length);
                 swhidToNodeMap.writeLong(nodeId);
                 sort_stdin.write((swhidStr + "\t" + nodeId + "\n").getBytes(StandardCharsets.US_ASCII));
 
                 nodeTypesMap.set(nodeId, swhid.getType().ordinal());
                 plSWHID2Node.lightUpdate();
             }
             plSWHID2Node.done();
             sort_stdin.close();
 
             // write type map
             logger.info("storing type map");
             BinIO.storeObject(nodeTypesMap, graphPath + Graph.NODE_TO_TYPE);
             logger.info("type map stored");
 
             // wait for nodeToSwhidMap filling
             try {
                 logger.info("waiting for node2swhid map...");
                 int sortExitCode = sort.waitFor();
                 if (sortExitCode != 0) {
                     logger.error("sort returned non-zero exit code: " + sortExitCode);
                     System.exit(2);
                 }
                 outputHandler.join();
             } catch (InterruptedException e) {
                 logger.error("processing of sort output failed with: " + e);
                 System.exit(2);
             }
         }
 
     }
 
     private static class SortOutputHandler extends Thread {
         private Scanner input;
         private OutputStream output;
         private ProgressLogger pl;
 
         SortOutputHandler(InputStream input, OutputStream output, ProgressLogger pl) {
             this.input = new Scanner(input, StandardCharsets.US_ASCII);
             this.output = output;
             this.pl = pl;
         }
 
         public void run() {
             boolean sortDone = false;
             logger.info("node2swhid: waiting for sort output...");
             while (input.hasNextLine()) {
                 if (!sortDone) {
                     sortDone = true;
                     this.pl.start("filling node2swhid map");
                 }
                 String line = input.nextLine(); // format: SWHID <TAB> NODE_ID
                 SWHID swhid = new SWHID(line.split("\\t")[0]); // get SWHID
                 try {
                     output.write((byte[]) swhid.toBytes());
                 } catch (IOException e) {
                     logger.error("writing to node->SWHID map failed with: " + e);
                 }
                 this.pl.lightUpdate();
             }
             this.pl.done();
         }
     }
 
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java b/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java
index 7e407e3..1938355 100644
--- a/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/ExportSubdataset.java
@@ -1,81 +1,81 @@
 package org.softwareheritage.graph.utils;
 
 import com.google.common.primitives.Longs;
 import it.unimi.dsi.big.webgraph.LazyLongIterator;
 import it.unimi.dsi.bits.LongArrayBitVector;
 import it.unimi.dsi.fastutil.Arrays;
 import it.unimi.dsi.fastutil.io.BinIO;
 import it.unimi.dsi.fastutil.objects.Object2LongFunction;
 import it.unimi.dsi.io.ByteDiskQueue;
 import it.unimi.dsi.io.FastBufferedReader;
 import it.unimi.dsi.io.LineIterator;
 import org.softwareheritage.graph.Graph;
 import org.softwareheritage.graph.SWHID;
 import org.softwareheritage.graph.experiments.topology.ConnectedComponents;
 
 import java.io.File;
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.nio.charset.StandardCharsets;
 
 public class ExportSubdataset {
     @SuppressWarnings("unchecked") // Suppress warning for Object2LongFunction cast
-    static Object2LongFunction<String> loadMPH(String mphPath) throws IOException, ClassNotFoundException {
-        return (Object2LongFunction<String>) BinIO.loadObject(mphPath);
+    static Object2LongFunction<byte[]> loadMPH(String mphPath) throws IOException, ClassNotFoundException {
+        return (Object2LongFunction<byte[]>) BinIO.loadObject(mphPath);
     }
 
     public static void main(String[] args) throws IOException, ClassNotFoundException {
         System.err.print("Loading everything...");
         String graphPath = args[0];
         Graph graph = new Graph(graphPath);
-        Object2LongFunction<String> mphMap = loadMPH(graphPath + ".mph");
+        Object2LongFunction<byte[]> mphMap = loadMPH(graphPath + ".mph");
         System.err.println(" done.");
 
         final long n = graph.numNodes();
 
         // Allow enough memory to behave like in-memory queue
         int bufferSize = (int) Math.min(Arrays.MAX_ARRAY_SIZE & ~0x7, 8L * n);
 
         // Use a disk based queue to store BFS frontier
         final File queueFile = File.createTempFile(ConnectedComponents.class.getSimpleName(), "queue");
         final ByteDiskQueue queue = ByteDiskQueue.createNew(queueFile, bufferSize, true);
         final byte[] byteBuf = new byte[Long.BYTES];
         // WARNING: no 64-bit version of this data-structure, but it can support
         // indices up to 2^37
         LongArrayBitVector visited = LongArrayBitVector.ofLength(n);
 
         FastBufferedReader buffer = new FastBufferedReader(new InputStreamReader(System.in, StandardCharsets.US_ASCII));
         LineIterator lineIterator = new LineIterator(buffer);
 
         while (lineIterator.hasNext()) {
             String line = lineIterator.next().toString();
             long i;
             try {
-                // i = mphMap.getLong(line);
+                // i = mphMap.getLong(line.getBytes(StandardCharsets.UTF_8));
                 i = graph.getNodeId(new SWHID(line));
             } catch (IllegalArgumentException e) {
                 continue;
             }
 
             queue.enqueue(Longs.toByteArray(i));
             visited.set(i);
 
             while (!queue.isEmpty()) {
                 queue.dequeue(byteBuf);
                 final long currentNode = Longs.fromByteArray(byteBuf);
                 SWHID currentNodeSWHID = graph.getSWHID(currentNode);
 
                 final LazyLongIterator iterator = graph.successors(currentNode);
                 long succ;
                 while ((succ = iterator.nextLong()) != -1) {
                     System.out.format("%s %s\n", currentNodeSWHID, graph.getSWHID(succ));
                     if (visited.getBoolean(succ))
                         continue;
                     visited.set(succ);
                     queue.enqueue(Longs.toByteArray(succ));
                 }
             }
 
         }
     }
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java b/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java
index ca7012b..3be8ae0 100644
--- a/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/MPHTranslate.java
@@ -1,50 +1,51 @@
 package org.softwareheritage.graph.utils;
 
 import com.martiansoftware.jsap.*;
 import it.unimi.dsi.fastutil.io.BinIO;
 import it.unimi.dsi.fastutil.objects.Object2LongFunction;
 import it.unimi.dsi.io.FastBufferedReader;
 import it.unimi.dsi.io.LineIterator;
 
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.nio.charset.StandardCharsets;
 
 public class MPHTranslate {
     private static JSAPResult parse_args(String[] args) {
         JSAPResult config = null;
         try {
             SimpleJSAP jsap = new SimpleJSAP(MPHTranslate.class.getName(), "",
                     new Parameter[]{new UnflaggedOption("function", JSAP.STRING_PARSER, JSAP.REQUIRED,
                             "Filename of the serialized MPH"),});
 
             config = jsap.parse(args);
             if (jsap.messagePrinted()) {
                 System.exit(1);
             }
         } catch (JSAPException e) {
             e.printStackTrace();
         }
         return config;
     }
 
     @SuppressWarnings("unchecked") // Suppress warning for Object2LongFunction cast
-    static Object2LongFunction<String> loadMPH(String mphPath) throws IOException, ClassNotFoundException {
-        return (Object2LongFunction<String>) BinIO.loadObject(mphPath);
+    static Object2LongFunction<byte[]> loadMPH(String mphPath) throws IOException, ClassNotFoundException {
+        return (Object2LongFunction<byte[]>) BinIO.loadObject(mphPath);
     }
 
     public static void main(String[] args) throws IOException, ClassNotFoundException {
         JSAPResult config = parse_args(args);
         String mphPath = config.getString("function");
 
-        Object2LongFunction<String> mphMap = loadMPH(mphPath);
+        Object2LongFunction<byte[]> mphMap = loadMPH(mphPath);
 
+        // TODO: wasteful to convert to/from bytes
         FastBufferedReader buffer = new FastBufferedReader(new InputStreamReader(System.in, StandardCharsets.US_ASCII));
         LineIterator lineIterator = new LineIterator(buffer);
 
         while (lineIterator.hasNext()) {
             String line = lineIterator.next().toString();
-            System.out.println(mphMap.getLong(line));
+            System.out.println(mphMap.getLong(line.getBytes(StandardCharsets.US_ASCII)));
         }
     }
 }
diff --git a/java/src/main/java/org/softwareheritage/graph/utils/WriteRevisionTimestamps.java b/java/src/main/java/org/softwareheritage/graph/utils/WriteRevisionTimestamps.java
index a0e1a12..52491b2 100644
--- a/java/src/main/java/org/softwareheritage/graph/utils/WriteRevisionTimestamps.java
+++ b/java/src/main/java/org/softwareheritage/graph/utils/WriteRevisionTimestamps.java
@@ -1,56 +1,57 @@
 package org.softwareheritage.graph.utils;
 
 import it.unimi.dsi.fastutil.BigArrays;
 import it.unimi.dsi.fastutil.Size64;
 import it.unimi.dsi.fastutil.io.BinIO;
 import it.unimi.dsi.fastutil.longs.LongBigArrays;
 import it.unimi.dsi.fastutil.objects.Object2LongFunction;
 import it.unimi.dsi.io.FastBufferedReader;
 import it.unimi.dsi.io.LineIterator;
 
 import java.io.IOException;
 import java.io.InputStreamReader;
 import java.nio.charset.StandardCharsets;
 
 public class WriteRevisionTimestamps {
     @SuppressWarnings("unchecked") // Suppress warning for Object2LongFunction cast
-    static Object2LongFunction<String> loadMPH(String mphPath) throws IOException, ClassNotFoundException {
-        return (Object2LongFunction<String>) BinIO.loadObject(mphPath);
+    static Object2LongFunction<byte[]> loadMPH(String mphPath) throws IOException, ClassNotFoundException {
+        return (Object2LongFunction<byte[]>) BinIO.loadObject(mphPath);
     }
 
     public static void main(String[] args) throws IOException, ClassNotFoundException {
         System.err.print("Loading everything...");
         String graphPath = args[0];
         String outputFile = args[1];
-        Object2LongFunction<String> mphMap = loadMPH(graphPath + ".mph");
+        Object2LongFunction<byte[]> mphMap = loadMPH(graphPath + ".mph");
         long nbIds = (mphMap instanceof Size64) ? ((Size64) mphMap).size64() : mphMap.size();
         long[][] nodePerm = BinIO.loadLongsBig(graphPath + ".order");
         // NodeIdMap nodeIdMap = new NodeIdMap(graphPath, nbIds);
         long[][] timestampArray = LongBigArrays.newBigArray(nbIds);
         BigArrays.fill(timestampArray, Long.MIN_VALUE);
         System.err.println(" done.");
 
+        // TODO: wasteful to convert to/from bytes
         FastBufferedReader buffer = new FastBufferedReader(new InputStreamReader(System.in, StandardCharsets.US_ASCII));
         LineIterator lineIterator = new LineIterator(buffer);
 
         while (lineIterator.hasNext()) {
             String line = lineIterator.next().toString();
             String[] line_elements = line.split("[ \\t]");
 
             // SWHID currentRev = new SWHID(line_elements[0].strip());
             long revId = -1;
             long timestamp = -1;
             try {
                 // revId = nodeIdMap.getNodeId(currentRev);
-                long revHash = mphMap.getLong(line_elements[0].strip());
+                long revHash = mphMap.getLong(line_elements[0].strip().getBytes(StandardCharsets.US_ASCII));
                 revId = BigArrays.get(nodePerm, revHash);
                 timestamp = Long.parseLong(line_elements[1].strip());
             } catch (IllegalArgumentException e) {
                 continue;
             }
             BigArrays.set(timestampArray, revId, timestamp);
             // System.err.println(revId + " " + timestamp);
         }
         BinIO.storeLongs(timestampArray, outputFile);
     }
 }