NDLI: Low-Complexity Interactive Algorithms for Synchronization From Deletions, Insertions, and Substitutions

Content Provider	IEEE Xplore Digital Library
Author	Venkataramanan, R. Swamy, V.N. Ramchandran, K.
Copyright Year	1963
Abstract	Consider two remote nodes having binary sequences X and Y, respectively. Y is an edited version of X, where the editing involves random deletions, insertions, and substitutions, possibly in bursts. The goal is for the node with Y to reconstruct X with minimal exchange of information over a noiseless link. The communication is measured in terms of both the total number of bits exchanged and the number of interactive rounds of communication. This paper focuses on the setting where the number of edits is o(n/log n), where n is the length of X. We first consider the case where the edits are a mixture of insertions and deletions (indels), and propose an interactive synchronization algorithm with near-optimal communication rate and average computational complexity of O(n) arithmetic operations. The algorithm uses interaction to efficiently split the source sequence into substrings containing exactly one deletion or insertion. Each of these substrings is then synchronized using an optimal one-way algorithm based on the single-deletion correcting channel codes of Varshamov and Tenengolts. We then build on this synchronization algorithm in three different ways. First, it is modified to work with a single round of interaction. The reduction in the number of rounds comes at the expense of higher communication, which is quantified. Next, we present an extension to the practically important case where the insertions and deletions may occur in (potentially large) bursts. Finally, we show how to synchronize the sources to within a target Hamming distance. This feature can be used to differentiate between substitution and indel edits. In addition to theoretical performance bounds, we provide several validating simulation results for the proposed algorithms.
Sponsorship	IEEE Information Theory Society
Starting Page	5670
Ending Page	5689
Page Count	20
File Size	1059671
File Format	PDF
ISSN	00189448
Volume Number	61
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-01-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Synchronization Decoding Protocols Approximation algorithms Computational complexity Algorithm design and analysis Simulation Varshamov- Tenengolts codes File Synchronization Two-way interaction Deletion edits Insertion edits Edit channels Varshamov-Tenengolts codes File synchronization two-way interaction deletion edits insertion edits edit channels
Content Type	Text
Resource Type	Article
Subject	Library and Information Sciences Information Systems Computer Science Applications

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

A practical framework for efficient file synchronization

Interactive low-complexity codes for synchronization from deletions and insertions

Efficient File Synchronization

A Deterministic Polynomial-Time Protocol for Synchronizing From Deletions

Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions (2014)

Achievable Rates for Channels With Deletions and Insertions

Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions

Reliable communication over channels with insertions, deletions, and substitutions

Marker codes for channels with insertions and deletions (2005)

Low-Complexity Interactive Algorithms for Synchronization From Deletions, Insertions, and Substitutions

Similar Documents

A practical framework for efficient file synchronization

Interactive low-complexity codes for synchronization from deletions and insertions

Efficient File Synchronization

A Deterministic Polynomial-Time Protocol for Synchronizing From Deletions

Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions (2014)

Achievable Rates for Channels With Deletions and Insertions

Low-Complexity Interactive Algorithms for Synchronization from Deletions, Insertions, and Substitutions

Reliable communication over channels with insertions, deletions, and substitutions

Marker codes for channels with insertions and deletions (2005)

Low-Complexity Interactive Algorithms for Synchronization From Deletions, Insertions, and Substitutions