An Algorithm to Update K-Dominant Skyline

Abstract:

K-dominant skyline query technology reduces the result sets for a dataset with high dimensional spaces, which is more convenient for user to make decision. But all the existent algorithms are for static k, not suitable for dynamic k. To solve this problem, this paper proposed a new idea, updating the k-dominant skyline for new k by computing the partial points based on existent k-dominant skyline. Based on which, two algorithms are proposed for k increasing and decreasing. Furthermore, detailed theoretical analyses and extensive experiments demonstrate that the algorithms can effectively reduce redundant work, and keep the result correctly.

• Periodical: Applied Mechanics and Materials (Volumes 462-463)
• Pages: 944-948
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.462-463.944
• Online since: November 2013
• Authors: Lei Gang Dong*, Xiao Wei Cui
• Keywords: Dynamic, High Dimensional Space, K-Dominant Skylines Query, Updating

References

[1] Chomicki, J., Godfrey, P., Gryz, J., Liang, D. Skyline with Pre-sorting. ICDE, 2003, 717-719.

[2] Tan, K., Eng, P. Ooi, B. Efficient Progressive Skyline Computation. VLDB, 2001, 301-310.

[3] Kossmann, D., Ramsak, F., Rost, S. Shooting Stars in the Sky: an Online Algorithm for Skyline Queries. VLDB, 2002, 275-286.

DOI: 10.1016/b978-155860869-6/50032-9

[4] C. -Y. Chan, H.V. Jagadish, K. -L. Tan, A.K.H. Tung, Z. Zhang. Finding k-Dominant Skylines in High Dimensional Space. In SIGOMOD 2006, Chicago, USA, (2006).

DOI: 10.1145/1142473.1142530

[5] Borzonyi S, Kossmann D, Stocker K. The Skyline Operator[C]. In ICDE, 2001. Heidelberg, Germany, 2001: 421-430.

[6] J. Pei, W. Jin, M. Ester et al. Catching the best views of skyline: a semantic , approach based on decisive subspaces. VLDB, 2005, 2253-264.

[7] Y. Tao, X. Xiao, J. Pei. Subsky: efficient computation of skylines in subspaces. ICDE, (2006).

DOI: 10.1109/icde.2006.149

[8] T. Xia, D. Zhang. Refreshing the sky: the compressed skycube with efficient support for frequent updates. SIGMOD, 2006, 491-502.

DOI: 10.1145/1142473.1142529

[9] D. Papadias, Y. Tao, G. Fu et al. Progressive skyline computation in database systems. ACM Transactions on Database systems 30(2005), 41-82.

DOI: 10.1145/1061318.1061320

[10] M. Sharifzadeh, C. Shahabi. The spatial skyline queries. VLDB, 2006, 751-762.

[11] X. Lian, L. Cheromatic n. Monochromatic and bichromatic reverse skyline search over uncertain databases. ACM, 2008, 213-226.

DOI: 10.1145/1376616.1376641

[12] J. Pei, B. Jiang, X. Lin et al. Probabilistic skylines on uncertain data. VLDB, 2007, 15-26.

[13] C.Y. Chan, H.V. Jagadish, K.L. Tan et al. Finding k-dominant skylines in high dimensional space. ACM SIGMOD, 2006, 503-514.

DOI: 10.1145/1142473.1142530

[14] M. A. Siddique, M. Yasuhiko. K-Dominant and Extended k-dominant Skyline Computation by using Statistics. International Journal on Computer Science and Engineering. 2010, 1934-(1943).

[15] I. -F. Su, Y.C. Chung, C. Lee. Top-k combinatorial skyline queries. DASFAA, 2010. 79-92.

[16] R.C. -W. Wong, J. Pei, A.W. -C. Fu. Efficient skyline querying with variable user preferences on nominal attributes. Proceedings of the 34th International Conference on Very Large Data Bases, 2008, 1032-1043.

DOI: 10.14778/1453856.1453967