monte david

informático estadounidense

David Mount es profesor del departamento de informática de College Park de la Universidad de Maryland, cuya investigación se centra en geometría computacional .

Biografía

Mount recibió una licenciatura en Ciencias de la Computación en la Universidad Purdue en 1977 y recibió su doctorado. en Ciencias de la Computación en la Universidad Purdue en 1983 bajo la dirección de Christoph Hoffmann.

Comenzó a enseñar en la Universidad de Maryland en 1984 y es profesor en el departamento de Ciencias de la Computación de allí. ^[1]

Como docente, ganó el Premio del Decano a la Excelencia en la Enseñanza de la Facultad de Ciencias Físicas y Matemáticas Informáticas de la Universidad de Maryland en 2005 y 1997, así como otros premios de enseñanza, incluido el Premio a la Excelencia en la Enseñanza de la Escuela de Ingeniería de Ciencia y Tecnología de Hong Kong. Revalorización en 2001.

Investigación

La principal área de investigación de Mounts es la geometría computacional , que es la rama de los algoritmos dedicada a la resolución de problemas de naturaleza geométrica. Este campo incluye problemas de geometría clásica , como el problema del par de puntos más cercano , así como problemas aplicados más recientes, como la representación por computadora y el modelado de curvas y superficies. En particular, Mount ha trabajado en el problema de agrupación de k-medias , la búsqueda del vecino más cercano y el problema de ubicación de puntos .

Mount ha trabajado en el desarrollo de algoritmos prácticos para la agrupación de k-medias, un problema conocido por ser NP-duro . El algoritmo más común utilizado es el algoritmo de Lloyd , que es de naturaleza heurística pero funciona bien en la práctica. Él y otros demostraron más tarde ^[2] cómo se podrían utilizar los árboles kd para acelerar el algoritmo de Lloyd. Han implementado este algoritmo, junto con algunas mejoras adicionales, en la biblioteca de software Kmeans .

Mount ha trabajado en los problemas de búsqueda del vecino más cercano y del vecino más cercano aproximado. Al permitir que el algoritmo devuelva una solución aproximada a la consulta del vecino más cercano, se puede obtener una aceleración significativa en la complejidad del espacio y el tiempo. Una clase de algoritmos aproximados toma como entrada la distancia de error, y forma una estructura de datos que se puede almacenar eficientemente (baja complejidad espacial) y que devuelve rápidamente el vecino más cercano aproximado (baja complejidad temporal). En un trabajo en coautoría con Arya, Netanyahu , R. Silverman y A. Wu , ^[3] Mount demostró que el problema del vecino más cercano aproximado podría resolverse eficientemente en espacios de baja dimensión. La estructura de datos descrita en ese artículo formó la base de la biblioteca de código abierto ANN para la búsqueda aproximada del vecino más cercano. ^[4] En trabajos posteriores, investigó la complejidad computacional de la búsqueda aproximada del vecino más cercano. Junto con los coautores Arya y Malamatos, proporcionó compensaciones espacio-temporales eficientes para la búsqueda aproximada del vecino más cercano, ^[5] basándose en una estructura de datos llamada AVD (o diagrama aproximado de Voronoi ). ${\displaystyle \epsilon }$ ${\displaystyle (1+\epsilon )}$

Mount también ha trabajado en la ubicación de puntos, que implica el preprocesamiento de una subdivisión poligonal plana S de tamaño para determinar la celda de una subdivisión en la que se encuentra un punto de consulta. ^[6] El artículo proporciona un tiempo para construir una estructura de datos del espacio que cuando se le solicita en qué celda se encuentra un punto de consulta, toma el tiempo esperado dónde está la entropía de la distribución de probabilidad de en qué celdas se encuentran los puntos de consulta. ${\displaystyle n}$ ${\displaystyle O(nlogn)}$ ${\displaystyle O(n)}$ ${\displaystyle H+O({\sqrt {H}}+1)}$ ${\displaystyle H}$

Además del diseño y análisis de algoritmos en geometría computacional, Mount ha trabajado en la implementación de algoritmos eficientes en bibliotecas de software como:

• ANN: búsqueda aproximada del vecino más cercano
• ISODATA: implementación eficiente de un algoritmo de agrupación popular
• KMeans - agrupación de k-medias

Obras más citadas

Al 8 de diciembre de 2009, aquí hay una lista de sus obras más citadas (según Google Scholar ) y sus principales contribuciones, enumeradas en orden decreciente de citas:

1. Un algoritmo óptimo para la búsqueda aproximada del vecino más cercano en dimensiones fijas ^[3] - En este artículo proporcionan un algoritmo (que depende tanto del número de dimensiones como del error aproximado ) para encontrar un vecino que esté como máximo a un factor de distancia del vecino más cercano. vecino. ${\displaystyle O(c_{d,\epsilon }\log(n))}$ ${\displaystyle c_{d,\epsilon }}$ ${\displaystyle d}$ ${\displaystyle \epsilon }$ ${\displaystyle (1+\epsilon )}$
2. Un algoritmo eficiente de agrupación de k-medias: análisis e implementación ^[2] : en este artículo, proporcionan una implementación más simple y eficiente del algoritmo de Lloyd , que se utiliza en la agrupación de k-medias . El algoritmo se llama algoritmo de filtrado.
3. El problema geodésico discreto ^[7] : en este artículo calculan el camino más corto desde un origen a un destino obligado a viajar sobre la superficie de un poliedro determinado (posiblemente no convexo ) . Su algoritmo necesita tiempo para encontrar la primera ruta más corta al primer destino y la ruta más corta a cualquier destino adicional (de la misma fuente) se puede calcular en el tiempo. Aquí está el número de vértices. ${\displaystyle O(n^{2}\log(n))}$ ${\displaystyle O(\log n)}$ ${\displaystyle n}$

Reconocimiento

Mount fue incluido en la clase 2022 de ACM Fellows , "por sus contribuciones a algoritmos y estructuras de datos para el análisis y la recuperación de datos geométricos". ^[8]

Referencias

1. D. Monte. Curriculum Vitae Archivado el 27 de noviembre de 2009 en la Wayback Machine.
2. T. Kanungo, DM Mount, NS Netanyahu , CD Piatko , R. Silverman y A. Wu . Un algoritmo eficiente de agrupación de k-medias: análisis e implementación. Transacciones IEEE sobre análisis de patrones e inteligencia artificial 24(7):881-–892, 2002.
3. S. Arya, DM Mount, NS Netanyahu , R. Silverman y A. Wu , '"n Algoritmo óptimo para la búsqueda aproximada del vecino más cercano en dimensiones fijas", Journal of the ACM , 45(6):891-923, 1998 .
4. DM Mount y S. Arya, ANN: una biblioteca para la búsqueda aproximada del vecino más cercano
5. S. Arya, S., T. Malamatos y DM Mount. Compensaciones espacio-temporales para la búsqueda aproximada del vecino más cercano. Revista de la ACM, 57(1): 1-54, 2009
6. S. Arya, T. Malamatos, DM Mount y KC Wong. Ubicación óptima del punto plano del caso esperado. Revista SIAM de Computación, 37(2):584-610, 2007.
7. JSB Mitchell, DM Mount y CH Papadimitriou. El problema geodésico discreto. Revista SIAM de Computación, 16(4):647-668, 1987
8. "La asociación global de informática nombra a 57 becarios por sus destacadas contribuciones que impulsan la tecnología actual". Asociación para Maquinaria de Computación. 18 de enero de 2023 . Consultado el 18 de enero de 2023 .

enlaces externos

• Página web oficial
• Estructuras de datos y algoritmos en C++
• Google Académico