David Karger

David Karger

David Karger is a Professor of Computer Science and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL) at the Massachusetts Institute of Technology (MIT). He received an AB from Harvard University and a PhD in computer science from Stanford University.[1] Dr. Karger's dissertation received the 1994 ACM doctoral dissertation award and the Mathematical Programming Society's 1997 Tucker Prize. He also received the National Academy of Science's 2004 Award for Initiative in Research.

David Karger's work in algorithms has focused on applications of randomization to optimization problems and led to significant progress on several core problems. He is responsible for Karger's algorithm, a Monte Carlo method to compute the minimum cut of a connected graph.[2] Dr. Karger developed the fastest minimum spanning tree algorithm to date with Philip Klein, and Robert Tarjan. They found a linear time randomized algorithm based on a combination of Borůvka's algorithm and the reverse-delete algorithm.[3] With Ion Stoica, Robert Morris, Frans Kaashoek, and Hari Balakrishnan, he also developed Chord, one of the four original distributed hash table protocols.[4]

Dr. Karger has also conducted research in the area of information retrieval and personal information management. This work has focused on new interfaces and algorithms for helping people sift effectively through large masses of information. While at Xerox PARC, he worked on the Scatter/Gather system, which hierarchically clustered a document collection and allow the user to gather clusters at different levels and rescatter them.[5] More recently he has been researching retrieval systems that personalize themselves to best fit their individual users' needs and behaviors, leading the Haystack project.

Dr. Karger is married to Allegra Goodman, an American author. The couple lives in Cambridge, Massachusetts and has four children, three boys and a girl.[6]

References

  1. ^ "David Karger CSAIL". http://www.csail.mit.edu/user/1542. Retrieved 13 March 2011. 
  2. ^ Karger, David. "Global Min-cuts in RNC and Other Ramifications of a Simple Mincut Algorithm". Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993. http://people.csail.mit.edu/karger/Papers/mincut.ps. 
  3. ^ Karger, D. R., Klein, P. N., and Tarjan, R. E. 1995. A randomized linear-time algorithm to find minimum spanning trees. J. ACM 42, 2 (Mar. 1995), 321–328.
  4. ^ Stoica, Ion et al. (2001). "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications". Proceedings of SIGCOMM'01 (ACM Press New York, NY, USA). 
  5. ^ Cutting, Douglass, Karger, David, Pedersen, Jan, and Tukey, John W.. "Scatter/Gather: A Cluster-based Approach to Browsing Large Document Collections". Proceedings of the 15th Annual International ACM/SIGIR Conference, Copenhagen, 1992.. ftp://parcftp.xerox.com/pub/qca/scattergather.ps. 
  6. ^ "About Allegra". http://www.allegragoodman.com/goodman-biography.htm. Retrieved 13 March 2011. 

External links


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • David Sheffield Bell — is a retired[1] physician who established a private practice in general medicine in the town of Lyndonville, New York starting in 1979.[2] He has researched extensively on the clinical aspects of chronic fatigue syndrome (CFS). He has also… …   Wikipedia

  • Karger's algorithm — In computer science and graph theory, the Karger s algorithm is a Monte Carlo method to compute the minimum cut of a connected graph.AlgorithmThe idea of the algorithm is based on the concept of contraction of an edge e in a graph. Informally… …   Wikipedia

  • David Duke — This article is about the white nationalist. For the Scottish football player, see David Duke (footballer). David Duke …   Wikipedia

  • Allegra Goodman — Infobox Writer imagesize = 150px name = Allegra Goodman caption = pseudonym = birthname = birthdate = birth year and age|1967 birthplace = deathdate = deathplace = occupation = novelist nationality = American period = 1996 current genre =… …   Wikipedia

  • Human Computer Information Retrieval — The fields of human computer interaction (HCI) and information retrieval (IR) have both developed innovative techniques to address the challenge of navigating the complex information spaces, but their insights have to date often failed to cross… …   Wikipedia

  • The Sing-Off — (The Sing Off) Genre Reality television Format Interactive Presented by Nick Lachey Judges Ben Folds Shawn Stockman …   Wikipedia

  • Illinois Security Lab — The Illinois Security Lab is a research laboratory at the University of Illinois Urbana Champaign established in 2004 to support research and education in computer and network security. The lab is part of the UIUC Computer Science Department and… …   Wikipedia

  • Distributed hash table — A distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to a hash table; (key, value) pairs are stored in a DHT, and any participating node can efficiently retrieve the value… …   Wikipedia

  • Infranet — The Infranet is a prospective architecture for the Internet and future packet based telecommunications networks. Currently the Internet s architecture is largely the result of the emergent behavior of the interacting protocols on the Internet and …   Wikipedia

  • Chord (peer-to-peer) — In computing, Chord is a protocol and algorithm for a peer to peer distributed hash table. A distributed hash table stores key value pairs by assigning keys to different computers (known as nodes ); a node will store the values for all the keys… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”