1st International ICST Conference on Scalable Information Systems

Research Article

Efficient progressive processing of skyline queries in peer-to-peer systems

  • @INPROCEEDINGS{10.1145/1146847.1146873,
        author={Huajing   Li and Qingzhao  Tan  and Wang-Chien  Lee},
        title={Efficient progressive processing of skyline queries in peer-to-peer systems},
        proceedings={1st International ICST Conference on Scalable Information Systems},
        publisher={ACM},
        proceedings_a={INFOSCALE},
        year={2006},
        month={6},
        keywords={},
        doi={10.1145/1146847.1146873}
    }
    
  • Huajing Li
    Qingzhao Tan
    Wang-Chien Lee
    Year: 2006
    Efficient progressive processing of skyline queries in peer-to-peer systems
    INFOSCALE
    ACM
    DOI: 10.1145/1146847.1146873
Huajing Li1,2,*, Qingzhao Tan 1,2,*, Wang-Chien Lee1,2,*
  • 1: Department of Computer Science and Engineering, Pennsylvania State University
  • 2: University Park, PA 16802, USA
*Contact email: huali@cse.psu.edu, qtan@cse.psu.edu, wlee@cse.psu.edu

Abstract

Skyline queries have received a lot of attention from database and information retrieval research communities. A skyline query returns a set of data objects that is not dominated by any other data objects in a given dataset. However, most of existing studies focus on skyline query processing in centralized systems. Only recently, skyline queries are considered in a distributed computing environment. Acknowledging the trend toward peer-to-peer (P2P) systems in distributed computing, we examine the problem of skyline query processing in P2P systems and propose innovative solutions. We exploit the data semantic embedded in semantically structured P2P overlay networks to efficiently prune search space, without compromising the quality of query result. In addition, we propose approximate algorithms to support skyline queries where exact answers are too costly to obtain. These approximate algorithms produce high quality answers using heuristics based on local semantics of peer nodes. Extensive experiments validate that our algorithms provides high efficiency and scalability to skyline query processing in P2P systems.