Ranking continuous probabilistic datasets
Authors:
Open Access
- 1 September 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 3 (1-2) , 638-649
Abstract
Ranking is a fundamental operation in data analysis and decision support, and plays an even more crucial role if the dataset being explored exhibits uncertainty. This has led to much work in understanding how to rank uncertain datasets in recent years. In this paper, we address the problem of ranking when the tuple scores are uncertain, and the uncertainty is captured using continuous probability distributions (e.g. Gaussian distributions). We present a comprehensive solution to compute the values of a parameterized ranking function (PRF) [18] for arbitrary continuous probability distributions (and thus rank the uncertain dataset); PRF can be used to simulate or approximate many other ranking functions proposed in prior work. We develop exact polynomial time algorithms for some continuous probability distribution classes, and efficient approximation schemes with provable guarantees for arbitrary probability distributions. Our algorithms can also be used for exact or approximate evaluation of k-nearest neighbor queries over uncertain objects, whose positions are modeled using continuous probability distributions. Our experimental evaluation over several datasets illustrates the effectiveness of our approach at efficiently ranking uncertain datasets with continuous attribute uncertainty.Keywords
This publication has 21 references indexed in Scilit:
- Rhodium-Catalyzed Stereospecific Construction of Allylic AminesSynfacts, 2009
- A unified approach to ranking in probabilistic databasesProceedings of the VLDB Endowment, 2009
- A survey of top- k query processing techniques in relational database systemsACM Computing Surveys, 2008
- Efficient search for the top-k probable nearest neighbors in uncertain databasesProceedings of the VLDB Endowment, 2008
- Ranking queries on uncertain data2008
- On the semantics and evaluation of top-k queries in probabilistic databases2008
- Probabilistic Verifiers: Evaluating Constrained Nearest-Neighbor Queries over Uncertain Data2008
- Model-Driven Data Acquisition in Sensor Networks2004
- Cumulated gain-based evaluation of IR techniquesACM Transactions on Information Systems, 2002
- On Estimation of a Probability Density Function and ModeThe Annals of Mathematical Statistics, 1962