David Karger - David Karger
David Karger | |
---|---|
narozený | David Ron Karger 1. května 1967 |
Alma mater | Harvardská Univerzita Stanfordská Univerzita |
Známý jako | Kargerův algoritmus Chord (peer-to-peer) Důsledné hašování |
Manžel (y) | Allegra Goodman |
Ocenění | Člen ACM |
Vědecká kariéra | |
Pole | Správa informací Interakce člověk-počítač Sémantický web PIM[1] |
Instituce | Harvardská Univerzita Stanfordská Univerzita MIT Xerox PARC |
Teze | Náhodné vzorkování při problémech s optimalizací grafů (1995) |
Doktorský poradce | Rajeev Motwani[2] |
Doktorandi | |
webová stránka | lidé |
David Ron Karger (narozen 1. května 1967) je profesorem informatiky a členem Laboratoře výpočetní techniky a umělé inteligence (CSAIL ) na Massachusetts Institute of Technology.
Vzdělávání
Karger dostal a Bakalář umění stupně od Harvardská Univerzita a doktorát v počítačová věda z Stanfordská Univerzita.[3]
Výzkum
Kargerova práce v algoritmech se zaměřila na aplikace randomizace na optimalizační problémy a vedla k významnému pokroku u několika klíčových problémů. Je zodpovědný za Kargerův algoritmus, a Metoda Monte Carlo vypočítat minimální řez připojeného grafu.[4] Karger vyvinul nejrychleji minimální kostra algoritmus k dnešnímu dni, s Philipem Kleinem a Robert Tarjan. Našli a lineární čas randomizovaný algoritmus na základě kombinace Borůvkův algoritmus a algoritmus zpětného mazání.[5] S Ion Stoica, Robert Morris, Frans Kaashoek, a Hari Balakrishnan, on také vyvinul Akord, jeden ze čtyř originálů distribuovaná hash tabulka protokoly.[6]
Karger provedl výzkum v oblasti vyhledávání informací a správa osobních údajů. Tato práce se zaměřila na nová rozhraní a algoritmy, které pomáhají lidem efektivně procházet velkým množstvím informací. Zatímco v Xerox PARC pracoval na systému Scatter / Gather, který hierarchicky seskupil kolekci dokumentů a umožnil uživateli shromažďovat shluky na různých úrovních a znovu je rozptýlit.[7] Poslední dobou[když? ] zkoumá vyhledávací systémy, které se přizpůsobují tak, aby co nejlépe vyhovovaly potřebám a chování jejich jednotlivých uživatelů, a vedl Kupka sena projekt. David Karger je také součástí konference: nástroj pro účastníky konference používaný mnoha výzkumnými konferencemi.
Ocenění
![]() | Tato část a životopis živé osoby ne zahrnout žádný odkazy nebo zdroje.Září 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Kargerova disertační práce byla přijata v roce 1994 ACM ocenění doktorské disertační práce a Společnost pro matematické programování Tuckerova cena z roku 1997. Také obdržel Národní akademie věd Cena 2004 za iniciativu ve výzkumu.
Osobní
Karger je ženatý Allegra Goodman, americký autor. Pár žije v Cambridge, Massachusetts a mají čtyři děti, tři chlapce a dívku.[8]
Reference
- ^ David Karger publikace indexované podle Google Scholar
- ^ A b David Karger na Matematický genealogický projekt
- ^ „David Karger CSAIL“. Citováno 13. března 2011.
- ^ Karger, David. „Globální minimální škrty v RNC a další důsledky jednoduchého mincutového algoritmu“. Proceedings of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, January 1993.
- ^ Karger, D. R .; Klein, P. N .; Tarjan, R. E. (1995). Msgstr "Randomizovaný algoritmus lineárního času pro nalezení minimálních rozpětí stromů". Deník ACM. 42 (2): 321. CiteSeerX 10.1.1.39.9012. doi:10.1145/201019.201022.
- ^ Stoica, I.; Morris, R .; Karger, D.; Kaashoek, M. F .; Balakrishnan, H. (2001). „Chord: Škálovatelná vyhledávací služba peer-to-peer pro internetové aplikace“ (PDF). Recenze počítačové komunikace ACM SIGCOMM. 31 (4): 149. doi:10.1145/964723.383071.
- ^ Cutting, D. R .; Karger, D. R .; Pedersen, J. O .; Tukey, J. W. (1992). "Scatter / Gather: klastrový přístup k procházení velkých sbírek dokumentů". Sborník z 15. ročníku mezinárodní konference ACM SIGIR o výzkumu a vývoji v získávání informací - SIGIR '92. p. 318. CiteSeerX 10.1.1.34.6746. doi:10.1145/133160.133214. ISBN 978-0897915236.
- ^ „About Allegra“. Archivovány od originál dne 24. června 2011. Citováno 13. března 2011.