k-dominant Skyline query algorithm for dynamic datasets

Abstract

At present, most k-dominant Skyline query algorithms are oriented to static datasets, this paper proposes a k-dominant Skyline query algorithm for dynamic datasets. The algorithm is recursive circularly. First, we compute the dominant ability of each object and sort objects in descending order by dominant ability. Then, we maintain an inverted index of the dominant index by k-dominant Skyline point calculation algorithm. When the data changes, it is judged whether the update point will affect the k-dominant Skyline point set. So the k-dominant Skyline point of the newdata set is obtained by inserting and deleting algorithm. The proposed algorithm resolves maintenance issue of a frequently updated database by dynamically updating the data sets. The experimental results show that the query algorithm can effectively improve query efficiency.

Keywords

multi-objective decision / Skyline queries / k-dominant Skyline queries / dynamic datasets

References

[1] Cui W X, Xiao Y Y, Hao G, Deng H F. MapReduce-based skyline query processing algorithm. Computer Science, 2016, 43(6): 35–38

[2] Dong L G, Cui X W, Liu G H. An update algorithm for k-dominating skyline. Science Technology and Engineering, 2014, 14(22): 235–239

[3] Bai M, Xin J C, Wang G R, Wang X T. Research on dynamic skyline query processing over data streams. Chinese Journal of Computers, 2016, 39(10): 2007–2030

[4] Park Y, Min J K, Shim K. Efficient processing of skyline queries using mapreduce. IEEE Transactions on Knowledge and Data Engineering, 2017, 29(5): 1031–1044

[5] Mullesgaard K, Pedersen J L, Lu H, Zhou Y L. Efficient skyline computation in mapreduce. In: Proceedings of the 17th International Conference on Extending Database Technology. 2014, 37–48

[6] Han X X, Li J Z, Gao H. An efficient top-k dominating algorithm on massive data title. Chinese Journal of Computers, 2013, 36(10): 2132–2145

[7] Han X X, Li J Z, Yang D H, Wang J B. Efficient skyline computation on big data. IEEE Transactions on Knowledge and Data Engineering, 2013, 25(11): 2521–2535

[8] Borzsony S, Kossmann D, Stocker K. The skyline operator. In: Proceedings of International Conference on Data Engineering. 2001, 421–430

[9] Chan C Y, Jagadish H V, Tan K L, Tung A K H, Zhang Z. Finding k-dominant skylines in high dimensional space. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2006, 503–514

[10] Yin J, Yao S Y, Xue S E, Yang W X, Liu Y B. An index based efficient k-dominant skyline algorithm. Chinese Journal of Computer, 2010, 33(7): 1236–1245

[11] Siddique MA, Morimoto Y. Efficient maintenance of k-Dominant skyline for frequently updated database. In: Proceedings of the 2nd International Conference on Advances in Databases Knowledge and Data Applications. 2010, 107–110

[12] Huang R Y, Zhao L. K-dominant skyline computation using simplified. Journal of Chinese Computer Systems, 2013, 34(5): 1054–1059

[13] Zhao X, Wu Y H, Cui W W, Du X N, Chen Y, Wang Y, Lee D L, Qu H M. SkyLens: visual analysis of skyline on multi-dimensional data. IEEE Transactions on Visualization and Computer Graphics, 2018, 24(1): 246–255

[14] Zhou X, Li K, Xiao G, Zhou Y, Li K. Top k favorite probabilistic products queries. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(10): 2808–2821

[15] Zhou X, Li K, Yang Z B, Li K Q. Finding optimal skyline product combinations under price promotion. IEEE Transactions on Knowledge and Data Engineering, 2018, 31(1): 138–151

[16] Zhou X, Li K L, Zhou Y T, Li K Q. Adaptive processing for distributed skyline queries over uncertain data. IEEE Transactions on Knowledge and Data Engineering, 2015, 28(2): 371–384

[17] Liu J, Xiong L, Pei J, Luo J, Zhang H Y. Finding pareto optimal groups: group-based skyline. Proceedings of the VLDB Endowment, 2015, 8(13): 2086–2097

[18] Miao X Y, Gao Y J, Zheng B H, Chen G, Cui H Y. Top-k dominating queries on incomplete data. IEEE Transactions on Knowledge and Data Engineering, 2015, 28(1): 252–266

[19] Papadias D, Tao Y, Fu G, Seeger B. An optimal and progressive algorithm for skyline queries. In: Proceedings of ACM SIGMOD International Conference on Management of Data. 2003, 467–478

RIGHTS & PERMISSIONS

Higher Education Press