Adaptive Processing for Distributed Skyline Queries over Uncertain Data
Authors:
- 2 September 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 28 (2) , 371-384
Abstract
Query processing over uncertain data has gained growing attention, because it is necessary to deal with uncertain data in many real-life applications. In this paper, we investigate skyline queries over uncertain data in distributed environments (DSUD query) whose research is only in an early stage. The state-of-the-art algorithm, called e-DSUD algorithm, is designed for processing this query. It has the desirable characteristics of progressiveness and minimum bandwidth consumption. However, it still needs to be perfected in three aspects. (1) Progressiveness. Each time it only returns one query result at most. (2) Efficiency. There are a significant amount of redundant I/O cost and numerous iterations which causes a long total query time. (3) Universality. It is restricted to the case where local skyline tuples are incomparability. To address these concerns, we first present a detailed analysis of the e-DSUD algorithm and then develop an improved framework for the DSUD query, namely IDSUD. Based on the new framework, we propose an adaptive algorithm, called ADSUD, for the DSUD query. In the algorithm, we redefine the approximate global skyline probability and choose local representative tuples due to minimum probabilistic bounding rectangle adaptively. Furthermore, we design a progressive pruning method and apply the reuse mechanism to improve its efficiency. The results of extensive experiments verify the better overall performance of our algorithm than the e-DSUD algorithm.Keywords
Funding Information
- Key Program of National Natural Science Foundation of China (61133005, 61432005)
- National Natural Science Foundation of China (61370095, 61472124, 61202109, 61472126)
- International Science & Technology Cooperation Program of China (2015DFA11240)
This publication has 22 references indexed in Scilit:
- A survey of large-scale analytical query processing in MapReduceThe VLDB Journal, 2013
- Skyline Processing on Distributed Vertical DecompositionsIEEE Transactions on Knowledge and Data Engineering, 2011
- A survey of skyline processing in highly distributed environmentsThe VLDB Journal, 2011
- Efficient and Progressive Algorithms for Distributed Skyline Queries over Uncertain DataIEEE Transactions on Knowledge and Data Engineering, 2011
- Constrained Skyline Query Processing against Distributed Data SitesIEEE Transactions on Knowledge and Data Engineering, 2010
- Efficient monitoring of skyline queries over distributed data streamsKnowledge and Information Systems, 2009
- AGiDS: A Grid-Based Strategy for Distributed Skyline Query Processing2009
- Progressive Skyline Query Processing in Wireless Sensor Networks2009
- Distributed Skyline Retrieval with Low Bandwidth ConsumptionIEEE Transactions on Knowledge and Data Engineering, 2008
- Angle-based space partitioning for efficient parallel skyline computation2008