  In algorithms for finite metric spaces, it is common to assume that the
distance between two points can be computed in constant time, and complexity
bounds are expressed only in terms of the number of points of the metric space.
We introduce a different model where we assume that the computation of a single
distance is an expensive operation and consequently, the goal is to minimize
the number of such distance queries. This model is motivated by metric spaces
that appear in the context of topological data analysis.
  We consider two standard operations on metric spaces, namely the construction
of a $1+\varepsilon$-spanner and the computation of an approximate nearest
neighbor for a given query point. In both cases, we partially explore the
metric space through distance queries and infer lower and upper bounds for yet
unexplored distances through triangle inequality. For spanners, we evaluate
several exploration strategies through extensive experimental evaluation. For
approximate nearest neighbors, we prove that our strategy returns an
approximate nearest neighbor after a logarithmic number of distance queries.
