For many database operations, such as nearest neighbor search, distance-based clustering and
outlier detection, there is an underlying k data space in which each tuple/object is
represented as a point in the space. We observe that in the presence of variability,
correlation, outliers and/or differing scales, we may get unintuitive results if an
inappropriate space is used. The fundamental question addressed in this paper is: "What
then is an appropriate space?". We propose using a robust space transformation called the
Donoho-Stahel estimator. In the first half of the paper, we show the key properties of the
estimator. Of particular importance to database applications is the stability property,
which says that in spite of frequent updates, the estimator does not (a) change much,
(b) lose its usefulness, or (c) require re-computation. In the second half, we focus on the
computation of the estimator for high-dimensional databases. We develop randomized algorithms
and evaluate how well they perform empirically. The bottom-line is that the Donoho-Stahel
transformation, which possesses desirable properties for database operations, can be
computed efficiently as well.