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

Formale Metadaten

Titel
Robust Set Reconciliation via Locality Sensitive Hashing
Serientitel
Anzahl der Teile
155
Autor
Lizenz
CC-Namensnennung 3.0 Deutschland:
Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.