You mention a dataset with two numerical features, hence you have points M(x, y) in a plane.

There is a lot of pre-existing knowledge on data sets in a plane: this is called an image!

First you may not need to compute distances, all of them. Use some topology in the plane, with a "tiling".

In other terms you can define quantizers where all points M in set Qi are represented by a selected typical member qi of Qi, assuming that Q0... Qn are non intersecting sets covering the plan P.

The distance between point M in Qi and point M' in Qj can be approximated by dist(qi, qj).

This is just an illustration of many possibilities existing.

Look up keywords quantization, Voronoi diagram, covering map (topology), compact set, etc