# Parallelizing the Computation of Grid Resistance to Measure the Strength of Skyline Tuples
## 6 Related Work  
In the last two and a half decades, the skyline operator has spurred numerous research efforts aiming to reduce its computational cost and augment its practicality by trying to overcome some of its most common limitations. While some of the essential works in this line of research have been presented already in Section 1, we now try to provide a more complete picture. Skylines are the preference-agnostic counterpart of ranking (also known as top-\(k\)) queries; while the former offer a wide overview of a dataset, the latter are more efficient, provide control over the output size, and apply to a large variety of queries, including complex joins and all types of utility components in their scoring functions (i.e., the main tool for the specification of preferences) [26; 27; 28]. Recently, hybrid approaches have started to appear, trying to exploit the advantages of both [29; 30]. As regards the efficiency aspects, several algorithms have been developed to address the centralized computation of skylines, including [1; 25; 31]. In order to address the most serious shortcomings of skylines, many different variants have been proposed so as to, e.g., accommodate user preferences and control or reduce the output size (which tends to grow uncontrollably in anti-correlated or highly dimensional data) or even add a probabilistic aspect to it; a non-exhaustive list of works in this direction is [32; 30; 33; 34]. Improvements in efficiency have been studied also in the case of the data distribution. In particular, in addition to the _horizontal partitioning_ strategies discussed here with the pattern described at the beginning of Section 4, _vertical partitioning_ has been studied extensively in the seminal works of [PERSON] [35] and subsequent contributions, addressing the so-called _middleware scenario_. While skyline tuples are part of the commonly accepted semantics of \"potentially optimal\" tuples of a dataset, in their standard version, they are returned to the final user as an unranked bunch. Recent attempts have been trying to counter this possibly overwhelming effect, which is particularly problematic in the case of very large skylines, by equipping skyline tuples with additional numeric scores that can be used to rank them and focus on a restricted set thereof. The first proposal was to rank skyline tuples based on the number of tuples that they dominate [8]; albeit very simple to understand, the subsequent literature has criticized this indicator for a number of reasons, including the fact that  
1. it may be applied to non-skyline tuples too and thus the resulting ranking may not prioritize skyline tuples over non-skyline tuples;
2. too many ties would occur in such a ranking; and
3. it is not stable, i.e., it depends on the presence of \"junk\" (i.e., dominated) tuples. Later attempts focused on other properties, including, e.g., the best rank that a tuple might have in any ranking obtainable by using a ranking query with a _linear_ scoring function (i.e., the most common and possibly the only type of scoring function adopted in practice) [36]. More recently, with the intention of exposing the inherent limitations of linear scoring functions, the authors of [20] introduced a number of novel indicators to measure both the \"robustness\" of a skyline tuple and the \"difficulty\" in retrieving it with a top-\(k\) query. The indicators measuring difficulty are typically based on the construction of the _convex hull_ of a dataset, whose parallel computation has been studied extensively [37; 38; 39]. Convex hull-based indicators include the mentioned best rank and the so-called _concavity degree_, i.e., the amount of non-linearity required in the scoring function for a tuple to become part of the top-\(k\) results of a query.