New Directions in Approximate Nearest-Neighbor Searching

摘要

Approximate nearest-neighbor searching is an important retrieval problem with numerous applications in science and engineering. This problem has been the subject of many research papers spanning decades of work. Recently, a number of dramatic improvements and extensions have been discovered. In this paper, we will survey some of recent techniques that underlie these developments. In particular, we discuss local convexification, Macbeath regions, Delone sets, and how to apply these concepts to develop new data structures for approximate polytope membership queries and approximate vertical ray-shooting queries.