research-article

Ranking queries on uncertain data: a probabilistic threshold approach

Authors:

Xuemin LinAuthors Info & Claims

SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

Pages 673 - 686

https://doi.org/10.1145/1376616.1376685

Published: 09 June 2008 Publication History

Abstract

Uncertain data is inherent in a few important applications such as environmental surveillance and mobile object tracking. Top-k queries (also known as ranking queries) are often natural and useful in analyzing uncertain data in those applications. In this paper, we study the problem of answering probabilistic threshold top-k queries on uncertain data, which computes uncertain records taking a probability of at least p to be in the top-k list where p is a user specified probability threshold. We present an efficient exact algorithm, a fast sampling algorithm, and a Poisson approximation based algorithm. An empirical study using real and synthetic data sets verifies the effectiveness of probabilistic threshold top-k queries and the efficiency of our methods.

References

[1]

S. Abiteboul et al. On the representation and querying of sets of possible worlds. In SIGMOD'87.

Digital Library

[2]

D. Angluin and L. G. Valiant. Fast probabilistic algorithms for hamiltonian circuits and matchings. In STOC'77.

Digital Library

[3]

L. Antova et al. 10^10⁶ worlds and beyond: Efficient representation and processing of incomplete information. In ICDE'07.

[4]

O. Benjelloun et al. Uldbs: databases with uncertainty and lineage. In VLDB'06.

Digital Library

[5]

L. Le Cam. An approximation theorem for poisson binomial distribution. Pacific J. Math., 10:1181--1197, 1960.

[6]

R. Cheng et al. Evaluating probabilistic queries over imprecise data. In SIGMOD'03.

Digital Library

[7]

R. Cheng et al. Efficient indexing methods for probabilistic threshold queries over uncertain data. In VLDB'04.

Digital Library

[8]

N. Dalvi and D. Suciu. Management of probabilistic data: foundations and challenges. In PODS'07.

Digital Library

[9]

N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. In VLDB'04.

Digital Library

[10]

N. Dalvi and D. Suciu. The dichotomy of conjunctive queries on probabilistic structures. In PODS'07.

Digital Library

[11]

D. Dey and S. Sarkar. A probabilistic relational model and algebra. ACM Trans. Database Syst., 21(3):339--369, 1996.

Digital Library

[12]

R. Fagin et al. Optimal aggregation algorithms for middleware. In PODS'01.

Digital Library

[13]

J. L. Hodges and Jr. L. Le Cam. The poisson approximation to the poisson binomial distribution. The Annals of Mathematical Statistics, 31(3):737--740, 1960.

[14]

W. Hoeffding. On the distribution of the number of successes in independent trials. Annals of Mathematical Statistics, 27:713--721, 1956.

[15]

M. Hua et al. Efficiently Answering Probabilistic Threshold Top-k Queries on Uncertain Data. In ICDE'08.

Digital Library

[16]

T. Imielinski and Jr. Witold Lipski. Incomplete information in relational databases. Journal of ACM, 31(4):761--791, 1984.

Digital Library

[17]

K. Lange. Numerical analysis for statisticians. Statistics and computing. 1999.

[18]

S. K. Lee. Imprecise and uncertain information in databases: An evidential approach. In ICDE'92.

Digital Library

[19]

X. Lian and L. Chen. Probabilistic Ranked Queries in Uncertain Databases. In EDBT'08.

Digital Library

[20]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, United Kingdom, 1995.

Digital Library

[21]

J. Pei et al. Probabilistic skylines on uncertain data. In VLDB'07, Viena, Austria, September 2007.

Digital Library

[22]

C. Ré et al. Efficient top-k query evaluation on probabilistic data. In ICDE'07.

[23]

A. D. Sarma et al. Working models for uncertain data. In ICDE'06.

Digital Library

[24]

A. Silberstein et al. A Sampling-Based Approach to Optimizing Top-k Queries in Sensor Networks. In ICDE'06.

Digital Library

[25]

S. Singh et al. Indexing uncertain categorical data. In ICDE'07.

[26]

M. A. Soliman et al. Top-k query processing in uncertain databases. In ICDE'07.

[27]

Y. Tao et al. Indexing multi-dimensional uncertain data with arbitrary probability density functions. In VLDB'05.

Digital Library

[28]

Y. H. Wang. On the number of successes in independent trials. Statistica Sinica, 3:295--312, 1993.

[29]

K. Yi et al. Efficient processing of top-k queries in uncertain databases. In ICDE'08.

Digital Library

[30]

X. Zhang and J. Chomicki. On the Semantics and Evaluation of Top-k Queries in Probabilistic Databases. In DBRank'08 Workshop.

Cited By

Feng SGlavic BKennedy O(2023)Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain DataProceedings of the VLDB Endowment10.14778/3583140.358315116:6(1346-1358)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583151
Rai NLian X(2023)Distributed probabilistic top-k dominating queries over uncertain databasesKnowledge and Information Systems10.1007/s10115-023-01917-365:11(4939-4965)Online publication date: 1-Jul-2023
https://doi.org/10.1007/s10115-023-01917-3
Le TCao J(2023)Probabilistic Reverse Top-k Query on Probabilistic DataDatabases Theory and Applications10.1007/978-3-031-47843-7_3(30-43)Online publication date: 7-Nov-2023
https://doi.org/10.1007/978-3-031-47843-7_3
Show More Cited By

Index Terms

Ranking queries on uncertain data: a probabilistic threshold approach
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Ranking queries on uncertain data

Uncertain data is inherent in a few important applications. It is far from trivial to extend ranking queries (also known as top-k queries), a popular type of queries on certain data, to uncertain data. In this paper, we cast ranking queries on uncertain ...
Top-k best probability queries and semantics ranking properties on probabilistic databases

There has been much interest in answering top-k queries on probabilistic data in various applications such as market analysis, personalized services, and decision making. In probabilistic relational databases, the most common problem in answering top-k ...
Probabilistic Reverse Nearest Neighbor Queries on Uncertain Data

Uncertain data are inherent in various important applications and reverse nearest neighbor (RNN) query is an important query type for many applications. While many different types of queries have been studied on uncertain data, there is no previous work ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '08: Proceedings of the 2008 ACM SIGMOD international conference on Management of data

June 2008

1396 pages

ISBN:9781605581026

DOI:10.1145/1376616

General Chairs:
Laks V. S. Lakshmanan
University of British Columbia, Canada
,
Raymond T. Ng
University of British Columbia, Canada
,
Dennis Shasha
New York University, USA

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '08

Sponsor:

SIGMOD/PODS '08: SIGMOD/PODS '08 - International Conference on Management of Data

June 9 - 12, 2008

Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

200
Total Citations
View Citations
1,335
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)2

Reflects downloads up to 14 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Feng SGlavic BKennedy O(2023)Efficient Approximation of Certain and Possible Answers for Ranking and Window Queries over Uncertain DataProceedings of the VLDB Endowment10.14778/3583140.358315116:6(1346-1358)Online publication date: 20-Apr-2023
https://dl.acm.org/doi/10.14778/3583140.3583151
Rai NLian X(2023)Distributed probabilistic top-k dominating queries over uncertain databasesKnowledge and Information Systems10.1007/s10115-023-01917-365:11(4939-4965)Online publication date: 1-Jul-2023
https://doi.org/10.1007/s10115-023-01917-3
Le TCao J(2023)Probabilistic Reverse Top-k Query on Probabilistic DataDatabases Theory and Applications10.1007/978-3-031-47843-7_3(30-43)Online publication date: 7-Nov-2023
https://doi.org/10.1007/978-3-031-47843-7_3
Li HLu HJensen CTang BCheema M(2022)Spatial Data Quality in the Internet of Things: Management, Exploitation, and ProspectsACM Computing Surveys10.1145/349833855:3(1-41)Online publication date: 3-Feb-2022
https://dl.acm.org/doi/10.1145/3498338
Kuo AChen HTang LKu WQin X(2022)ProbSky: Efficient Computation of Probabilistic Skyline Queries over Distributed DataIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2022.3151740(1-1)Online publication date: 2022
https://doi.org/10.1109/TKDE.2022.3151740
Guo HLi JGao HZhang K(2022)PSATop-kKnowledge-Based Systems10.1016/j.knosys.2021.107614235:COnline publication date: 10-Jan-2022
https://dl.acm.org/doi/10.1016/j.knosys.2021.107614
Wang LFang YZhou LWang LFang YZhou L(2022)Top-k Probabilistically Prevalent Co-location PatternsPreference-based Spatial Co-location Pattern Mining10.1007/978-981-16-7566-9_5(107-136)Online publication date: 4-Jan-2022
https://doi.org/10.1007/978-981-16-7566-9_5
Le TBe MNgoc D(2022)A Processing of Top-k Aggregate Queries on Distributed DataIOT with Smart Systems10.1007/978-981-16-3945-6_80(815-826)Online publication date: 5-Jan-2022
https://doi.org/10.1007/978-981-16-3945-6_80
Alsaudi AAltowim YMehrotra SYu Y(2021)TQELProceedings of the VLDB Endowment10.14778/3476249.347630914:11(2642-2654)Online publication date: 27-Oct-2021
https://dl.acm.org/doi/10.14778/3476249.3476309
Lai ZHan CLiu CZhang PLo EKao BLi GLi ZIdreos SSrivastava D(2021)Top-K Deep Video AnalyticsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3452786(1037-1050)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3452786
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents