Scalable skyline computation using object-based space partitioning

ABSTRACT

The skyline operator returns from a set of multi-dimensional objects a subset of superior objects that are not dominated by others. This operation is considered very important in multi-objective analysis of large datasets. Although a large number of skyline methods have been proposed, the majority of them focuses on minimizing the I/O cost. However, in high dimensional spaces, the problem can easily become CPU-bound due to the large number of computations required for comparing objects with current skyline points while scanning the database. Based on this observation, we propose a dynamic indexing technique for skyline points that can be integrated into state-of-the-art sort-based skyline algorithms to boost their computational performance. The new indexing and dominance checking approach is supported by a theoretical analysis, while our experiments show that it scales well with the input size and dimensionality not only because unnecessary dominance checks are avoided but also because it allows efficient dominance checking with the help of bitwise operations.

REFERENCES

• 1: Ilaria Bartolini , Paolo Ciaccia , Marco Patella, Efficient sort-based skyline evaluation, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-49, November 2008 [doi>10.1145/1412331.1412343]
• 2: Jon L. Bentley , Kenneth L. Clarkson , David B. Levine, Fast linear expected-time alogorithms for computing maxima and convex hulls, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.179-187, January 22-24, 1990, San Francisco, California, United States
• 3: S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In ICDE, 2001.
• 4: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Efficient Processing of Skyline Queries with Partially-Ordered Domains, Proceedings of the 21st International Conference on Data Engineering, p.190-191, April 05-08, 2005 [doi>10.1109/ICDE.2005.60]
• 5: Chee-Yong Chan , Pin-Kwang Eng , Kian-Lee Tan, Stratified computation of skylines with partially-ordered domains, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066181]
• 6: Chee-Yong Chan , H. V. Jagadish , Kian-Lee Tan , Anthony K. H. Tung , Zhenjie Zhang, Finding k-dominant skylines in high dimensional space, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142530]
• 7: C. Y. Chan, H. V. Jagadish, K. L. Tan, A. K. H. Tung, and Z. Zhang. On high dimensional skylines. In EDBT, 2006.
• 8: 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]
• 9: Lei Chen , Xiang Lian, Dynamic skyline queries in metric spaces, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France [doi>10.1145/1353343.1353386]
• 10: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In ICDE, 2003.
• 11: Parke Godfrey , Ryan Shipley , Jarek Gryz, Maximal vector computation in large data sets, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 12: Mohamed E. Khalefa , Mohamed F. Mokbel , Justin J. Levandoski, Skyline Query Processing for Incomplete Data, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.556-565, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497464]
• 13: Werner Kießling, Foundations of preferences in database systems, Proceedings of the 28th international conference on Very Large Data Bases, p.311-322, August 20-23, 2002, Hong Kong, China
• 14: 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
• 15: Ken C. K. Lee , Baihua Zheng , Huajing Li , Wang-Chien Lee, Approaching the skyline in Z order, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 16: Xiang Lian , Lei Chen, Monochromatic and bichromatic reverse skyline search over uncertain databases, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376641]
• 17: X. Lin, Y. Yuan, Q. Zhang, and Y. Zhang. Selecting stars: The k most representative skyline operator. In ICDE, 2007.
• 18: Michael Morse , Jignesh M. Patel , H. V. Jagadish, Efficient skyline computation over low-cardinality domains, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 19: 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]
• 20: Jian Pei , Bin Jiang , Xuemin Lin , Yidong Yuan, Probabilistic skylines on uncertain data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 21: Dimitris Sacharidis , Panagiotis Bouros , Timos Sellis, Caching Dynamic Skyline Queries, Proceedings of the 20th international conference on Scientific and Statistical Database Management, July 09-11, 2008, Hong Kong, China [doi>10.1007/978-3-540-69497-7_29]
• 22: Nikos Sarkas , Gautam Das , Nick Koudas , Anthony K. H. Tung, Categorical skylines for streaming data, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376643]
• 23: 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
• 24: Yufei Tao , Xiaokui Xiao , Jian Pei, SUBSKY: Efficient Computation of Skylines in Subspaces, Proceedings of the 22nd International Conference on Data Engineering, p.65, April 03-07, 2006 [doi>10.1109/ICDE.2006.149]
• 25: Akrivi Vlachou , Christos Doulkeridis , Yannis Kotidis, Angle-based space partitioning for efficient parallel skyline computation, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376642]
• 26: Shiyuan Wang , Quang Hieu Vu , Beng Chin Ooi , Anthony K. Tung , Lizhen Xu, Skyframe: a framework for skyline query processing in peer-to-peer systems, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.345-362, January 2009 [doi>10.1007/s00778-008-0104-3]
• 27: Raymond Chi-Wing Wong , Ada Wai-Chee Fu , Jian Pei , Yip Sing Ho , Tai Wong , Yubao Liu, Efficient skyline querying with variable user preferences on nominal attributes, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453967]
• 28: Raymond Chi-Wing Wong , Jian Pei , Ada Wai-Chee Fu , Ke Wang, Mining favorable facets, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281278]
• 29: P. Wu, C. Zhang, Y. Feng, B. Y. Zhao, D. Agrawal, and A. E. Abbadi. Parallelizing skyline queries for scalable distribution. In EDBT, 2006.
• 30: Man Lung Yiu , Nikos Mamoulis, Efficient processing of top-k dominating queries on multi-dimensional data, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 31: Yidong Yuan , Xuemin Lin , Qing Liu , Wei Wang , Jeffrey Xu Yu , Qing Zhang, Efficient computation of the skyline cube, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
preference, skyline, space partitioning