Дэвид Маунт

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

Биография

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

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

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

Исследовать

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

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

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

Маунт также работал над определением местоположения точки, что включает предварительную обработку плоского многоугольного подразделения S размером для определения ячейки подразделения, в которой находится точка запроса. ^[6] В статье приводится время построения структуры данных пространства, которая при запросе о том, в какой ячейке находится точка запроса, занимает ожидаемое время, где — энтропия распределения вероятностей того, в каких ячейках находятся точки запроса. $n$ $O(nlogn)$ $O(n)$ $H+O({\sqrt {H}}+1)$ $H$

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

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

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

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

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

Признание

Маунт был включен в число стипендиатов ACM 2022 года «за вклад в алгоритмы и структуры данных для геометрического анализа и поиска данных» ^{[8] .}

Ссылки

^ Д. Маунт. Биография. Архивировано 27 ноября 2009 г. на Wayback Machine.
^ ab T. Kanungo, DM Mount, NS Netanyahu , CD Piatko , R. Silverman и A. Wu . Эффективный алгоритм кластеризации k-средних: анализ и реализация. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(7):881-–892, 2002.
^ ab S. Arya, DM Mount, NS Netanyahu , R. Silverman и A. Wu , «Оптимальный алгоритм для приближенного поиска ближайшего соседа в фиксированных измерениях», Journal of the ACM , 45(6):891-923, 1998.
^ DM Mount и S. Arya, ANN: Библиотека для приблизительного поиска ближайшего соседа
^ S. Arya, S., T. Malamatos и DM Mount. Пространственно-временные компромиссы для приближенного поиска ближайшего соседа. Журнал ACM, 57(1): 1-54, 2009
^ S. Arya, T. Malamatos, DM Mount и KC Wong. Оптимальное ожидаемое расположение точек на плоскости. Журнал SIAM по вычислениям, 37(2):584-610, 2007.
^ JSB Mitchell, DM Mount и CH Papadimitriou. Дискретная геодезическая задача. SIAM Journal of Computing, 16(4):647-668, 1987
^ "Глобальная вычислительная ассоциация называет 57 стипендиатов за выдающийся вклад, который движет сегодняшними технологиями". Ассоциация вычислительной техники. 18 января 2023 г. Получено 18 января 2023 г.

Внешние ссылки

Официальный сайт
Структуры данных и алгоритмы в C++
Google Академия