{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:58:56Z","timestamp":1760057936992,"version":"build-2065373602"},"reference-count":51,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T00:00:00Z","timestamp":1741046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>While classical skyline queries identify interesting data within large datasets, flexible skylines introduce preferences through constraints on attribute weights, and further reduce the data returned. However, computing these queries can be time-consuming for large datasets. We propose and implement a parallel computation scheme consisting of a parallel phase followed by a sequential phase, and apply it to flexible skylines. We assess the additional effect of an initial filtering phase to reduce dataset size before parallel processing, and the elimination of the sequential part (the most time-consuming) altogether. All our experiments are executed in the PySpark framework for a number of different datasets of varying sizes and dimensions.<\/jats:p>","DOI":"10.3390\/a18030141","type":"journal-article","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T04:58:17Z","timestamp":1741064297000},"page":"141","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Partitioning Strategies for Parallel Computation of Flexible Skylines"],"prefix":"10.3390","volume":"18","author":[{"given":"Emilio","family":"De Lorenzis","sequence":"first","affiliation":[{"name":"Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Piazza Leonardo 32, 20133 Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2726-7683","authenticated-orcid":false,"given":"Davide","family":"Martinenghi","sequence":"additional","affiliation":[{"name":"Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Piazza Leonardo 32, 20133 Milan, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,4]]},"reference":[{"key":"ref_1","unstructured":"De Lorenzis, E. (2025, February 28). Computation of Flexible Skylines in a Distributed Environment. Available online: https:\/\/github.com\/emilio99-del\/Master-Thesis."},{"key":"ref_2","unstructured":"B\u00f6rzs\u00f6nyi, S., Kossmann, D., and Stocker, K. (2001, January 2\u20136). The Skyline Operator. Proceedings of the 17th International Conference on Data Engineering, Heidelberg, Germany."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"18:1","DOI":"10.1145\/3406113","article-title":"Flexible Skylines: Dominance for Arbitrary Sets of Monotone Functions","volume":"45","author":"Ciaccia","year":"2020","journal-title":"ACM Trans. Database Syst."},{"key":"ref_4","unstructured":"Dayal, U., Ramamritham, K., and Vijayaraman, T.M. (2003, January 5\u20138). Skyline with Presorting. Proceedings of the 19th International Conference on Data Engineering, Bangalore, India."},{"key":"ref_5","unstructured":"Pinari, E. (2022). Parallel Implementations of the Skyline Query Using PySpark. [Master\u2019s Thesis, Politecnico di Milano]."},{"key":"ref_6","unstructured":"Pindozzi, A. (2023). Scalable Solutions for Skyline Computation Using PySpark: Exploring Parallel Algorithms. [Master\u2019s Thesis, Politecnico di Milano]."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Cosgaya-Lozano, A., Rau-Chaplin, A., and Zeh, N. (2007, January 13\u201316). Parallel Computation of Skyline Queries. Proceedings of the 21st Annual International Symposium on High Performance Computing Systems and Applications (HPCS 2007), Saskatoon, SK, Canada.","DOI":"10.1109\/HPCS.2007.25"},{"key":"ref_8","unstructured":"Amer-Yahia, S., Christophides, V., Kementsietsidis, A., Garofalakis, M.N., Idreos, S., and Leroy, V. (2014, January 24\u201328). Efficient Skyline Computation in MapReduce. Proceedings of the 17th International Conference on Extending Database Technology, EDBT 2014, Athens, Greece."},{"key":"ref_9","unstructured":"Wang, J.T. (2008, January 10\u201312). Angle-based space partitioning for efficient parallel skyline computation. Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2008, Vancouver, BC, Canada."},{"key":"ref_10","unstructured":"Tan, K., Eng, P., and Ooi, B.C. (2001, January 11\u201314). Efficient Progressive Skyline Computation. Proceedings of the VLDB 2001, Proceedings of 27th International Conference on Very Large Data Bases, Roma, Italy."},{"key":"ref_11","unstructured":"Halevy, A.Y., Ives, Z.G., and Doan, A. (2003, January 9\u201312). An Optimal and Progressive Algorithm for Skyline Queries. Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1145\/1061318.1061320","article-title":"Progressive skyline computation in database systems","volume":"30","author":"Papadias","year":"2005","journal-title":"TODS"},{"key":"ref_13","unstructured":"Yu, P.S., Tsotras, V.J., Fox, E.A., and Liu, B. (2006, January 6\u201311). SaLSa: Computing the skyline without scanning the whole sky. Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management, Arlington, VA, USA."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ciaccia, P., and Martinenghi, D. (2018, January 22\u201326). FA + TA < FSA: Flexible Score Aggregation. Proceedings of the 27th ACM International Conference on Information and Knowledge Management, CIKM 2018, Torino, Italy.","DOI":"10.1145\/3269206.3271753"},{"key":"ref_15","unstructured":"Li, G., Li, Z., Idreos, S., and Srivastava, D. (2021, January 20\u201325). Marrying Top-k with Skyline Queries: Relaxing the Preference Input while Producing Output of Controllable Size. Proceedings of the SIGMOD \u201921: International Conference on Management of Data, Virtual Event, China."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Mendelzon, A.O., and Paredaens, J. (1998, January 1\u20133). Fuzzy Queries in Multimedia Database Systems. Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, Seattle, WA, USA.","DOI":"10.1145\/275487.275488"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1109\/TKDE.2011.266","article-title":"Skyline Processing on Distributed Vertical Decompositions","volume":"25","author":"Trimponias","year":"2013","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/2536669.2536671","article-title":"Skyline queries, front and back","volume":"42","author":"Chomicki","year":"2013","journal-title":"SIGMOD Record"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1059","DOI":"10.1109\/TKDE.2008.235","article-title":"Efficient Skyline Computation in Structured Peer-to-Peer Systems","volume":"21","author":"Cui","year":"2009","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1145\/1327452.1327492","article-title":"MapReduce: Simplified data processing on large clusters","volume":"Volume 51","author":"Dean","year":"2008","journal-title":"Proceedings of the Communications of the ACM"},{"key":"ref_21","unstructured":"Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauley, M.J., Franklin, M.J., Shenker, S., and Stoica, I. (2010, January 22\u201325). Spark: Cluster computing with working sets. Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud), Boston, MA, USA."},{"key":"ref_22","unstructured":"De Lorenzis, E. (2022). Computation of Flexible Skylines in a Distributed Environment. [Master\u2019s Thesis, Politecnico di Milano (Italy)]."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1391729.1391730","article-title":"A survey of top-k query processing techniques in relational database systems","volume":"40","author":"Ilyas","year":"2008","journal-title":"ACM Comput. Surv."},{"key":"ref_24","first-page":"1554","article-title":"Maximum Rank Query","volume":"8","author":"Mouratidis","year":"2015","journal-title":"PVLDB"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3698807","article-title":"Directional Queries: Making Top-k Queries More Effective in Discovering Relevant Results","volume":"2","author":"Ciaccia","year":"2024","journal-title":"Proc. ACM Manag. Data"},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Nakagawa, M., Man, D., Ito, Y., and Nakano, K. (2009, January 8\u201311). A Simple Parallel Convex Hulls Algorithm for Sorted Points and the Performance Evaluation on the Multicore Processors. Proceedings of the 2009 International Conference on Parallel and Distributed Computing, Applications and Technologies, PDCAT 2009, Higashi Hiroshima, Japan.","DOI":"10.1109\/PDCAT.2009.56"},{"key":"ref_27","unstructured":"Chechik, S., Navarro, G., Rotenberg, E., and Herman, G. (2022, January 5\u20139). ParGeo: A Library for Parallel Computational Geometry. Proceedings of the 30th Annual European Symposium on Algorithms, ESA 2022, Berlin\/Potsdam, Germany. LIPIcs."},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Kwon, H., Oh, S., and Baek, J.W. (2024). Algorithmic Efficiency in Convex Hull Computation: Insights from 2D and 3D Implementations. Symmetry, 16.","DOI":"10.3390\/sym16121590"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3453474","article-title":"The Hypervolume Indicator: Computational Problems and Algorithms","volume":"54","author":"Guerreiro","year":"2022","journal-title":"ACM Comput. Surv."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.tcs.2010.09.026","article-title":"Approximating the least hypervolume contributor: NP-hard in general, but fast in practice","volume":"425","author":"Bringmann","year":"2012","journal-title":"Theor. Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Martinenghi, D. (2025). Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples. Algorithms, 18.","DOI":"10.3390\/a18010029"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Andreasen, T., Yager, R.R., Bulskov, H., Christiansen, H., and Larsen, H.L. (2009, January 26\u201328). Trajectory Clustering via Effective Partitioning. Proceedings of the Flexible Query Answering Systems, 8th International Conference, FQAS 2009, Roskilde, Denmark. Proceedings; Lecture Notes in Computer Science.","DOI":"10.1007\/978-3-642-04957-6"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/j.ins.2013.12.003","article-title":"Analysing microarray expression data through effective clustering","volume":"262","author":"Masciari","year":"2014","journal-title":"Inf. Sci."},{"key":"ref_34","first-page":"113","article-title":"A Deep Learning Approach to Fake News Detection","volume":"Volume 12117","author":"Helic","year":"2020","journal-title":"Proceedings of the Foundations of Intelligent Systems\u201425th International Symposium, ISMIS 2020"},{"key":"ref_35","unstructured":"Desai, B.C., and Cho, W. (2020, January 12\u201314). Detecting fake news by image analysis. Proceedings of the IDEAS 2020: 24th International Database Engineering & Applications Symposium, Seoul, Republic of Korea."},{"key":"ref_36","unstructured":"Desai, B.C., Sacc\u00e0, D., and Greco, S. (2009, January 16\u201318). Efficient and effective RFID data warehousing. Proceedings of the International Database Engineering and Applications Symposium (IDEAS 2009), Cetraro, Calabria, Italy. ACM International Conference Proceeding Series."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/2487259.2487263","article-title":"RFID-data compression for supporting aggregate queries","volume":"38","author":"Fazzinga","year":"2013","journal-title":"ACM Trans. Database Syst."},{"key":"ref_38","unstructured":"Desai, B.C., Larriba-Pey, J.L., and Bernardino, J. (2013, January 9\u201311). Sequential pattern mining from trajectory data. Proceedings of the 17th International Database Engineering & Applications Symposium, IDEAS \u201913, Barcelona, Spain."},{"key":"ref_39","unstructured":"Bozzon, A., Catallo, I., Ciceri, E., Fraternali, P., Martinenghi, D., and Tagliasacchi, M. (2012, January 17). A Framework for Crowdsourced Multimedia Processing and Querying. Proceedings of the First International Workshop on Crowdsourcing Web Search, Lyon, France. Available online: http:\/\/ceur-ws.org\/Vol-842\/crowdsearch-bozzon.pdf."},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10844-013-0267-2","article-title":"Dealing with trajectory streams by clustering and mathematical transforms","volume":"42","author":"Costa","year":"2014","journal-title":"J. Intell. Inf. Syst."},{"key":"ref_41","unstructured":"Chandra, A.K., and Merlin, P.M. (1977, January 4\u20136). Optimal implementation of conjunctive queries in relational databases. Proceedings of the 9th Annual ACM Symposium on Theory of Computing, Boulder, CO, USA."},{"key":"ref_42","doi-asserted-by":"crossref","unstructured":"Shmueli, O. (1987, January 23\u201325). Decidability and expressiveness aspects of logic queries. Proceedings of the Sixth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, San Diego, CA, USA.","DOI":"10.1145\/28659.28685"},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"326","DOI":"10.1007\/978-3-540-87877-3_24","article-title":"Conjunctive Query Containment under Access Limitations","volume":"Volume 5231","author":"Li","year":"2008","journal-title":"Proceedings of the Conceptual Modeling\u2014ER 2008, 27th International Conference on Conceptual Modeling"},{"key":"ref_44","first-page":"33","article-title":"Dynamic Query Optimization under Access Limitations and Dependencies","volume":"15","author":"Calvanese","year":"2009","journal-title":"J. Univers. Comput. Sci."},{"key":"ref_45","unstructured":"Horrocks, I. (2006, January 13\u201317). Semantic web reasoning with OWL: Why it\u2019s hard and where it\u2019s going. Proceedings of the International Conference on Logic for Programming Artificial Intelligence and Reasoning (LPAR), Phnom Penh, Cambodia."},{"key":"ref_46","unstructured":"Bechhofer, S., van Harmelen, F., Hendler, J., Horrocks, I., McGuinness, D.L., Patel-Schneider, P.F., and Stein, L.A. (2025, February 28). OWL Web Ontology Language Reference. Available online: https:\/\/research.vu.nl\/en\/publications\/owl-web-ontology-language-reference."},{"key":"ref_47","unstructured":"Koch, C., Gehrke, J., Garofalakis, M.N., Srivastava, D., Aberer, K., Deshpande, A., Florescu, D., Chan, C.Y., Ganti, V., and Kanne, C. (2007, January 23\u201327). Efficient Skyline Computation over Low-Cardinality Domains. Proceedings of the 33rd International Conference on Very Large Data Bases, Vienna, Austria."},{"key":"ref_48","doi-asserted-by":"crossref","unstructured":"Godfrey, P. (2004, January 17\u201320). Skyline Cardinality for Relational Processing. Proceedings of the Foundations of Information and Knowledge Systems (FoIKS), Wilhelminenburg Castle, Austria.","DOI":"10.1007\/978-3-540-24627-5_7"},{"key":"ref_49","first-page":"1","article-title":"Efficient and Effective Cardinality Estimation for Skyline Family","volume":"1","author":"Miao","year":"2023","journal-title":"Proc. ACM Manag. Data"},{"key":"ref_50","unstructured":"Lu, Y., Zhao, J., Chen, L., Cui, B., and Yang, D. (2008, January 1\u20135). Effective Skyline Cardinality Estimation on Data Streams. Proceedings of the International Conference on Database and Expert Systems Applications (DEXA), Turin, Italy."},{"key":"ref_51","first-page":"1","article-title":"On Estimating the Maximum Domination Value and the Skyline Cardinality in High Dimensional Datasets","volume":"3","author":"Tiakas","year":"2013","journal-title":"Int. J.-Knowl.-Based Organ."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/3\/141\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:46:48Z","timestamp":1760028408000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/3\/141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,4]]},"references-count":51,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["a18030141"],"URL":"https:\/\/doi.org\/10.3390\/a18030141","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,3,4]]}}}