Back to search

Boston University

Scalable string reconciliation by recursive content-dependent shingling

Abstract

dc:description.abstract

We consider the problem of reconciling similar strings in a distributed system. Specifically, we are interested in performing this reconciliation in an efficient manner, minimizing the communication cost. Our problem applies to several types of large-scale distributed networks, file synchronization utilities, and any system that manages the consistency of string encoded ordered data. We present the novel Recursive Content-Dependent Shingling (RCDS) protocol that can handle large strings and has the communication complexity that scales with the edit distance between the reconciling strings. Also, we provide analysis, experimental results, and comparisons to existing synchronization software such as the Rsync utility with an implementation of our protocol.

Degree

thesis:*
Name thesis:degree_name
Master of Science
Level thesis:degree_level
masters
Discipline thesis:degree_discipline
Electrical & Computer Engineering
Grantor
Boston University
Year dc:date.issued
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Song, Bowen
Advisor dc:contributor.advisor
  • Trachtenberg, Ari

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Attribution-ShareAlike 4.0 International
Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/2144/36028

Chain of custody

source
Harvested from
Boston University
Base URL
open.bu.edu/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Song, Bowen. Scalable string reconciliation by recursive content-dependent shingling. masters thesis, Boston University, 2019. https://hdl.handle.net/2144/36028