Presorting Grouping Algorithm for Skyline Computation

doi:10.3969/j.issn.1006-2475.2014.02.016

Abstract

Abstract: In this paper, we proposed the presorting grouping algorithm for skyline computation. This algorithm was based on SFS algorithm, and efficiently supported the preference of users. We proved that, for computing skyline, the number required comparisons between two points does not exceed m(n-m/2-1/2), where n being the number of points, and m being the number of skyline points; if the number of groups being k, then the number required comparisons used in the presorting grouping algorithm reduced m(m-k)/2k.

Key words: multi-objective optimization, presorting, skyline, grouping algorithm

CLC Number:

TP311

LIU Ping.

Presorting Grouping Algorithm for Skyline Computation

[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2014.02.016.

References 15

[1]	Borzsony S, Kossmann D, Stocker K. The skyline operator[C]// Proceedings of the 17th IEEE International Conference on Data Engineering. 2001:421-430.
[2]	Chomicki J, Godfrey P, Gryz J, et al. Skyline with Presorting[R]. York University, 2002.
[3]	Chomicki J, Godfrey P, Gryz J, et al. Skyline with presorting[C]// Proceedings of the 19th IEEE International Conference on Data Engineering. 2003:717-719.
[4]	Kung H T, Luccio F, Preparata F P. On finding the maxima of a set of vectors[J]. Journal of the Association for Computing Machinery, 1975,22(4):469-476.
[5]	Bentley J L, Kung H T, Schkolnick M, et al. On the average number of maxima in a set of vectors and applications[J]. Journal of the Association for Computing Machinery, 1978,25(4):536-543.
[6]	Tan K L, Eng P K, Ooi B C. Efficient progressive skyline computation[C]// Proceedings of the 27th IEEE International Conference on Very Large Data Bases. Rome, Italy, 2001:301-310.
[7]	Papadias D, Tao Y, Fu G, et al. Progressive skyline computation in database systems[J]. ACM Transactions on Database Systems, 2005,30(1):41-82.
[8]	Balke W-T, Guntzer U, Zheng J X. Efficient distributed skylining for Web information systems[C]// Proceedings of the 9th IEEE International Conference on Extending Database Technology. Crete, Greece, 2004:256-273.
[9]	Hose K. Processing skyline queries in P2P systems[C]// Proceedings of VLDB 2005 PhD Workshop. Trondheim, Norway, 2005:36-40.
[10]	Pei J, Jiang B, Lin X, et al. Probabilistic skylines on uncertain data[C]// Proceedings of the 33rd IEEE International Conference on Very Large Data Bases. Vienna, Austria, 2007:15-26.
[11]	Vlachou A, Doulkeridis C, Kotidis Y, et al. SKYPEER: Efficient subspace skyline computation over distributed data[C]// Proceedings of the 23rd IEEE International Conference on Data Engineering. 2007:416-425.
[12]	Tao Y, Xiao X, Pei J. SUBSKY: Efficient computation of skylines in subspaces[C]// Proceedings of the 22nd IEEE International Conference on Data Engineering. 2006.
[13]	Pei J, Yuan Y, Lin X, et al. Towards multidimensional subspace skyline analysis[J]. ACM Transactions on Database Systems, 2006,31(4):1335-1381.
[14]	Tao Y, Papadias D. Maintaining sliding window skylines on data streams[J]. IEEE Transactions on Knowledge and Data Engineering, 2006,18(3):377-391.
[15]	Lin X, Yuan Y, Wang W, et al. Stabbing the skyline: Efficient skyline computation over sliding windows[C]// Proceedings of the 21st IEEE International Conference on Data Engineering. 2005:502-513.