Parallel Distributed Processing of Constrained Skyline Queries by Filtering
- 1 April 2008
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 546-555
Abstract
Skyline queries are capable of retrieving interesting points from a large data set according to multiple criteria. Most work on skyline queries so far has assumed a centralized storage, whereas in practice relevant data are often distributed among geographically scattered sites. In this work, we tackle constrained skyline queries in large-scale distributed environments without the assumption of any overlay structures, and propose a novel algorithm named PaDSkyline (Parallel distributed Skyline query processing). PaDSkyline significantly shortens the response time by performing parallel processing over site groups produced by a partition algorithm. Within each group, it locally optimizes the query processing over distributed sites. It also drastically enhances the network transmission efficiency by performing early reduction of skyline candidates with deliberately selected multiple filtering points. Results of extensive experiments demonstrate the efficiency and robustness of our proposals.Keywords
This publication has 8 references indexed in Scilit:
- Robust Cardinality and Cost Estimation for Skyline Operator2006
- Skyline with presorting2004
- An optimal and progressive algorithm for skyline queries2003
- The Skyline operator2002
- A scalable content-addressable networkACM SIGCOMM Computer Communication Review, 2001
- Distance browsing in spatial databasesACM Transactions on Database Systems, 1999
- Distributed query processingACM Computing Surveys, 1984
- Query processing in a system for distributed databases (SDD-1)ACM Transactions on Database Systems, 1981