David Mount
Proximity Searching in Euclidean and Other Metric Spaces

Wednesday, November 4 , 2009
Building 3 Auditorium - 11:00 AM
(Coffee at 10:30 AM)

Nearest neighbor searching is a fundamental problem in computational geometry, databases, information retrieval, and pattern recognition. Given a large set of points in space, the problem involves preprocessing these points into a data structure so that, given a query point, it is possible to rapidly report the closest point of the set to. For the sake of efficiency, we consider approximate solutions, where the user can specify the required degree of accuracy of the final result.

This problem has been extensively studied in the context of Euclidean distances, but Euclidean distance is not the most meaningful measure for many applications. For example, distances between strings are often measured using edit distance, and distances between geometric shapes are measured using the earth mover's distance. There has been growing interest in studying proximity searching in the context of general metric spaces. The distance function is provided by a black-box function, which returns the distance between any given pair of points. This function is assumed to satisfy basic geometric properties, such as the triangle inequality.

In this talk, we will begin with a brief overview of many of the important concepts that have been developed recently in the context of proximity searching in metric spaces including doubling spaces. We will discuss theoretical limitations of the general black-box model for approximate nearest neighbor searching, and we will introduce a more powerful model that allows for more efficient algorithms for nearest neighbor searching in metric spaces of low doubling dimension.

David Mount is a professor in the Department of Computer Science at the University of Maryland with a joint appointment in the University's Institute for Advanced Computer Studies (UMIACS). He received his Ph.D. from Purdue University in Computer Science in 1983, and started at the University of Maryland in 1984. He has written over 130 research publications on algorithms for geometric problems, particularly problems with applications in image processing, pattern recognition, information retrieval, and computer graphics.

He currently serves as an associate editor for the journals ACM Trans. on Mathematical Software and the International Journal of Computational Geometry and Applications. He served on the editorial board of Pattern Recognition from 1999 to 2006. He has served as the Conference and Programs Chairs of a number of conferences, including the 2003 and 2008 Symposia on Computational Geometry and the 2009 Symposium on Theory of Computing.

He has won a number of awards for excellence in teaching, including University of Maryland's College of Computer, Mathematical and Physical Sciences, Dean's Award for Excellence in Teaching in 1997, and the Award for Teaching Excellence Appreciation in 2001 at the Hong Kong University of Science and Technology.

IS&T Colloquium Committee Host: Nargess Memarsadeghi