At present, an adequate therapy planning of newly detected brain tumors needs invasive biopsy due to the fact that prognosis and treatment, both vary strongly for different tumor grades. To assist neuroradiologist experts during the differentiation between tumors of different malignancy a novel, efficient similarity search technique for uncertain data in combination with a technique for parameter-free outlier detection is proposed. Previous work is limited to axis-parallel Gaussian distributions, hence, correlations between different features are not considered in these similarity searches. In this work a similarity search technique for general Gaussian Mixture Models (GMMs) without independence assumption is presented. The actual components of a GMM are approximated in a conservative but tight way. The conservativity of the approach leads to a filter-refinement architecture, which guarantees no false dismissals and the tightness of the approximations causes good filter selectivity. Promising results for advancing the differentiation between brain tumors of different grades could be obtained by applying the approach to four-dimensional Magnetic Resonance Images of glioma patients.