Finding k-Dominant Skyline for Combined Dataset

Abstract:

The k-dominant skyline query which can return small result set in high dimensional space is very convenient for user to make decision. But all the existent algorithms are for single dataset, not suitable for two or more datasets being combined. To solve this problem, this paper proposed a new idea to get the new k-dominant skyline by computing the partial points of each dataset based on their existent k-dominant skylines. 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 568-570)
• Pages: 1534-1538
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.568-570.1534
• Online since: June 2014
• Authors: Lei Gang Dong*, Xiao Wei Cui
• Keywords: Dataset Combine, High Dimensional Space, K-Dominant Skylines

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] M. k, ontaki, A.N. Papadopoulos, Y. Manolopoulos. Continuous k-dominant skyline computation on multidimensional data streams. SAC, 2008, 245-250.

DOI: 10.1145/1363686.1363908

[16] D. Gautam, G. Dimitrios, K. Nick et al. Answering top-k queries using views. VLDB, 2006, 451-462.

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

[18] Md. Anisuzzaman Siddique, Yasuhiko Morimoto。Efficient k-dominant Skyline Computation for High Dimensional Space with Domination Power Index。Journal of Computers, 2012, 7(11): 608-615.

DOI: 10.4304/jcp.7.3.608-615

[19] Yu-Chi Chung, I-Fang Su, Chiang Lee. Efficient computation of combinatorial skyline queries. Information Systems, 2013(38): 369-387.

DOI: 10.1016/j.is.2012.10.005