Some robust perhaps more complex as neural networks to measure the distance between data? Now after certain preprocess we can repeatedly get two sets of data points, exhaustively enumerate one from the first set and one from the second set to form pairs. Each pair of these two data points have the same dimensionality, say two dimensional or one dimensional. The target is to measure the top n nearest ones among the distances of these pairs each time and perhaps finally the average of them. Euclidean distance is the simplest way to measure, but is there any more robust perhaps more complex way even applying neural networks to measure the distance between the pair? For instance, add a linear neural network layer after each data point, and measure the distance between the two outputs of the layer.
It all depends how you frame your problem.

Whats complex? more parameters, more time complexity, more exotic looking etc...

Here are 2 cool ideas how to measure similarity:

Mahalanobis distance measure of the distance between a point P and a distribution D. Cool but more importantly its robust because you are using parameters of your distribution to measure the distance.

Neural networks. If we relax the definition of "measuring distance between data" then Check siamesse networks. The gist of it is, can you group similiar sequences of data together. Why I like it? cause of one-shot learning