Given a set of points, S, in a metric space and query point q, the goal is to find the point in S closest to q. Ideally, the data structure to do this only relies on an oracle that gives the distance between any two points, and not on any other detail of the metric space.
In some metric spaces, this seems difficult. Consider, for example, a metric space and a query point such that all points in S are at a distance one from each other, and all but one are at distance q from S. Finding the one point closest to q will probably require querying the distance from q to every point in S. In other metric spaces, it is possible to do this with a logarithmic number of queries (see  or ).
Following up on  and , we have a result showing that this can be done in constant space and logarithmic time for unchanging sets S and hope to argue that a similar data structure with expected constant space works for dynamic sets S.
A more general goal is to characterize the metric spaces for which finding the nearest point requires a sublinear number of queries and develop algorithms for those metric spaces.