Дэвид Маунт - Википедия - David Mount

Дэвид Маунт это профессор на Университет Мэриленда, Колледж-Парк отдел информатики, чьи исследования находятся в вычислительная геометрия.

биография

Маунт получил B.S. в области компьютерных наук в Университет Пердью в 1977 году и получил докторскую степень. получил степень бакалавра компьютерных наук в Университете Пердью в 1983 году под руководством Кристофа Хоффмана.

Он начал преподавать в Университет Мэриленда в 1984 году и является Профессор на кафедре информатики есть.[1]

В качестве учителя он получил награду декана Колледжа компьютерной математики и физических наук Мэрилендского университета за выдающиеся достижения в преподавании в 2005 и 1997 годах, а также другие награды в области преподавания, в том числе премию Гонконгской школы инженерии науки и технологий за выдающиеся успехи в преподавании. Признательность в 2001 году.

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

Основная область исследований Mounts - вычислительная геометрия, которая является ветвью алгоритмы посвящен решению задач геометрического характера. Это поле включает задачи из классических геометрия, словно проблема ближайшей пары точек, а также более современные прикладные задачи, такие как компьютерное представление и моделирование кривых и поверхностей. В частности, Маунт работал над k-означает кластеризацию проблема, поиск ближайшего соседа, и точка расположения.

Маунт работал над разработкой практических алгоритмов для кластеризации k-средних, известной как проблема NP-жесткий. Чаще всего используется алгоритм Алгоритм Ллойда, который является эвристическим по своей природе, но хорошо работает на практике. Он и другие позже показали [2] как k-d деревья может использоваться для ускорения алгоритма Ллойда. Они реализовали этот алгоритм вместе с некоторыми дополнительными улучшениями в библиотеке программного обеспечения. Kmeans.

Маунт работал над проблемами поиска ближайшего соседа и приблизительного ближайшего соседа. Позволяя алгоритму возвращать приблизительное решение для запроса ближайшего соседа, можно получить значительное ускорение пространственной и временной сложности. Один класс приближенных алгоритмов принимает в качестве входных данных расстояние ошибки, , и формирует структуру данных, которую можно эффективно хранить (низкая сложность пространства) и которая возвращает -приблизительный ближайший сосед быстро (низкая временная сложность). В соавторстве с Арьей, Нетаньяху, Р. Сильверман и А. Ву,[3] Маунт показал, что проблема приближенного ближайшего соседа может быть эффективно решена в пространствах низкой размерности. Структура данных, описанная в этой статье, легла в основу библиотеки с открытым исходным кодом ИНС для приблизительного поиска ближайшего соседа.[4] В последующей работе он исследовал вычислительная сложность приблизительного поиска ближайшего соседа. Вместе с соавторами Арьей и Маламатосом он обеспечил эффективное пространственно-временные компромиссы для приблизительного поиска ближайшего соседа,[5] на основе структуры данных, называемой AVD (или приблизительный Диаграмма Вороного ).

Mount также работал с местоположением точки, что включает предварительную обработку планарно-полигональное деление S размера для определения ячейки подразделения, в котором находится точка запроса.[6] В статье дается время построить структуру данных пространство, которое на вопрос, в какой ячейке находится точка запроса, занимает ожидаемое время куда это энтропия распределения вероятностей, в каких ячейках находятся точки запроса.

Помимо дизайна и анализ алгоритмов В области вычислительной геометрии Mount работал над реализацией эффективных алгоритмов в программных библиотеках, таких как:

  • ИНС - приблизительный поиск ближайшего соседа
  • ISODATA - эффективная реализация популярного алгоритма кластеризации
  • KMeans - кластеризация k-средних

Наиболее цитируемые работы

По состоянию на 8 декабря 2009 г., вот список его наиболее цитируемых работ (по данным Google ученый ) и их основные вклады, перечисленные в порядке убывания цитирования:

  1. Оптимальный алгоритм приближенного поиска ближайшего соседа в фиксированных размерах[3] - В этой статье они ставят n алгоритм (где зависит как от количества измерений и приблизительная погрешность ), чтобы найти соседа, который является не более чем фактором расстояние от ближайшего соседа.
  2. Эффективный алгоритм кластеризации k-средних: анализ и реализация[2] - В этой статье они обеспечивают более простую и эффективную реализацию Алгоритм Ллойда, который используется в k-означает кластеризацию. Алгоритм называется алгоритмом фильтрации.
  3. Дискретная геодезическая задача[7] - В этой статье они вычисляют кратчайший путь от источника до места назначения, ограниченный необходимостью путешествовать по поверхности заданного (возможно, невыпуклый ) многогранник. Их алгоритм принимает время нахождения первого кратчайшего пути к первому месту назначения и кратчайшего пути к любому дополнительному месту назначения (из того же источника) может быть вычислено в время. Здесь, количество вершин.

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

  1. ^ D. Mount. Биография Резюме В архиве 2009-11-27 на Wayback Machine
  2. ^ а б Т. Канунго, Д. М. Маунт, Н. С. Нетаньяху, С. Д. Пятко, Р. Сильверман и А. Ву. Эффективный алгоритм кластеризации k-средних: анализ и реализация. IEEE Transactions по анализу шаблонов и машинному анализу 24 (7): 881–892, 2002.
  3. ^ а б С. Арья, Д. М. Маунт, Н. С. Нетаньяху, Р. Сильверман и А. Ву, '"Оптимальный алгоритм приближенного поиска ближайшего соседа в фиксированных размерах", Журнал ACM, 45(6):891-923, 1998.
  4. ^ Д. М. Маунт и С. Арья, ANN: библиотека для приблизительного поиска ближайшего соседа
  5. ^ С. Арья, С., Т. Маламатос, Д. М. Маунт. Пространственно-временные компромиссы для приближенного поиска ближайшего соседа. Журнал ACM, 57 (1): 1-54, 2009.
  6. ^ С. Арья, Т. Маламатос, Д. М. Маунт и К. К. Вонг. Оптимальное расположение точки на плоскости для ожидаемого случая. SIAM Journal on Computing, 37 (2): 584-610, 2007.
  7. ^ Дж. С. Б. Митчелл, Д. М. Маунт и К. Х. Пападимитриу. Дискретная геодезическая задача. SIAM Journal of Computing, 16 (4): 647-668, 1987.

внешняя ссылка