{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:44:03Z","timestamp":1760240643592,"version":"build-2065373602"},"reference-count":28,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2019,8,13]],"date-time":"2019-08-13T00:00:00Z","timestamp":1565654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"KAKENHI","award":["16K00155"],"award-info":[{"award-number":["16K00155"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The skyline query and its variant queries are useful functions in the early stages of a knowledge-discovery processes. The skyline query and its variant queries select a set of important objects, which are better than other common objects in the dataset. In order to handle big data, such knowledge-discovery queries must be computed in parallel distributed environments. In this paper, we consider an efficient parallel algorithm for the \u201cK-skyband query\u201d and the \u201ctop-k dominating query\u201d, which are popular variants of skyline query. We propose a method for computing both queries simultaneously in a parallel distributed framework called MapReduce, which is a popular framework for processing \u201cbig data\u201d problems. Our extensive evaluation results validate the effectiveness and efficiency of the proposed algorithm on both real and synthetic datasets.<\/jats:p>","DOI":"10.3390\/a12080166","type":"journal-article","created":{"date-parts":[[2019,8,14]],"date-time":"2019-08-14T03:59:26Z","timestamp":1565755166000},"page":"166","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["MapReduce Algorithm for Variants of Skyline Queries: Skyband and Dominating Queries"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7791-8248","authenticated-orcid":false,"given":"Md. Anisuzzaman","family":"Siddique","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, University of Rajshahi, Rajshahi 6205, Bangladesh"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3220-1726","authenticated-orcid":false,"given":"Hao","family":"Tian","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8521, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2509-1191","authenticated-orcid":false,"given":"Mahboob","family":"Qaosar","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, University of Rajshahi, Rajshahi 6205, Bangladesh"},{"name":"Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8521, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7130-2864","authenticated-orcid":false,"given":"Yasuhiko","family":"Morimoto","sequence":"additional","affiliation":[{"name":"Graduate School of Engineering, Hiroshima University, Higashi-Hiroshima 739-8521, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,8,13]]},"reference":[{"key":"ref_1","unstructured":"Borzsonyi, S., Kossmann, D., and Stocker, K. (2001, January 2\u20136). The skyline operator. Proceedings of the IEEE International Conference on Data Engineering (ICDE), Heidelberg, Germany."},{"key":"ref_2","unstructured":"Yiu, M.L., and Mamoulis, N. (2007, January 23\u201327). Efficient Processing of Top-k Dominating Queries on Multi-Dimensional Data. Proceedings of the VLDB Endowment, Vienna, Austria."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Papadias, D., Tao, Y., Fu, G., and Seeger, B. (2005). Progressive skyline computation in database systems. ACM Trans. Database Syst., 41\u201382.","DOI":"10.1145\/1061318.1061320"},{"key":"ref_4","unstructured":"Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. (2003, January 5\u20138). Skyline with Presorting. Proceedings of the IEEE International Conference on Data Engineering (ICDE), Bangalore, India."},{"key":"ref_5","unstructured":"Godfrey, P., Shipley, R., and Gryz, J. (September, January 30). Maximal vector computation in large datasets. Proceedings of the VLDB Endowment, Trondheim, Norway."},{"key":"ref_6","unstructured":"Kossmann, D., Ramsak, F., and Rost, S. (2002, January 20\u201323). Shooting stars in the sky: An online algorithm for skyline queries. Proceedings of the VLDB Endowment, Hong Kong, China."},{"key":"ref_7","unstructured":"Tan, K.L., Eng, P.K., and Ooi, B.C. (2001, January 11\u201314). Efficient Progressive Skyline Computation. Proceedings of the VLDB Endowment, Roma, Italy."},{"key":"ref_8","unstructured":"Yuan, Y., Lin, X., Liu, Q., Wang, W., Yu, J.X., and Zhang, Q. (September, January 30). Efficient computation of the skyline cube. Proceedings of the VLDB Endowment, Trondheim, Norway."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Xia, T., and Zhang, D. (2006, January 27\u201329). Refreshing the sky: The compressing skycube with efficient support for frequent updates. Proceedings of the ACM SIGMOD International conference on Management of Data, Chicago, IL, USA.","DOI":"10.1145\/1142473.1142529"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Chan, C.Y., Jagadish, H.V., Tan, K.L., Tung, A.K.H., and Zhang, Z. (2006, January 26\u201331). On High Dimensional Skylines. Proceedings of the Extending Database Technology (EDBT) Conference, Munich, Germany.","DOI":"10.1007\/11687238_30"},{"key":"ref_11","unstructured":"Li, C., Ooi, B.C., Tung, A.K.H., and Wang, S. (2006, January 27\u201329). DADA: A Data Cube for Dominant Relationship Analysis. Proceedings of the ACM SIGMOD International conference on Management of Data, Chicago, IL, USA."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Lin, X., Yuan, Y., Zhang, Q., and Zhang, Y. (2007, January 15\u201320). Selecting stars: The k most representative skyline operator. Proceedings of the IEEE International Conference on Data Engineering (ICDE), Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367854"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Chan, C.Y., Jagadish, H.V., Tan, K.L., Tung, A.K.H., and Zhang, Z. (2006, January 27\u201329). Finding k-Dominant Skyline in High Dimensional Space. Proceedings of the ACM SIGMOD International conference on Management of Data, Chicago, IL, USA.","DOI":"10.1145\/1142473.1142530"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Gong, Z., Sun, G.Z., Yuan, J., and Zhong, Y. (2009, January 10\u201311). Efficient Top-k Query Algorithms Using K-skyband Partition. Proceedings of the of Scalable Information Systems, Hong Kong, China.","DOI":"10.1007\/978-3-642-10485-5_21"},{"key":"ref_15","unstructured":"Lin, X., Yuan, Y., Wang, W., and Lu, H. (2005, January 5\u20138). Stabbing the sky: Efficient Skyline computation over sliding windows. Proceedings of the IEEE International Conference on Data Engineering (ICDE), Tokoyo, Japan."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Balke, W.T., G\u00fcntzer, U., and Zheng, J.X. (2004, January 14\u201318). Efficient distributed skylining for web information systems. Proceedings of the Extending Database Technology (EDBT) Conference, Crete, Greece.","DOI":"10.1007\/978-3-540-24741-8_16"},{"key":"ref_17","unstructured":"Tao, Y., Xiao, X., and Pei, J. (2006, January 3\u20137). Subsky: Efficient Computation of Skylines in Subspaces. Proceedings of the IEEE International Conference on Data Engineering (ICDE), Atlanta, GA, USA."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Papadias, D., Tao, Y., Fu, G., and Seeger, B. (2003, January 9\u201312). An optimal and progressive algorithm for skyline queries. Proceedings of the ACM SIGMOD International conference on Management of Data, San Diego, CA, USA.","DOI":"10.1145\/872757.872814"},{"key":"ref_19","unstructured":"Dellis, E., and Seeger, B. (2007, January 23\u201327). Efficient Computation of Reverse Skyline Queries. Proceedings of the VLDB Endowment, Vienna, Austria."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Blanas, S., Patel, J.M., Ercegovac, V., Rao, J., Shekita, E.J., and Tian, Y. (2010, January 6\u201310). A comparison of join algorithms for log processing in MapReduce. Proceedings of the ACM SIGMOD International Conference on Management of Data, Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807273"},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Jiang, D., Tung, A.K.H., and Chen, G. (2011). MAP-JOIN-REDUCE: Toward Scalable and Efficient Data Analysis on Large Clusters. IEEE Trans. Knowl. Data Eng., 1299\u20131311.","DOI":"10.1109\/TKDE.2010.248"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Vernica, R., Carey, M.J., and Li, C. (2010, January 6\u201310). Efficient parallel set-similarity joins using MapReduce. Proceedings of the ACM SIGMOD International conference on Management of Data, Indianapolis, IN, USA.","DOI":"10.1145\/1807167.1807222"},{"key":"ref_23","unstructured":"Apache (2019, June 03). Apache Hadoop. Available online: https:\/\/hadoop.apache.org."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2002","DOI":"10.14778\/2556549.2556580","article-title":"Parallel Computation of Skyline and Reverse Skyline Queries Using MapReduce","volume":"6","author":"Park","year":"2013","journal-title":"Proc. VLDB Endow."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Tao, Y., Lin, W., and Xiao, X. (2013, January 22\u201327). Minimal MapReduce Algorithm. Proceedings of the ACM SIGMOD International Conference on Management of Data, New York, NY, USA.","DOI":"10.1145\/2463676.2463719"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Siddique, M.A., Tian, H., and Morimoto, Y. (2015). k-dominant Skyline Query Computation in MapReduce Environment. IEICE Trans. Inf. Syst., 1027\u20131034.","DOI":"10.1587\/transinf.2014DAP0010"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Ezatpoor, P., Zhan, J., Wu, J.M., and Chiu, C. (2018). Finding Top-k Dominance on Incomplete Big Data Using MapReduce Framework. IEEE Access, 7872\u20137887.","DOI":"10.1109\/ACCESS.2018.2797048"},{"key":"ref_28","first-page":"13","article-title":"Top-K Dominating Query Processing over Distributed Data Streams","volume":"5","year":"2018","journal-title":"Glob. J. Eng. Sci. Res. Manag."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/166\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:10:44Z","timestamp":1760188244000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/8\/166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,13]]},"references-count":28,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2019,8]]}},"alternative-id":["a12080166"],"URL":"https:\/\/doi.org\/10.3390\/a12080166","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,8,13]]}}}