[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Fast Approximate Algorithms > David Mount

Fast Multipole Method, Tree-Code and Related Approximate Algorithms.
Trading Exactness for Efficiency.

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Data Structures for Approximate Proximity and Range Searching

Dr. David Mount

Computer Science at University of Maryland

Abstract:   A fundamental problem in the fast multipole method (FMM) is the analysis of the approximate structure of space about some point. The design of efficient data structures for storing multidimensional spatial point sets and efficiently computing aggregate properties of these sets is fundamental not only to FMMs but to many problems in geometric retrieval. In this talk we consider two of the most fundamental retrieval problems on point sets: geometric range queries and k-nearest neighbor queries. We present a data generalization of a structure called an AVD, or approximate Voronoi diagram, which can answer these queries approximately. This structure is based on a simple hierarchical subdivision of space, which can answer queries by a simple descent in a tree combined with a small number of distance computations. In this talk we will discuss a number of aspects of AVDs, including their origins, analysis of the construction time and space complexity, and their use in answering approximate range and k-nearest neighbor searching, and some recent work on their implementation. This is joint work with Sunil Arya of the Hong University of Science and Technology and Charis Malamatos of the Max Plank Institute, Saarbruecken, Germany.