Reconciling Differences
Mon., Feb 6, 2012
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).

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