Дэвид Каргер - David Karger

Дэвид Каргер
Родившийся
Дэвид Рон Каргер

(1967-05-01) 1 мая 1967 г. (возраст 53 года)
Альма-матерГарвардский университет
Стэндфордский Университет
ИзвестенАлгоритм Каргера
Аккорд (одноранговый)
Последовательное хеширование
Супруг (а)Аллегра Гудман
НаградыЧлен ACM
Научная карьера
ПоляУправление информацией
Взаимодействие человека с компьютером
Семантическая сеть
PIM[1]
УчрежденияГарвардский университет
Стэндфордский Университет
Массачусетский технологический институт
Xerox PARC
ТезисСлучайная выборка в задачах оптимизации графов  (1995)
ДокторантРаджив Мотвани[2]
Докторанты
Интернет сайтлюди.csail.mit.edu/ karger

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

Образование

Каргер получил Бакалавр искусств степень от Гарвардский университет и докторскую степень в Информатика из Стэндфордский Университет.[3]

Исследование

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

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

Награды

Каргер получил в 1994 г. ACM докторская диссертация и Общество математического программирования Приз Такера 1997 года. Он также получил Национальная академия наук Премия 2004 года за инициативу в области исследований.

Личное

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

Рекомендации

  1. ^ Дэвид Каргер публикации, проиндексированные Google ученый
  2. ^ а б Дэвид Каргер на Проект "Математическая генеалогия"
  3. ^ "Дэвид Каргер CSAIL". Получено 13 марта 2011.
  4. ^ Каргер, Дэвид. «Глобальные минимальные сокращения в RNC и другие разветвления простого алгоритма сокращения». Материалы 4-го ежегодного симпозиума ACM-SIAM по дискретным алгоритмам, январь 1993 г.
  5. ^ Karger, D. R .; Klein, P.N .; Тарьян, Р. Э. (1995). «Рандомизированный алгоритм линейного времени для поиска минимальных остовных деревьев». Журнал ACM. 42 (2): 321. CiteSeerX  10.1.1.39.9012. Дои:10.1145/201019.201022.
  6. ^ Стойка, И.; Morris, R .; Каргер, Д.; Kaashoek, M. F .; Балакришнан, Х. (2001). «Chord: масштабируемая одноранговая служба поиска для интернет-приложений» (PDF). Обзор компьютерных коммуникаций ACM SIGCOMM. 31 (4): 149. Дои:10.1145/964723.383071.
  7. ^ Раскрой, Д. Р .; Karger, D. R .; Pedersen, J. O .; Тьюки, Дж. У. (1992). «Scatter / Gather: кластерный подход к просмотру больших коллекций документов». Материалы 15-й ежегодной международной конференции ACM SIGIR по исследованиям и разработкам в области информационного поиска - SIGIR '92. п. 318. CiteSeerX  10.1.1.34.6746. Дои:10.1145/133160.133214. ISBN  978-0897915236.
  8. ^ "Об Аллегре". Архивировано из оригинал 24 июня 2011 г.. Получено 13 марта 2011.