Optimizing Quality for Probabilistic Skyline Computation and Probabilistic Similarity Search
- 13 February 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 30 (9) , 1741-1755
Abstract
Probabilistic queries have been extensively explored to provide answers with confidence, in order to support the real-life applications struggling with uncertain data, such as sensor networks and data integration. However, the uncertainty of data may propagate, and thus, the results returned by probabilistic queries contain much noise, which degrades query quality significantly. In this paper, we propose an efficient optimization framework, termed as QueryClean, for both probabilistic skyline computation and probabilistic similarity search. The goal of QueryClean is to optimize query quality via selecting a group of uncertain objects to clean under limited resource available, where a joint-entropy based quality function is leveraged. We develop an efficient structure called ASI to index the possible result sets of probabilistic queries, which helps to avoid many times of probabilistic query evaluations over a large number of the possible worlds for quality computation. Moreover, we present exact and approximate algorithms for the optimization problem, using two newly presented heuristics. Considerable experimental results on both real and synthetic data sets demonstrate the efficiency and scalability of our proposed framework QueryClean.Keywords
Funding Information
- the 973 Program of China (2015CB352502)
- NSFC (61522208, 61379033)
- NSFC-Zhejiang Joint (U1609217)
- ARC DP (170103710)
- D2D CRC (DC25002, DC25003)
This publication has 32 references indexed in Scilit:
- KATARA2015
- Query-Oriented Data Cleaning with Oracles2015
- Skyline Queries with Noisy Comparisons2015
- Graph similarity search on large uncertain graph databasesThe VLDB Journal, 2014
- Query-driven approach to entity resolutionProceedings of the VLDB Endowment, 2013
- UV-diagram: a voronoi diagram for uncertain spatial databasesThe VLDB Journal, 2012
- Explore or exploit?Proceedings of the VLDB Endowment, 2010
- Scalable processing of snapshot and continuous nearest-neighbor queries over one-dimensional uncertain dataThe VLDB Journal, 2009
- Cleaning uncertain data with quality guaranteesProceedings of the VLDB Endowment, 2008
- Probabilistic top- k and ranking-aggregate queriesACM Transactions on Database Systems, 2008