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.