TU Berlin

Internet Network ArchitecturesPublications by Type: Conference and Workshop Papers

Inhalt

zur Navigation

Es gibt keine deutsche Übersetzung dieser Webseite.

Publications by Type: Conference and Workshop Publications

see also conference papers, workshop papers, demos, and posters. (under construction)

Estimating the number of differences between remote sets
Zitatschlüssel AT-ENDBRS-06
Autor Agarwal, Sachin and Trachtenberg, Ari
Buchtitel IEEE Information Theory Workshop (ITW)
Seiten 217–221
Jahr 2006
ISBN 1-4244-0035-X
DOI http://dx.doi.org/10.1109/ITW.2006.1633815
Ort Punta del Este, Uruguay
Monat March
Zusammenfassung We consider the problem of approximating the number of differences between sets held on remote hosts using minimum communication. Efficient solutions to this problem are important for streamlining a variety of communication sensitive network applications, including data synchronization in mobile networks, gossip protocols and content delivery networks. Using tools from the field of interactive communication, we show that this problem requires about as much communication as the problem of exactly determining such differences. As a result, we propose a heuristic solution based on the counting Bloom filter. We provide analytic bounds on the expected performance of our protocol and also experimental evidence that they can outperform existing difference approximation techniques.
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe