An approximate median search algorithm in non-metric spaces

Given a set of data points and a distance function, the median point is def ined as the point tin the set) that minimizes the sum of the distances to t he remaining points of the set. In the general case, the median computation has an O(n(2)) time cost, where n is the number of points. Nevertheless, f or most tasks an approximate median is enough. In this paper a very fast al gorithm (linear in time) is presented that finds a point that is a very goo d approximation of the exact median. This algorithm is independent of the d istance function and does not degrade as the dimensionality of the data inc reases. (C) 2001 Elsevier Science B.V. All rights reserved.