LiU Electronic Press

Mapping the set into the secondary space of lower dimension will not result in loss of information with regard to the semantics defined by the measure. However, it helps to reduce storage and computing efforts. Additionally, the secondary space itself reveals much about the set's structure and can facilitate data mining.

The main problem with the secondary space is that it is unknown, and if it is not a linear sub-space of  Re^d , then there  Re^d  then there is no algorithm to determine it. We make a proposal for adding the property of a dimension to a metric and show that this is compatible to our customized understanding of a a dimension. We present an algorithm which computes, in optimal time, an index on the data set. The index can be regarded as a materialized view for representing the structure of the elements with respect to the given metric. The algorithm works independently of the dimension of the primary space, i.e. pumping up the dimension of the primary space wil not affect the result and the computational effort. Thus, besides supporting navigation and answering neighborhood queries, the algorihm also determines the real dimension of the underlying data set, even if the set is not linearly structured. We prove that the algorithm is robust with respect to skewed data or a distortion of the distance measure.