Reconciling Differences

Mon., Feb 6, 2012

2:00 - 3:00 PM

521 Cory (Hogan room)

2:00 - 3:00 PM

521 Cory (Hogan room)

If you and I both have a million song titles, of which almost
all are the same, how can we efficiently communicate the songs that
are different? I will describe a new and practical algorithm (joint
work with D. Eppstein, M. Goodrich, and F. Uyeda) for computing the
set difference using communication proportional to the difference,
linear computation, and small latency. A key component is a new
estimator for the set difference that outperforms earlier estimators
such as MinWise sketches for small values of the set difference.
Potential applications include trading blocks in a peer-to-peer
environment, link state routing and data deduplication. I will show
that the similarity to the "peeling algorithm" used in say Tornado
codes is not surprising because there is a reduction from set
difference to coding. In the second part I will describe
generalizations to reconciling sequences under the edit distance
metric (joint work with J. Ullman), and to reconciling sets on graphs
(a generalization of the celebrated rumor spreading problem, joint
work with N. Goyal and R. Kannan). A "Steiner" version of the graph
problem suggests new network coding problems. If time permits, I will
describe an unexpected but simple connection that shows that the basic
data structure can be used to design new error correction codes that
are efficiently decodable (joint work with M. Mitzenmacher).

Bio:

George Varghese worked at DEC for several years designing DECNET protocols and products (bridge architecture, Gigaswitch) before obtaining his Ph.D in 1992 from MIT. He worked from 1993-1999 at Washington University. He joined UCSD in 1999, where he currently is a professor of computer science. He won the ONR Young Investigator Award in 1996, and was elected to be a Fellow of the Association for Computing Machinery (ACM) in 2002. Together with colleagues, he has 16 patents awarded in the general field of Network Algorithmics. Several of the algorithms he has helped develop have found their way into commercial systems including Linux (timing wheels), the Cisco GSR (DRR), and Microsoft Windows (IP lookups). He also helped design the lookup engine for Procket's 40 Gbps forwarding engine. He has written a book on building fast router and endnode implementations called "Network Algorithmics", which was published in December 2004 by Morgan-Kaufman. In May 2004, he co-founded NetSift Inc., where he was the President and CTO. NetSift was acquired by Cisco Systems in 2005. For the 2010-2011 academic year, he was the Distinguished Visitor in the Computer Science department at Stanford University. He is spending the 2011-2012 year on leave at Yahoo Research in Santa Clara.

Bio:

George Varghese worked at DEC for several years designing DECNET protocols and products (bridge architecture, Gigaswitch) before obtaining his Ph.D in 1992 from MIT. He worked from 1993-1999 at Washington University. He joined UCSD in 1999, where he currently is a professor of computer science. He won the ONR Young Investigator Award in 1996, and was elected to be a Fellow of the Association for Computing Machinery (ACM) in 2002. Together with colleagues, he has 16 patents awarded in the general field of Network Algorithmics. Several of the algorithms he has helped develop have found their way into commercial systems including Linux (timing wheels), the Cisco GSR (DRR), and Microsoft Windows (IP lookups). He also helped design the lookup engine for Procket's 40 Gbps forwarding engine. He has written a book on building fast router and endnode implementations called "Network Algorithmics", which was published in December 2004 by Morgan-Kaufman. In May 2004, he co-founded NetSift Inc., where he was the President and CTO. NetSift was acquired by Cisco Systems in 2005. For the 2010-2011 academic year, he was the Distinguished Visitor in the Computer Science department at Stanford University. He is spending the 2011-2012 year on leave at Yahoo Research in Santa Clara.

UC Berkeley Networking

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016

Ashwin Pananjady and Orhan Ocal

Last Modification Date: Wednesday, February 10, 2016