iSky: Efficient and Progressive Skyline Computing in a Structured P2P Network

An interesting problem in peer-based data management is efficient support for skyline queries within a multi-attribute space. A skyline query retrieves from a set of multidimensional data points a subset of interesting points, compared to which no other points are better Skyline queries play an important role in multi-criteria decision making and user preference applications. In this paper we address the skyline computing problem in a structured P2P network. We exploit the iMinMax(theta) transformation to map high-dimensional data points to 1-dimensional values. All transformed data points are then distributed on a structured P2P network called BATON, where all peers are virtually organized as a balanced binary search tree. Subsequently, a progressive algorithm is proposed to compute skyline in the distributed P2P network. Further, we propose an adaptive skyline filtering technique to reduce both processing cost and communication cost during distributed skyline computing. Our performance study, with both synthetic and real datasets, shows that the proposed approach can dramatically reduce transferred data volume and gain quick response time.