Angle-based space partitioning for efficient parallel skyline computation

ABSTRACT

Recently, skyline queries have attracted much attention in the database research community. Space partitioning techniques, such as recursive division of the data space, have been used for skyline query processing in centralized, parallel and distributed settings. Unfortunately, such grid-based partitioning is not suitable in the case of a parallel skyline query, where allpartitions are examined at the same time, since many data partitions do not contribute to the overall skyline set, resulting in a lot of redundant processing.

In this paper we propose a novel angle-based space partitioning scheme using the hyperspherical coordinates of the data points. We demonstrate both formally as well as through an exhaustive set of experiments that this new scheme is very suitable for skyline query processing in a parallel share-nothing architecture. The intuition of our partitioning technique is that the skyline points are equally spread to all partitions. We also show that partitioning the data according to the hyperspherical coordinates manages to increase the average pruning power of points within a partition. Our novel partitioning scheme alleviates most of the problems of traditional grid partitioning techniques, thus managing to reduce the response time and share the computational workload more fairly. As demonstrated by our experimental study, our technique outperforms grid partitioning in all cases, thus becoming an efficient and scalable solution for skyline query processing in parallel environments.

REFERENCES

• 1: W.-T. Balke, U. Güntzer, and J. X. Zheng. Efficient distributed skylining for web information systems. In Proc. of Int. Conf. on Extending Database Technology (EDBT), pages 256--273, 2004.
• 2: Stephan Börzsönyi , Donald Kossmann , Konrad Stocker, The Skyline Operator, Proceedings of the 17th International Conference on Data Engineering, p.421-430, April 02-06, 2001
• 3: Surajit Chaudhuri , Nilesh Dalvi , Raghav Kaushik, Robust Cardinality and Cost Estimation for Skyline Operator, Proceedings of the 22nd International Conference on Data Engineering, p.64, April 03-07, 2006 [doi>10.1109/ICDE.2006.131]
• 4: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In Proc. of Int. Conf. on Data Engineering (ICDE), pages 717--719, 2003.
• 5: Adan Cosgaya-Lozano , Andrew Rau-Chaplin , Norbert Zeh, Parallel Computation of Skyline Queries, Proceedings of the 21st International Symposium on High Performance Computing Systems and Applications, p.12, May 13-16, 2007 [doi>10.1109/HPCS.2007.25]
• 6: Y. Gao, G. Chen, L. Chen, and C. Chen. Parallelizing progressive computation for skyline queries in multi-disk environment. In Proc. Int. Conf. of Database and Expert Systems Applications (DEXA), pages 697--706, 2006.
• 7: Katja Hose , Christian Lemke , Kai-Uwe Sattler, Processing relaxed skylines in PDMS using distributed data summaries, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183676]
• 8: Zhiyong Huang , Christian S. Jensen , Hua Lu , Beng Chin Ooi, Skyline Queries Against Mobile Lightweight Devices in MANETs, Proceedings of the 22nd International Conference on Data Engineering, p.66, April 03-07, 2006 [doi>10.1109/ICDE.2006.142]
• 9: H. V. Jagadish , Beng Chin Ooi , Quang Hieu Vu, BATON: a balanced tree structure for peer-to-peer networks, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 10: Donald Kossmann , Frank Ramsak , Steffen Rost, Shooting stars in the sky: an online algorithm for skyline queries, Proceedings of the 28th international conference on Very Large Data Bases, p.275-286, August 20-23, 2002, Hong Kong, China
• 11: Huajing Li , Qingzhao Tan , Wang-Chien Lee, Efficient progressive processing of skyline queries in peer-to-peer systems, Proceedings of the 1st international conference on Scalable information systems, p.26-es, May 30-June 01, 2006, Hong Kong [doi>10.1145/1146847.1146873]
• 12: Eric Lo , Kevin Y. Yip , King-Ip Lin , David W. Cheung, Progressive skylining over web-accessible databases, Data & Knowledge Engineering, v.57 n.2, p.122-147, May 2006 [doi>10.1016/j.datak.2005.04.003]
• 13: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• 14: Dimitris Papadias , Yufei Tao , Greg Fu , Bernhard Seeger, Progressive skyline computation in database systems, ACM Transactions on Database Systems (TODS), v.30 n.1, p.41-82, March 2005 [doi>10.1145/1061318.1061320]
• 15: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 16: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 17: Kian-Lee Tan , Pin-Kwang Eng , Beng Chin Ooi, Efficient Progressive Skyline Computation, Proceedings of the 27th International Conference on Very Large Data Bases, p.301-310, September 11-14, 2001
• 18: A. Vlachou, C. Doulkeridis, Y. Kotidis, and M. Vazirgiannis. SKYPEER: Efficient subspace skyline computation over distributed data. In Proc. of Conf. on Data Engineering (ICDE), pages 416--425, 2007.
• 19: S.Wang, B. C. Ooi, A. K. H. Tung, and L. Xu. Efficient skyline query processing on peer-to-peer networks. In Proc. of Int. Conf. on Data Engineering (ICDE), pages 1126--1135, 2007.
• 20: Roger Weber , Hans-Jörg Schek , Stephen Blott, A Quantitative Analysis and Performance Study for Similarity-Search Methods in High-Dimensional Spaces, Proceedings of the 24rd International Conference on Very Large Data Bases, p.194-205, August 24-27, 1998
• 21: P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi. Parallelizing skyline queries for scalable distribution. In Proc. of Conf. on Extending Database Technology (EDBT), pages 112--130, 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Parallel databases

General Terms:
Algorithms, Experimentation, Performance

Keywords:
parallel computation, skyline operator, space partitioning