Fast approximate middle of points in a metric space?

Question

Given $N$ points $X_i$ in a metric space and a measure of "middleness" $ \qquad \qquad \mathsf{middle}( X_i ) \equiv \frac{1}{N} \sum_j \mathsf{metric}( X_i, X_j ) $
can one find an $X_i$ near the middle of all $N$ points, i.e. roughly minimizing $\mathsf{middle}( X_i )$,
in time and space both better than $O( N^2 )$ ?
If not in general, are there cases that can be done — trees, Euclidean metrics ?

Clarification: by "space better than $O(N^2)$" I mean, are there approximate methods that give many nearby pairs after looking at $O(N^{1+\epsilon})$ of all pairs ?
This is broader than just middles. Of course, guarantees are then gone, or empirical or statistical. But methods that work for $N$ 10000 or 1000000 would have broad application.
(Is that clear, is it worth a separate question ?)

Answer 1

There's a rather large literature on this problem. In brief, the problem you're looking at is called the $1$-median problem for a metric space. Since you're allowing for things "near" the middle, I'll assume approximations are ok. I also don't know what you mean by space less than $n^2$, since the input size itself is $n^2$.

Having said that, for an arbitrary metric space you can get a "sublinear" approximation (i.e one that runs in $o(n^2)$ time. Specifically, Piotr Indyk showed that you can get a $(1+\epsilon)$ approximation in time linear in $n$ and polynomial in $1/\epsilon$.

For structured spaces you can also do quite well. In Euclidean space, core-set techniques for the $k$-median problem (of which the 1-median is a special case) give you similar bounds (linear in n) to get arbitrarily good approximations. The caveat in this case is that the solution you get might not be one of the input points.

Answer 2

I don't know if you are interested in those kind of results, but Brassard, Dupuis, Gambs and Tapp devised a quantum algorithm that does just that. It finds an element $X_i$ such that $|\mathsf{middle}(X_i)-\mathsf{middle}(X_{min})|< O(\epsilon)$ (when all distances are normalized to be in $[0, 1]$). and requires $O(\frac 1\epsilon \sqrt N\log N)$ calls to the distance function (which you call metric) where $X_{min}$ is the middle you are looking for.

What might surely interest you is that in the first paragraph of the section on the median algorithm, they provide an argument that in the worst case, with a general metric, $\Omega(N^2)$ calls to the distance function is required without a quantum computer. Here is their argument :

[..] consider the case in which all the points are at the same distance from each other, except for two points that are closer than the rest of the points. These two points are the medians of this ensemble. In this case, classically we would need to query the oracle for the distances between each and every pair of points before we can identify one of the two medians. (We expect to discover this special pair after querying about half the pairs on the average but we cannot know that there isn’t some other even closer pair until all the pairs have been queried.) This results in a lower bound of $\Omega(N^2)$ calls to the oracle.

This give a lower bound on the number of calls to the oracle (distance function) which itself lower-bounds the time complexity.

Here is a link to the article.