{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T00:35:19Z","timestamp":1759970119416,"version":"build-2065373602"},"reference-count":46,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"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>Several indicators have been recently proposed for the measurement of various characteristics of the tuples of a dataset\u2014particularly the so-called skyline tuples, i.e., those that are not dominated by other tuples. Numeric indicators are very important as they may, e.g., provide an additional criterion to be used to rank skyline tuples and focus on a subset thereof. We focus on an indicator of robustness that may be measured for any skyline tuple t: the grid resistance, i.e., how large-value perturbations can be tolerated for t to remain non-dominated (and thus in the skyline). The computation of this indicator typically involves one or more rounds of computation of the skyline itself or, at least, of dominance relationships. Building on recent advances in partitioning strategies allowing the parallel computation of skylines, we discuss how these strategies can be adapted to the computation of the indicator.<\/jats:p>","DOI":"10.3390\/a18010029","type":"journal-article","created":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T03:38:41Z","timestamp":1736221121000},"page":"29","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2726-7683","authenticated-orcid":false,"given":"Davide","family":"Martinenghi","sequence":"first","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,1,7]]},"reference":[{"key":"ref_1","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_2","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_3","unstructured":"Mullesgaard, K., Pederseny, J.L., Lu, H., and Zhou, Y. (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_4","unstructured":"Hasan, M.A., and Xiong, L. (2022, January 17\u201321). Parallel Skyline Processing Using Space Pruning on GPU. Proceedings of the 31st ACM International Conference on Information & Knowledge Management, Atlanta, GA, USA."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"102258","DOI":"10.1016\/j.datak.2023.102258","article-title":"S_IDS: An efficient skyline query algorithm over incomplete data streams","volume":"149","author":"Bai","year":"2024","journal-title":"Data Knowl. Eng."},{"key":"ref_6","unstructured":"Ciaccia, P., and Martinenghi, D. (2024). Optimization Strategies for Parallel Computation of Skylines. arXiv."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"991","DOI":"10.1109\/TKDE.2010.47","article-title":"Flexible and Efficient Resolution of Skyline Query Size Constraints","volume":"23","author":"Lu","year":"2011","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_8","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 2003 ACM SIGMOD International Conference on Management of Data, San Diego, CA, USA.","DOI":"10.1145\/872811.872814"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"695","DOI":"10.1007\/s00778-008-0117-y","article-title":"Multi-dimensional top-k dominating queries","volume":"18","author":"Yiu","year":"2009","journal-title":"VLDB J."},{"key":"ref_10","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 33rd International Conference on Very Large Data Bases, University of Vienna, Vienna, Austria."},{"key":"ref_11","unstructured":"Chan, C.Y., Jagadish, H.V., Tan, K., Tung, A.K.H., and Zhang, Z. (2006, January 26\u201331). On High Dimensional Skylines. Proceedings of the Advances in Database Technology\u2014EDBT 2006, 10th International Conference on Extending Database Technology, Munich, Germany."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Zhang, Z., Guo, X., Lu, H., Tung, A.K.H., and Wang, N. (November, January 31). Discovering strong skyline points in high dimensional spaces. Proceedings of the 2005 ACM CIKM International Conference on Information and Knowledge Management, Bremen, Germany.","DOI":"10.1145\/1099554.1099610"},{"key":"ref_13","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 23rd International Conference on Data Engineering, ICDE 2007, The Marmara Hotel, Istanbul, Turkey.","DOI":"10.1109\/ICDE.2007.367854"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1114","DOI":"10.14778\/1920841.1920980","article-title":"Regret-Minimizing Representative Databases","volume":"3","author":"Nanongkai","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Tao, Y., Ding, L., Lin, X., and Pei, J. (April, January 29). Distance-Based Representative Skyline. Proceedings of the 25th International Conference on Data Engineering, ICDE 2009, Shanghai, China.","DOI":"10.1109\/ICDE.2009.84"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"389","DOI":"10.14778\/2732269.2732275","article-title":"Computing k-Regret Minimizing Sets","volume":"7","author":"Chester","year":"2014","journal-title":"Proc. VLDB Endow."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Vlachou, A., Doulkeridis, C., N\u00f8rv\u00e5g, K., and Vazirgiannis, M. (2008, January 7\u201312). Skyline-based Peer-to-Peer Top-k Query Processing. Proceedings of the 24th International Conference on Data Engineering, ICDE 2008, Canc\u00fan, Mexico.","DOI":"10.1109\/ICDE.2008.4497576"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"943","DOI":"10.1016\/j.datak.2010.03.008","article-title":"Ranking the sky: Discovering the importance of skyline points through subspace dominance relationships","volume":"69","author":"Vlachou","year":"2010","journal-title":"Data Knowl. Eng."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Lofi, C., and Balke, W. (2013). On Skyline Queries and How to Choose from Pareto Sets. Advanced Query Processing, Volume 1: Issues and Trends, Springer.","DOI":"10.1007\/978-3-642-28323-9_2"},{"key":"ref_20","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_21","unstructured":"(2023, November 23). San Francisco Open Data. Employee Compensation in SF. Available online: https:\/\/data.world\/data-society\/employee-compensation-in-sf."},{"key":"ref_22","unstructured":"Hebrail, G., and Berard, A. (2024, March 04). Individual Household Electric Power Consumption. Available online: https:\/\/archive.ics.uci.edu\/dataset\/235\/individual+household+electric+power+consumption."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Vlachou, A., Doulkeridis, C., and Kotidis, Y. (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.","DOI":"10.1145\/1376616.1376642"},{"key":"ref_24","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., and Stein, C. (2009). Introduction to Algorithms, Mit Press. [3rd ed.]."},{"key":"ref_25","unstructured":"Chomicki, J., Godfrey, P., Gryz, J., and Liang, D. (2003, January 5\u20138). Skyline with Presorting. Proceedings of the 19th International Conference on Data Engineering, Bangalore, India."},{"key":"ref_26","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_27","doi-asserted-by":"crossref","first-page":"352","DOI":"10.14778\/1920841.1920889","article-title":"Proximity Rank Join","volume":"3","author":"Martinenghi","year":"2010","journal-title":"Proc. VLDB Endow."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2143","DOI":"10.1109\/TKDE.2011.161","article-title":"Cost-Aware Rank Join with Random and Sorted Access","volume":"24","author":"Martinenghi","year":"2012","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1454","DOI":"10.14778\/3137628.3137653","article-title":"Reconciling Skyline and Ranking Queries","volume":"10","author":"Ciaccia","year":"2017","journal-title":"Proc. VLDB Endow."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Mouratidis, K., Li, K., and Tang, B. (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.","DOI":"10.1145\/3448016.3457299"},{"key":"ref_31","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":"ACM Trans. Database Syst. TODS"},{"key":"ref_32","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_33","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_34","doi-asserted-by":"crossref","unstructured":"Gao, X., Li, J., and Miao, D. (2024, January 13\u201316). Computing All Restricted Skyline Probabilities on Uncertain Datasets. Proceedings of the 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands.","DOI":"10.1109\/ICDE60146.2024.00363"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Fagin, R. (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_36","doi-asserted-by":"crossref","first-page":"1554","DOI":"10.14778\/2824032.2824053","article-title":"Maximum Rank Query","volume":"8","author":"Mouratidis","year":"2015","journal-title":"Proc. VLDB Endow."},{"key":"ref_37","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_38","doi-asserted-by":"crossref","unstructured":"Wang, Y., Yesantharao, R., Yu, S., Dhulipala, L., Gu, Y., and Shun, J. (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.","DOI":"10.1145\/3503221.3508429"},{"key":"ref_39","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_40","doi-asserted-by":"crossref","first-page":"119: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_41","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_42","doi-asserted-by":"crossref","unstructured":"Soliman, M.A., Ilyas, I.F., Martinenghi, D., and Tagliasacchi, M. (2011, January 12\u201316). Ranking with uncertain scoring functions: Semantics and sensitivity measures. Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD 2011, Athens, Greece.","DOI":"10.1145\/1989323.1989408"},{"key":"ref_43","unstructured":"Masciari, E. (2009, January 26\u201328). Trajectory Clustering via Effective Partitioning. Proceedings of the Flexible Query Answering Systems, 8th International Conference, FQAS 2009, Roskilde, Denmark."},{"key":"ref_44","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_45","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, Italy. ACM International Conference Proceeding Series."},{"key":"ref_46","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."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/1\/29\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T10:24:02Z","timestamp":1759919042000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/1\/29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":46,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,1]]}},"alternative-id":["a18010029"],"URL":"https:\/\/doi.org\/10.3390\/a18010029","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,1,7]]}}}