Hadjer Belaicha, Computer Sciences Department, Ahmed Ben Bella Oran1 University, Algeria
Lougmiri Zekri, Computer Sciences Department, Ahmed Ben Bella Oran1 University, Algeria
Larbi Sakhri, Computer Sciences Department, Ahmed Ben Bella Oran1 University, Algeria
The skyline computation is very important in the field of decision making. It gives solutions to help among a wide dataset and where information is contradictory, especially when the implemented solution is progressive. As the need to get rapid solution is growing, it will be suitable to exploit new machines’ performances and plate-forms. In this paper, we present a new solution of type divide-and-conquer for computing the skyline on GPU (Graphics Processing Units) cards. The proposed partitioning is adaptable to characteristics of the GPU. This proposition can lead to a well balanced computing and avoids overflows. The dominance tests are performed on points components in parallel and dominated points are early discarded unlike other solutions which save them for next loops. This way of comparison avoids threads' idleness. We compare our solution with other similar solutions on the same datasets. Experimentations show that our proposition is better in terms of time computing and exploitation of the GPU parallelism.
Skyline, GPU, Multi-criteria, Optimization, GNL, GSA, Threads, Partitioning
[1] Belaicha H., Zekri L., Sekhri L. Expérimentation d'une nouvelle stratégie pour le Calcul du Skyline sur GPU, COSI 2016 volume pages 183-194, 2016.
[2] Börzsonyi,S., Kossmann, D, Stocker, K. : The skyline operator. In ICDE2001. 421-430(2001).
[3] Bogh, k., Assents, I., Magnani, M. : Efficient gpu-based skyline computation. In DaMoN'13(2013).
[4] Bøgh, K.S., Chester, S., Assent, I. SkyAlign: A Portable, Work-Efficient Skyline Algorithm for Multicore and GPU Architectures. VLDB J.25(6): 817-841 (2016).
[5] Bøgh, K.S, Chester, S., Šidlauskas, D., Assent, I. Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures. SIGMOD’17, May 14 - 19, 2017, Raleigh, NC, USA.
[6] Choi, W., Liu, L., Boseon Yu, B. Multi-Criteria Decision Making with Skyline Computation. IEEE IRI 2012, August 8-10, 2012, Las Vegas, Nevada, USA.
[7] Chomicki, J., Godfrey, P., Gryz, J., & Liang, D. (2005). Skyline with presorting: Theory and optimizations. In Klopotek et al. (Ed.), Intelligent Information Processing and Web Mining, Gdansk, Poland (pp. 595-604).
[8] Flynn, M.J., Some Computer Organizations and Their Effectiveness. IEEE Transactions on Computers. Vol. c-21, No.9, September 1972.
[9] Haichuan, S., Masaru, K., Skyline Operator on Anti-correlated Distributions. August 26th -30th 2013, Riva del Garda, Trento, Italy. Proceeding of the VLDB Endowment, Vol. 6, No9.
[10] Kossmann, D., Ramsak, F., Rost, S. Shooting Stars in the Sky: an Online Algorithm for Skyline Queries. VLDB, 2002.
[11] Kung, H., Luccio, F., Preparata, F. On Finding the Maxima of a Set of Vectors. Journal of the ACM, 22(4), 1975.
[12] Lee, J., Kim, J., Hwang, S.: Supporting efficient distributed skyline computation using skyline views. In (DaWaK)(2009). Linz, Austria, 31 August -2 September 2009.
[13] Liknes, S., Vlachou, A., Doulkeridis, C., & Nørvag, K. (2014). APSkyline: Improved Skyline Computation for Multicore Architectures. Proc. DASFAA (pp. 312–326).
[14] Mullesgaardy, K., Pederseny, J. L., Luy, H., & Zhou, Y. (2014, March 24-28). Efficient Skyline Computation in MapReduce. Proc. 17th International Conference on Extending Database Technology (EDBT), Athens, Greece.
[15] Nickolls, J., Kirk, D., Graphics and Computing GPUs. Appendix_C. Computer Organization and Design. 5th edition. Morgan Kaufmann, 2014.
[16] Papadias, D., Tao, Y., Fu, G., & Seeger, B. (2003, June 9-12). An optimal and progressive algorithm for skyline queries. ACM SIGMOD’2003, San Diego, California (pp. 467-478).
[17] Pei, J., Jin, W., Ester, M., Tao, Y.. Catching the best views of the skyline: a semantic approach based on decisive subspaces. In VLDB, pages 253-264, 2005.
[18] Reges, S., Stepp, M. Building Java Programs. A Back to Basics Approach 4th edition by. Addison-Wesley. Second Edition. 2011.
[19] Tan, K., Eng, P., & Ooi, B. (2001, September). Efficient Progressive Skyline Computation. Proceedings of the 27th International Conference on Very Large Data Bases, Rome, Italy.
[20] Vlachou, A., Doulkeridis, C., & Kotidis, Y. (2008). Angle based Space Partitioning for Efficient Parallel Skyline Computation. Proc of ACM SIGMOD ’08, Vancouver, BC, Canada.
[21] Wang, W., Zhang, J., Sun, M., Ku, W.. Efficient Parallel Spatial Skyline Evaluation Using MapReduce. Published in Proc. 20th International Conference on Extending Database Technology (EDBT), March 21-24, 2017 - Venice, Italy.
[22] Yu. B, Choi. W, Liu. L; Exploring correlation for fast skyline computation The Journal of Supercomputing Volume 73 Issue 11, November 2017 Pages 5071-5102.
[23] Yuan, Y., Lin, X., Liu, Q., Wang, W., Xu, J., Yu, J., & Zhang, Q. (2005). Efficient computation of the skyline cube. Proceedings of VLDB (pp. 241-252).
[24] Zekri L, A New Progressive Method for Computing Skyline Queries. Journal of Information Technology Research Volume 10 • Issue 3 • July-September 2017.
[25] Zhang, B., Zhou, S., and Guan, J., Adapting Skyline Computation to the MapReduce Framework: Algorithms and Experiments. DASFAA Workshops 2011, LNCS 6637, pp. 403–414, 2011.
APA:
Belaicha, H., Zekri, L., & Sakhri, L. (2019). An Efficient Contribution to Computing the Skyline on GPU. International Journal of Grid and Distributed Computing (IJGDC), ISSN: 2005-4262 (Print); 2207-6379 (Online), NADIA, 12(2), 49-66. doi: 10.33832/ijgdc.2019.12.2.04.
MLA:
Belaicha, Hadjer, et al. “An Efficient Contribution to Computing the Skyline on GPU.” International Journal of Grid and Distributed Computing (IJGDC), ISSN: 2005-4262 (Print); 2207-6379 (Online), NADIA, vol. 12, no. 2, 2019, pp. 49-66. IJGDC, http://article.nadiapub.com/IJGDC/vol12_no2/4.html.
IEEE:
[1] H. Belaicha, L. Zekri, and L. Sakhri, "An Efficient Contribution to Computing the Skyline on GPU." International Journal of Grid and Distributed Computing (IJGDC), ISSN: 2005-4262 (Print); 2207-6379 (Online), NADIA, vol. 12, no. 2, pp. 49-66, Dec 2019.
IJGDC aims to facilitate and support research related to grid and distributed computing technology and its applications. Our Journal provides a chance for academic and industry professionals to discuss recent progress in the area of grid and distributed computing technology.
