  The reconstruction of shredded documents consists in arranging the pieces of
paper (shreds) in order to reassemble the original aspect of such documents.
This task is particularly relevant for supporting forensic investigation as
documents may contain criminal evidence. As an alternative to the laborious and
time-consuming manual process, several researchers have been investigating ways
to perform automatic digital reconstruction. A central problem in automatic
reconstruction of shredded documents is the pairwise compatibility evaluation
of the shreds, notably for binary text documents. In this context, deep
learning has enabled great progress for accurate reconstructions in the domain
of mechanically-shredded documents. A sensitive issue, however, is that current
deep model solutions require an inference whenever a pair of shreds has to be
evaluated. This work proposes a scalable deep learning approach for measuring
pairwise compatibility in which the number of inferences scales linearly
(rather than quadratically) with the number of shreds. Instead of predicting
compatibility directly, deep models are leveraged to asymmetrically project the
raw shred content onto a common metric space in which distance is proportional
to the compatibility. Experimental results show that our method has accuracy
comparable to the state-of-the-art with a speed-up of about 22 times for a test
instance with 505 shreds (20 mixed shredded-pages from different documents).
