Accordion: Multi-Scale Recipes for Adaptive Detection of Duplication

A recipe is metadata that describes the contents of a file as a sequence of blocks identified by their hash. Using recipes, one can rapidly compare the contents of two files without reading the files themselves. Unfortunately, recipes present a space/precision tradeoff: small block sizes will maximize the duplication that is discoverable, but large block sizes produce small recipes that can be compared more quickly. In this paper, we present Accordion, a toolset for the creation and use of multi-scale recipes—that is, recipes that include blocks at several different scales. We demonstrate two duplication-detection algorithms—one optimized for situations where lots of duplication is expected, and another for those where the existence of duplication is uncertain.