stringtranslate.com

Дэвид Каргер

Дэвид Рон Каргер (родился 1 мая 1967 года) — американский учёный-компьютерщик, профессор и член Лаборатории компьютерных наук и искусственного интеллекта ( CSAIL ) Массачусетского технологического института .

Образование

Каргер получил степень бакалавра гуманитарных наук в Гарвардском университете и степень доктора философии в области компьютерных наук в Стэнфордском университете . [3]

Исследовать

Работа Каргера в области алгоритмов была сосредоточена на применении рандомизации к задачам оптимизации и привела к значительному прогрессу в решении нескольких основных проблем. Он отвечает за алгоритм Каргера , метод Монте-Карло для вычисления минимального разреза связного графа. [4] Каргер разработал самый быстрый алгоритм минимального остовного дерева на сегодняшний день совместно с Филиппом Клейном и Робертом Тарьяном . Они нашли линейный по времени рандомизированный алгоритм, основанный на комбинации алгоритма Борувки и алгоритма обратного удаления. [5] Совместно с Ионом Стойкой , Робертом Моррисом , Франсом Каашоеком и Хари Балакришнаном он также разработал Chord , один из четырех оригинальных протоколов распределенных хэш-таблиц . [6]

Каргер проводил исследования в области поиска информации и управления персональной информацией . Эта работа была сосредоточена на новых интерфейсах и алгоритмах, помогающих людям эффективно просеивать большие массивы информации. Работая в Xerox PARC , он работал над системой Scatter/Gather, которая иерархически кластеризовала коллекцию документов и позволяла пользователю собирать кластеры на разных уровнях и повторно рассеивать их. [7] Совсем недавно [ когда? ] он исследовал системы поиска, которые персонализируются, чтобы наилучшим образом соответствовать потребностям и поведению своих индивидуальных пользователей, возглавляя проект Haystack . Дэвид Каргер также является частью Confer: инструмента для участников конференций, используемого многими исследовательскими конференциями.

Награды

Диссертация Каргера получила докторскую диссертацию ACM в 1994 году [8] и премию Такера от Общества математического программирования в 1997 году. [9] Он также получил премию Национальной академии наук за инициативу в исследованиях в 2004 году. [10]

Личный

Каргер женат на Аллегре Гудман , американской писательнице. Пара живет в Кембридже, Массачусетс , у них четверо детей, три мальчика и девочка. [11]

Ссылки

  1. ^ Публикации Дэвида Каргера, проиндексированные Google Scholar
  2. ^ Дэвид Каргер из проекта «Генеалогия математики»
  3. ^ "David Karger CSAIL" . Получено 13 марта 2011 г.
  4. ^ Каргер, Дэвид. «Глобальные минимальные разрезы в RNC и другие последствия простого алгоритма минимальных разрезов». Труды 4-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, январь 1993 г.
  5. ^ Каргер, DR; Кляйн, PN; Тарьян, RE (1995). "Рандомизированный линейный алгоритм поиска минимальных остовных деревьев". Журнал ACM . 42 (2): 321. CiteSeerX 10.1.1.39.9012 . doi :10.1145/201019.201022. S2CID  832583. 
  6. ^ Стоика, И .; Моррис, Р.; Каргер, Д.; Каашук, М.Ф.; Балакришнан, Х. (2001). «Аккорд: масштабируемая одноранговая служба поиска для интернет-приложений» (PDF) . Обзор компьютерной связи ACM SIGCOMM . 31 (4): 149. doi :10.1145/964723.383071.
  7. ^ Каттинг, DR; Каргер, DR; Педерсен, 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.
  8. ^ "David Karger". Главная страница наград . Ассоциация вычислительной техники . Получено 2021-01-23 .
  9. ^ "AW Tucker Prize - Победители прошлых лет". Премии Общества математической оптимизации . Общество математической оптимизации .
  10. ^ "Лауреаты премии Уильяма О. Бейкера за инициативы в области исследований". О премии Уильяма О. Бейкера за инициативы в области исследований . Национальная академия наук .
  11. ^ "About Allegra". Архивировано из оригинала 24 июня 2011 года . Получено 13 марта 2011 года .