We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Robust Set Reconciliation via Locality Sensitive Hashing

Formal Metadata

Title
Robust Set Reconciliation via Locality Sensitive Hashing
Title of Series
Number of Parts
155
Author
License
CC Attribution 3.0 Germany:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
We consider variations of set reconciliation problems where two parties, Alice and Bob, each hold a set of points in a metric space, and the goal is for Bob to conclude with a set of points that is close to Alice's set of points in a well-defined way. This setting has been referred to as robust set reconciliation. In one variation, the goal is for Bob to end with a set of points that is close to Alice's in earth mover's distance, and in another the goal is for Bob to have a point that is close to each of Alice's. The first problem has been studied before; while previous results achieved an O(d) approximation, where d is the dimension of the space, we achieve an O(log n) approximation, where n is the number of points. The second problem appears new, and here we find schemes that, under certain conditions, use sublinear communication. Our primary novelty is utilizing Invertible Bloom Lookup Tables in combination with locality sensitive hashing. This combination allows us to cope with the geometric setting in a communication-efficient manner.