A Unified Approach to Approximate Proximity Searching

by 

Guilherme Fonseca

Time: 11am on Friday, August 20, 2010
Venue: 3530

Abstract:

The inability to answer proximity queries efficiently for spaces of
dimension $d>2$ has led to the study of approximation to proximity
problems. Several techniques have been proposed to address different
approximate proximity problems. In this paper, we present a new and
unified approach to proximity searching, which provides efficient
solutions for several problems: spherical range queries, idempotent
spherical range queries, spherical emptiness queries, and nearest
neighbor queries. In contrast to previous data structures, our
approach is simple and easy to analyze, providing a clear picture of
how to exploit the particular characteristics of each of these
problems. As applications of our approach, we provide simple and
practical data structures that match the best previous results up to
logarithmic factors, as well as advanced data structures that improve
over the best previous results for all aforementioned proximity
problems.