2003 · 133 citations · 17 references
ComputingComputer ScienceComputer SystemsData MiningData StructuresDatabasesData CompressionData DeduplicationData RedundancyDuplicate DetectionLossy Data CompressionText Similarity AnalysisCompressionCompression AlgorithmsCompression TechniquesData Redundancy ReductionDelta EncodingMessage CompressionSimilarity Detection
Many objects, such as files, electronic messages, and web pages, contain overlapping content. Numerous past research projects have observed that one can compress one object relative to another one by computing the differences between the two, but these delta-encoding systems have almost invariably required knowledge of a specific relationship between them---most commonly, two versions using the same name at different points in time. We consider cases in which this relationship is determined dynamically, by efficiently determining when a sufficient resemblance exists between two objects in a relatively large collection. We look at specific examples of this technique, namely web pages, email, and files in a file system, and evaluate the potential data reduction and the factors that influence this reduction. We find that delta-encoding using this resemblance detection technique can improve on simple compression by up to a factor of two, depending on workload, and that a small fraction of objects can potentially account for a large portion of these savings.
17
On the resemblance and containment of documents
Arndt Bröder · 2002 · 1.7K citations
Rcs — a system for version control
Walter F. Tichy · Software Practice and Experience · 1985 · 950 citations
A low-bandwidth network file system
Athicha Muthitacharoen, Benjie Chen, David Mazières · 2001 · 786 citations
Venti: A New Approach to Archival Storage
Sean Quinlan, Sean Dorward · 2002 · 728 citations
Finding similar files in a large file system
Udi Manber · 1994 · 589 citations