David Eppstein - Publications

Publications with Frank Uyeda

• What's the difference? Efficient set reconciliation without prior context.
  D. Eppstein, M. T. Goodrich, F. Uyeda, and G. Varghese.
  Proc. ACM SIGCOMM, Toronto, Canada, 2011.

  We determine the symmetric difference between two similar sets of items, held by different machines on the internet, using an amount of communication bandwidth that is proportional only to the difference between the sets and with low computational overhead. Our solution technique combines the invertible Bloom filter data structure from our previous work on streaming straggler detection with a randomized sampling scheme that allows us to accurately and efficiently estimate the size of the difference.