Our approach to similarity search and data mining on large databases of uncertain feature vectors is to represent each uncertain object by a multivariate probability density function (PDF). In contrast to previous approaches, our idea is not to represent the PDFs discretely (e.g. by some histogram) but in their original, parametric form. Typical and widely used probability distributions such as Gaussian, Laplacian, Generalized Exponential or even Mixture Models can in this way be represented in a lossless way. Organizing objects in the parameter space (e.g. by mean and variance for Gaussian distributions) requires a careful reformulation of methods for data mining and indexing structures but is very space and time efficient. We will present in detail the Gauss-tree, an index structure for Gaussian PDFs but we will also introduce some advanced data analysis methods such as skylines or clustering methods on our notion of uncertain objects.