# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 1 Introduction  
Multi-criteria analysis aims to identify the most suitable alternatives in datasets characterized by multiple attributes. This challenge is prevalent in many data-intensive fields and has been amplified by the advent of big data, which emphasizes the importance of efficiently searching through vast datasets. Skyline queries [1] are a widely used method to address this issue, filtering out alternatives that are dominated by others. An alternative \(a\) is said to dominate \(b\) if \(a\) is at least as good as \(b\) in all attributes and strictly better in at least one. Non-dominated alternatives are valuable because they represent the top choice for at least one ranking function, thus offering a comprehensive view of the best options. To understand and illustrate the impact of skyline queries, let us consider a real-world use case using a real estate dataset (like the Zillow dataset from zillow.com, accessed on 3 December 2024, which we will use in our experiments). A real estate investor is looking to purchase properties that offer the best combination of price, size, location, and other attributes, but is not sure about what aspects matter the most. Therefore, the investor wants to identify properties that are not dominated by others in terms of these attributes, i.e., no other property is better in all of these aspects. For example, a property might be cheaper but smaller or larger but more expensive. Skylines offer a way to identify properties that offer all the best possible (i.e., non-dominated) trade-offs. For instance, suppose that we have the following properties with attributes (price, size, bedrooms, bathrooms): A = (EUR 800 K, 110 m\({}^{2}\), 3, 2); B = (EUR 850 K, 110 m\({}^{2}\), 3, 1); C = (EUR 720 K, 90 m\({}^{2}\), 2, 2); D = (EUR 610 K, 85 m\({}^{2}\), 3, 2). A skyline query would identify Property A and Property D as possible alternatives, while B (dominated by A) and C (dominated by D) would be discarded. Bydiscarding unsuitable options, skyline queries can then significantly facilitate decision-making in this and many other data-intensive scenarios. A common limitation of skyline queries is their complexity, generally quadratic in the dataset size, which poses challenges in big data contexts. To mitigate this, researchers have been exploring dataset partitioning strategies to enable parallel processing, thereby reducing the overall computation time. A common application scenario, which is the one used here, regards the so-called _horizontal partitioning_, in which each partition is assigned a subset of the tuples. Peer-to-peer (P2P) architectures [2] first explored this approach, by having each peer to compute its skyline locally and then merging it with the rest of the network. The typical approach, indeed, involves a two-phase process: the first involves computing local skylines within each partition; the second involves merging these local skylines to create a pruned dataset for the final skyline computation. The aim is to eliminate as many dominated alternatives as possible during the local skyline phase, minimizing the dataset size for the final computation. With the maturity of parallel computation paradigms such as Map-Reduce and Spark and the usage of GPUs, parallel solutions reflecting this pattern have become common [3, 4, 5] and have been subjected to careful experimental scrutiny [6]. Another limitation of skylines as a query tool is that they may return result sets that are too large and thus of little use to the final user. A way around this problem is to equip skyline tuples with additional numeric indicators that measure their \"strength\" according to various characteristics. With this, skyline tuples can be ranked and selected accordingly to offer a more concise result to the final user. Several previous research attempts, including [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20], have proposed a plethora of such indicators.