Research Activities > Programs >
Fast Approximate Algorithms > David Mount
|
|
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.
[LECTURE SLIDES]
|
|
|
