| Дэвид Каргер | |
|---|---|
| Родившийся | Дэвид Рон Каргер 1 мая 1967 г. |
| Альма-матер | Гарвардский университет Стэнфордский университет |
| Известен | Алгоритм Каргера Chord (одноранговая сеть) Согласованное хеширование |
| Супруг (а) | Аллегра Гудман |
| Награды | Член ACM |
| Научная карьера | |
| Поля | Управление информацией Взаимодействие человека и компьютера с семантической сетью PIM [1] |
| Учреждения | Гарвардский университет Стэнфордский университет MIT Xerox PARC |
| Тезис | Случайная выборка в задачах оптимизации графов (1995) |
| Докторант | Раджив Мотвани [2] |
| Докторанты | |
| Веб-сайт | люди |
Дэвид Рон Каргер (родился 1 мая 1967 г.) - профессор компьютерных наук и сотрудник Лаборатории компьютерных наук и искусственного интеллекта ( CSAIL ) Массачусетского технологического института .
Образование [ править ]
Karger получил степень бакалавра искусств диплома Гарвардского университета и степень доктора философии в области информатики из Стэнфордского университета . [3]
Исследование [ править ]
Работа Каргера в области алгоритмов была сосредоточена на применении рандомизации к задачам оптимизации и привела к значительному прогрессу в нескольких основных проблемах. Он отвечает за алгоритм Каргера , метод Монте-Карло для вычисления минимального разреза связного графа. [4] Каргер вместе с Филипом Кляйном и Робертом Тарьяном разработал самый быстрый алгоритм минимального остовного дерева на сегодняшний день . Они нашли линейный рандомизированный алгоритм времени , основанный на комбинации алгоритма Борувки и алгоритма обратного удаления. [5] С Ионом Стойкой , Робертом Моррисом , Франс Каашук и Хари Балакришнан , он также разработал Chord , один из четырех исходных протоколов распределенных хеш-таблиц . [6]
Karger проводил исследования в области поиска информации и управления персональной информацией . Эта работа была сосредоточена на новых интерфейсах и алгоритмах, помогающих людям эффективно просеивать большие массивы информации. Находясь в Xerox PARC , он работал над системой Scatter / Gather, которая иерархически кластеризовала коллекцию документов и позволяла пользователю собирать кластеры на разных уровнях и повторно разбрасывать их. [7] Совсем недавно [ когда? ] он исследовал поисковые системы, которые персонализируются так, чтобы наилучшим образом соответствовать потребностям и поведению их индивидуальных пользователей, и возглавил Haystackпроект. Дэвид Каргер также является частью Confer: инструмента для участников конференций, используемого на многих исследовательских конференциях.
Награды [ править ]
Диссертация Каргера была удостоена награды ACM в 1994 году [8] и премии Такера Общества математического программирования в 1997 году. [9] Он также получил премию Национальной академии наук 2004 года за инициативу в области исследований. [10]
Личный [ править ]
Каргер женат на Аллегре Гудман , американском писателе. Пара живет в Кембридже, штат Массачусетс, у них четверо детей, трое мальчиков и девочка. [11]
Ссылки [ править ]
- ^ Публикации Дэвида Каргера, проиндексированные Google Scholar
- ^ а б Дэвид Каргер в проекте « Математическая генеалогия»
- ^ "Дэвид Каргер CSAIL" . Проверено 13 марта 2011 года .
- ^ Каргер, Дэвид. «Глобальные минимальные сокращения в RNC и другие разветвления простого алгоритма минимальных сокращений» . Материалы 4-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, январь 1993 г.
- ^ Karger, DR; Klein, PN; Tarjan, RE (1995). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев». Журнал ACM . 42 (2): 321. CiteSeerX 10.1.1.39.9012 . DOI : 10.1145 / 201019.201022 . S2CID 832583 .
- ^ Stoica, I .; Morris, R .; Каргер, Д .; Kaashoek, MF; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска для интернет-приложений» (PDF) . Обзор компьютерных коммуникаций ACM SIGCOMM . 31 (4): 149. DOI : 10,1145 / 964723,383071 .
- ^ Резка, DR; Karger, DR; Pedersen, JO; Тьюки, JW (1992). «Scatter / Gather: кластерный подход к просмотру больших коллекций документов». Материалы 15-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска - SIGIR '92 . п. 318. CiteSeerX 10.1.1.34.6746 . DOI : 10.1145 / 133160.133214 . ISBN 978-0897915236. S2CID 373655 .
- ^ "Дэвид Каргер" . Награды Дом . Ассоциация вычислительной техники . Проверено 23 января 2021 .
- ^ «Приз А.В. Такера - Победители прошлого» . Премии Общества математической оптимизации . Общество математической оптимизации .
- ^ "Премия Уильяма О. Бейкера за инициативы в области исследования получателей" . О премии Уильяма О. Бейкера за инициативы в области исследований . Национальная академия наук .
- ^ «Об Аллегре» . Архивировано из оригинального 24 июня 2011 года . Проверено 13 марта 2011 года .
