{"id":{"repo_id":"bu","oai_identifier":"oai:open.bu.edu:2144/36028"},"canonical_url":"https://search.ndltd.org/etd/bu/oai:open.bu.edu:2144/36028","repository":{"repo_id":"bu","name":"Boston University","base_url":"https://open.bu.edu/oai/request"},"display":{"title":"Scalable string reconciliation by recursive content-dependent shingling","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Song, Bowen"],"institution":"Boston University","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Electrical & Computer Engineering","degree_department":null,"school":null,"contributors":[],"advisors":["Trachtenberg, Ari"],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-11-19T02:41:09Z","subjects":["Computer engineering"],"languages":["en_US"],"rights":["Attribution-ShareAlike 4.0 International"],"rights_urls":["http://creativecommons.org/licenses/by-sa/4.0/"],"identifier_entries":[],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2144/36028","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/2144/36028","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://open.bu.edu/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aopen.bu.edu%3A2144%2F36028","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Trachtenberg, Ari"]},{"key":"dc:creator","label":"Author","values":["Song, Bowen"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2019-06-21T18:20:09Z"]},{"key":"dc:date.embargo","label":"Dc Date Embargo","values":["2019-12-03T00:00:00Z"]},{"key":"dc:date.issued","label":"Date","values":["2019"]},{"key":"dc:date.updated","label":"Dc Date Updated","values":["2019-06-04T01:05:26Z"]},{"key":"dc:type","label":"Dc Type","values":["Thesis/Dissertation"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical & Computer Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Boston University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer engineering"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["Attribution-ShareAlike 4.0 International"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://creativecommons.org/licenses/by-sa/4.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/2144/36028"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Scalable string reconciliation by recursive content-dependent shingling"]}]}],"canonical_facts":{"dc:contributor.advisor":["Trachtenberg, Ari"],"dc:creator":["Song, Bowen"],"dc:date.accessioned":["2019-06-21T18:20:09Z"],"dc:date.embargo":["2019-12-03T00:00:00Z"],"dc:date.issued":["2019"],"dc:date.updated":["2019-06-04T01:05:26Z"],"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."],"dc:identifier.uri":["https://hdl.handle.net/2144/36028"],"dc:language.iso":["en_US"],"dc:rights":["Attribution-ShareAlike 4.0 International"],"dc:rights.uri":["http://creativecommons.org/licenses/by-sa/4.0/"],"dc:subject":["Computer engineering"],"dc:title":["Scalable string reconciliation by recursive content-dependent shingling"],"dc:type":["Thesis/Dissertation"],"thesis:degree_discipline":["Electrical & Computer Engineering"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Boston University"]},"updated_at":"2026-11-19T02:41:09Z"}