NDLI: Compactly encoding unstructured inputs with differential compression

Content Provider	ACM Digital Library
Author	Ajtai, Miklos Burns, Randal Fagin, Ronald Long, Darrell D E Stockmeyer, Larry
Copyright Year	2002
Abstract	The subject of this article is differential compression, the algorithmic task of finding common strings between versions of data and using them to encode one version compactly by describing it as a set of changes from its companion. A main goal of this work is to present new differencing algorithms that (i) operate at a fine granularity (the atomic unit of change), (ii) make no assumptions about the format or alignment of input data, and (iii) in practice use linear time, use constant space, and give good compression. We present new algorithms, which do not always compress optimally but use considerably less time or space than existing algorithms. One new algorithm runs in $\textit{O}(\textit{n})$ time and $\textit{O}(1)$ space in the worst case (where each unit of space contains [log $\textit{n}]$ bits), as compared to algorithms that run in $\textit{O}(\textit{n})$ time and $\textit{O}(\textit{n})$ space or in $O(n^{2})$ time and $\textit{O}(1)$ space. We introduce two new techniques for differential compression and apply these to give additional algorithms that improve compression and time performance. We experimentally explore the properties of our algorithms by running them on actual versioned data. Finally, we present theoretical results that limit the compression power of differencing algorithms that are restricted to making only a single pass over the data.
Starting Page	318
Ending Page	367
Page Count	50
File Format	PDF
ISSN	00045411
e-ISSN	1557735X
DOI	10.1145/567112.567116
Journal	Journal of the ACM (JACM)
Volume Number	49
Issue Number	3
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-05-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Delta compression Differencing Differential compression
Content Type	Text
Resource Type	Article
Subject	Hardware and Architecture Information Systems Control and Systems Engineering Artificial Intelligence Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Coding and Code Compression

Encoding Data Structures in Trees

Information Content of Programs and Operation Encoding

Data compression via textual substitution

Parallel algorithms for data compression

A Dictionary for Minimum Redundancy Encoding

Applications of Path Compression on Balanced Trees

Resolution With Merging

Linear Algorithm for Data Compression via String Matching

Compactly encoding unstructured inputs with differential compression

Similar Documents

Coding and Code Compression

Encoding Data Structures in Trees

Information Content of Programs and Operation Encoding

Data compression via textual substitution

Parallel algorithms for data compression

A Dictionary for Minimum Redundancy Encoding

Applications of Path Compression on Balanced Trees

Resolution With Merging

Linear Algorithm for Data Compression via String Matching

Compactly encoding unstructured inputs with differential compression