DuoWave: Mitigating the curse of dimensionality for uncertain data

The curse of dimensionality has been a vexatious obstacle in processing queries on multidimensional data. This problem is more serious with uncertain data: an uncertain object's value may spread extensively in the data space with varying probability distribution. In this paper, we attack this challenging problem and propose a technique called DuoWave for indexing uncertain multidimensional objects under a commonly used data model. We propose efficient algorithms to process range queries, the most popular filtering paradigm for many multidimensional queries on uncertain data. Extensive experiments show that DuoWave significantly outperforms state-of-the-art techniques. Moreover, DuoWave can also be exploited for a number of other query types on uncertain data.