# Ranking methods for skyline queries

Mickaël Martin Nevot, Lotfi Lakhal

► To cite this version:

Mickaël Martin Nevot, Lotfi Lakhal. Ranking methods for skyline queries. Knowledge and Information Systems (KAIS), 2026, 68, pp.78. 10.1007/s10115-026-02684-7. hal-05513986

HAL Id: hal-05513986

https://hal.science/hal-05513986v1

Submitted on 17 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Ranking Methods for Skyline Queries*

Mickaël Martin Nevot¹* and Lotfi Lakhal¹*

¹* Aix-Marseille Université, 52 AVENUE ESCADRILLE NORMANDIE
NIEMEN, 13397, Marseille Cedex 20, FRANCE.

*Corresponding author(s). E-mail(s): mickael.martin-nevot@univ-amu.fr; lotfi.lakhal@univ-amu.fr;

## Abstract

Multi-criteria decision analysis in databases has been actively studied, especially through the Skyline operator. Yet, few approaches offer a relevant comparison of Pareto optimal, or Skyline, points for high cardinality result sets. We propose to improve the dp-idp method, inspired by tf-idf, a recent approach computing a score for each Skyline point, by introducing the concept of dominance hierarchy. As dp-idp lacks efficiency and does not ensure a distinctive rank, we introduce the RankSky method, the adaptation of Google's well-known PageRank solution, using a square stochastic matrix, a teleportation matrix, a damping factor, and then a row score eigenvector and the IPL algorithm. For the same reasons as RankSky, and also to offer directly embeddable in DBMS solution, we establish the TOPSIS based CoSky method, derived from both information research and multi-criteria analysis. CoSky automatically ponderates normalized attributes using the Gini index, then computes a score using Salton's cosine toward an ideal point. By coupling multilevel Skyline to dp-idp, RankSky or CoSky, we introduce DeepSky. Implementations of dp-idp, RankSky and CoSky are evaluated experimentally.

**Keywords:** Multiple-criteria decision analysis, Skyline, Information retrieval, Ranking, PageRank

## 1 Introduction

<footnote>*This manuscript is currently under review for possible publication in Knowledge and Information Systems (KAIS).</footnote>
The Skyline operator ([1]), formerly Pareto set and maximal vectors ([2]), is critical in multi-criteria analysis and has been widely studied. Its main issues with the dataset are, on the one hand, high cardinality and, on the other hand, low correlation. In these cases, it is often hard to extract significant information since more Skyline points often lead to less differences between them. Efficient ranking overcomes that, but few such approaches have been proposed.

Some ranking techniques have been proposed, dp-idp is one of the most recent approaches.

In this paper, we first propose improving the dp-idp method using dominance hierarchy to perfect score computation of Skyline points, then we define both the RankSky method, which is an adaptation of Google's well-known PageRank solution and the IPL algorithm, and the CoSky method ([3]), to rank efficiently skyline's points ignoring dominance, before presenting DeepSky algorithm, a multilevel Skyline algorithm using CoSky to rank the top-k Skyline points. Finally, implementations of dp-idp and CoSky are presented with experimental evaluation.

## 2 Use case

In this paper, we introduce an example applied to Pokémon Showdown!<fnref n="1" />, and its Pokémon example relation (cf. table 1).

<table><caption>Table 1 Pokémon relation</caption><thead><tr><th>RowId</th><th>Player<sup>a</sup></th><th>Opponent<sup>b</sup></th><th>Rarity<sup>c</sup></th><th>Duration<sup>d</sup></th><th>Win<sup>e</sup></th></tr></thead><tbody><tr><td>1</td><td>121, 113, 103</td><td>121, 113, 121</td><td>5</td><td>20</td><td>70</td></tr><tr><td>2</td><td>065, 103, 065</td><td>065, 143, 065</td><td>4</td><td>60</td><td>50</td></tr><tr><td>3</td><td>121, 113, 121</td><td>065, 103, 065</td><td>5</td><td>30</td><td>60</td></tr><tr><td>4</td><td>121, 113, 080</td><td>065, 143, 065</td><td>1</td><td>80</td><td>60</td></tr><tr><td>5</td><td>121, 113, 128</td><td>121, 113, 121</td><td>5</td><td>90</td><td>40</td></tr><tr><td>6</td><td>065, 113, 143</td><td>065, 113, 143</td><td>9</td><td>30</td><td>50</td></tr><tr><td>7</td><td>065, 143, 065</td><td>121, 113, 143</td><td>7</td><td>80</td><td>40</td></tr><tr><td>8</td><td>065, 113, 143</td><td>065, 103, 065</td><td>9</td><td>90</td><td>30</td></tr></tbody></table>

<footnote><sup>a</sup>With official Pokémon numbers: n°065: Alakazam, n°080: Slowbro, n°103: Exeggutor, n°113: Chansey, n°121: Starmie, n°128: Tauros, n°143: Snorlax.</footnote>

<footnote><sup>b</sup>idem supra.</footnote>

<footnote><sup>c</sup>Let *p* be the percentage of drop for the Pokémon sequence (which is the multiplication of the percentage of drop for each sequence's Pokémon), the Rarity score *r* is calculated, on a scale of 0 to 10, as such: if *p* = 1 then *r* = 0, else *r* = $\lceil \max(\frac{(p-1)\times10-(100-e\times0.9)}{e}, 0) \rceil + 1$.</footnote>

<footnote><sup>d</sup>In total number of turns in the fight.</footnote>

<footnote><sup>e</sup>In percentage.</footnote>

<footnote n="1">¹Pokémon Showdown! is a popular Pokémon (Pokémon, possibly because of its Japanese origins, where the plural is not marked on substantives, is, usually, written identically regardless of the plural) open source browser-based online fighting simulator (with millions of monthly visitors).</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1 The Pokémon of the use case<sup>a</sup></figcaption></figure>

**Example 1** The the Pokémon example shown in table 1 is typical of Skyline computation usage. The Player attribute is the player's Pokémon sequence, and Opponent, the opponent's one. Criteria determining the "best Pokémon apparition order in a fight" are the player's Pokémon sequence Rarity, the fight Duration (in rounds) and the player's Pokémon sequence Win rate against the opponent's sequence. For our example, only sequences of three Pokémon are retained, both for the player or the opponent, and to simplify their representation usage we call Pokémon using their number and then substitute a letter for the whole sequence. Thus, the list 121, 113, 128 corresponds to the three Pokémon sequence Starmie, Chansey and Tauros. For convenience, we round Duration and Win to the nearest five.

# 3 Preliminary Definitions

## 3.1 Preference and dominance

Let $r$ be a relation with attributes $A_1, \dots, A_n$. A Skyline preference on $A_j$ is one of the two following expressions: $Pref(A_i) = \text{MIN}$, or $Pref(A_i) = \text{MAX}$. Let $t$ and $t'$ be two tuples of $r$. We consider $t$ dominate $t'$ (noted $t \prec_d t'$) if and only if $t[A_1] \le t'[A_1], \dots, t[A_n] \le t'[A_n]$ and $\exists j \in [1..n] : t[A_j] < t'[A_j]$ with:

$$ (\leq_d, \prec_d) = \begin{cases} (\leq, <) \equiv Pref(A_j) = \text{MIN} \\ (\geq, >) \equiv Pref(A_j) = \text{MAX} \end{cases} \quad (1) $$

**Example 2** In the Pokémon example shown in table 1, Rarity and Duration are criteria to be minimized, while Win is to be maximized (considering that Skyline preferences are mixed). Thus, the tuple of RowId 1 dominates all others ones considering both Duration and Win criteria (i.e., the sequence 121, 113, 103 versus the sequence 121, 113, 121 has the shortest fight, lasting 20 rounds, and this is also the most frequently winning Pokémon sequence with a 70% win rate), whereas the tuple of RowId 4 dominates all others ones considering only the Rarity criterion (i.e., the sequence containing least rare Pokémon is 121, 113, 080, regardless of the rarity of the sequence 065, 143, 065), and the tuple of RowId 2 does not dominate any other tuple considering any criterion.

## 3.2 Skyline operator

A SQL syntax for the Skyline operator ([$1$]) has been proposed.

<footnote><sup>a</sup>From left to right: Alakazam (n°065), Slowbro (n°080), Exeggutor (n°103), Chansey (n°113), Starmie (n°121), Tauros (n°128), Snorlax (n°143); illustration of Pokémon FireRed Version and LeafGreen on Poképédia (https://www.pokepedia.fr/).</footnote>
In our example, the SQL query using the Skyline operator is:

<table><tr><td>01</td><td>SELECT *</td></tr><tr><td>02</td><td>FROM Pokémon</td></tr><tr><td>03</td><td>SKYLINE OF Rarity MIN, Duration MIN, Win MAX</td></tr></table>

And, the associated query without the Skyline operator is as follows:

<table><tr><td>01</td><td>SELECT *</td></tr><tr><td>02</td><td>FROM Pokémon AS P1</td></tr><tr><td>03</td><td>WHERE NOT EXISTS (<br/> 04 SELECT *<br/> 05 FROM Pokémon AS P2<br/> 06 WHERE (P2.Rarity <= P1.Rarity<br/> 07 AND P2apiapi Duration <= P1apiapi Duration<br/> 08 AND P2apiapi Win >= P1apiapi Win)<br/> 09 AND (P2.Rarity < P1.Rarity<br/> 10 OR P2apiapi Duration < P1apiapi Duration<br/> 11 OR P2apiapi Win > P1apiapi Win));</td></tr></table>

In a Pareto dominance representation context, we call point belonging to a Skyline, or Skyline point, or Pareto optimal point (belonging to Pareto front), sp, each of these tuples, whose set forms a Skyline S.

*Example 3* In our example, the Skyline is composed of tuples of RowId 1: (1,...,5,20,70), 2: (2,...,4,60,50) and 4: (4,...,1,80,60). It is the Pokémon sequence set as good as any, or best, regarding all the considered dimension criteria (Rarity, Duration and Win) and best for at least one.

# 4 Skyline ranking

Many research have been dedicated to Skyline ranking. A metric called Skyline frequency is proposed to order Skyline by prioritizing points with high skyline frequency ([4]). This method works for a large number of dimensions and experimentation shows a good algorithm efficiency.

Top-k queries ([5]) can be used as an alternative to Skyline queries. Another method is, using user defined regions, to look for regions dominating all the others ([6]). A Skyline ranking approach for a Skycube ([7]) focused on the most informational Skyline points has been proposed ([8]). This method captures dominance relationships between Skyline points belonging to different subspaces. A new operator has also been introduced to find the most desirable skyline objects, or MDSO ([9]).

## 4.1 dp-idp method

dp-idp (for dominance power and inverse dominance power) is inspired by the weighting scheme tf-idf (for term frequency-inverse document frequency) use in Information research, attributing to a *t* term a weight in the *d* document. The idea is not to determine the occurrence count of each *t* query term in *d*, but instead the tf-idf weight of each term in *d*. The aim is to find important keywords in a document corpus. In the Skyline context, dominated points have different impact on Skyline points. Thus,
their contribution depend on local characteristics corresponding to Skyline points and global characteristics corresponding to the whole Skyline. Thus, dp-idp is build on dominance relation. More specifically, we find the layer of minima<fnref n="2" /> $lm(p, sp)$ where the dominated point $p$ falls in, with respect to sp. The dominance of a point is inversely proportional to the number of points that dominate it. (|[10|], i.e.:

$$dp(p, sp) = \frac{1}{lm(p, sp)} \qquad (2)$$

*Example 4* In the pokémon example shown in table 1, for tuples of RowId 1 and 3, we have $lm(3, 1) = 2$ and $dp(3, 1) = \frac{1}{lm(3, 1)} = \frac{1}{2}$.

dp-idp focuses on dominated points' relative positions to differentiate them by promoting less dominated points: e.g. let sp be a Skyline point, if sp $<$$_d p_1$, sp $<$$_d p_2$ and neither p_1 nor p_2 dominate each other, they are said similar in regard to sp. Whereas, if p_1 $<$$_d p_2$, then score(p_1) > score(p_2), and consequently p_1 has a great significance. A p $\in r \setminus S$ point's idp corresponds to the count of Skyline points dominating p. The less frequently a p point appears in a Skyline's dominated points set, the more it is significant:

$$idp(p) = \log \frac{|S|}{|\{sp \in S : sp \prec_d p\}|} \qquad (3)$$

In order to compute a p dominated point's value dp, its relative position regarding a Skyline point sp is essential. Therefore, a given dominated point can participate differently to several Skyline points. Thus, it is mandatory to compute the layer of minima $lm(p, sp)$ where p, dominated by sp, belongs. p's dominance power is then given by the inverse of the layer where it lies. Score(sp) measuring the significance of a Skyline point sp is defined as follows:

$$Score(sp) = \sum_{p:sp \prec_d p} dp(p, sp) \cdot idp(p) \qquad (4)$$

A baseline's steps to order a Skyline using dp-idp are:

* computing Skyline points sp' layers of minima;

* updating Score(sp) with, for each p point in each layer of minima $lm(p, sp)$, the count of points dominating p;

* ranking Skyline points using these computations.

Unfortunately, this approach is computationally expensive, due to repeated evaluations. It also computes the score of all skyline points, despite any interest in the Top-k results. Finally, it lacks any notion of progressiveness, as the whole Skyline have to be ranked first (|[10|]).

<footnote n="2">²The term "layer of maxima" is more common in the literature. Here, however, the term "layer of minima" is preferred because small values are assumed to be preferable. It is defined by all minimal points in a given set. It is the first layer, or frontier, of non dominating points in the multidimensional space.</footnote>
For these reasons, a more efficient alternative approach, SkyIR, has been proposed ([10]). The algorithm is submitted with different priority schemes (Round-robin, pending or Upper Bound). The most efficient configuration is usually the UBS one, named SkyIR-UBS.

SkyIR-UBS' generation of all layers of minima computations induced complexity is its main issue. We propose to perfect this approach by considering, for each Skyline point, only its closest dominated points, and none of its "indirectly" dominated ones. In this fashion, all $lm(p, sp)$ are composed by a sp and the chain of directly dominated points from sp to p.

## 4.2 dp-idp improvement

The dominance relationship can be seen as a hierarchical sort. In other words, a Skyline point has a hierarchical position over its dominated points. This motivated us to correlate the dominance relationship seen earlier with a graph called dominance hierarchy. Using a dominance hierarchy in dp-idp accelerates layers of minima computations, the graph being pruned of all useless edges, and therefore improves its efficiency. Our proposed graph is acyclic and directed, portraying a representation of a partially sorted set. An acyclic directed graph offers a topological order that can be a great representation for a Skyline point sp's hierarchy over its dominated points.

**Definition 1** (Dominance hierarchy) Let $D$ be a points set and $\prec_d$ be a dominance order, therefore the dominance hierarchy (DH) is the ordered set $(D, \prec_d)$'s vertex cover.

*Example 5* Figure 2 portrays a dominance hierarchy with Skyline point sp as its entry node. The dominance order is illustrated by edges between sp and its dominated points ($p_1, p_2, p_3$ and $p_4$).

<figure><img src="image_3.png" /><figcaption>Fig. 2 Dominance hierarchy example</figcaption></figure>

We consider the layer of minima $lm(p, sp)$ as the minimal path's summits count between sp and p in the dominance hierarchy.
*Example 6* To compute the layer of minima $lm(p_3, sp)$, on the figure 2, we see two paths from sp to $p_3$:

1. First path: $sp \to p_1 \to p_2 \to p_3$.

2. Second path: $sp \to p_4 \to p_3$.

The first path crosses four summits while the second only takes three, therefore the minimal path from sp to $p_3$ is the second and $lm(p_3, sp) = 3$.

<figure><img src="image_4.png" /><figcaption>Fig. 3 Example's dominance hierarchy graph</figcaption></figure>

*Example 7* Considering again the *Pokémon* relation (cf. table 1), the dominance hierarchy graph portraying dominance relationships between Skyline points and dominated points is given by figure 3 ($I^+$ being the ideal theoretical point, or abstract, dominating all Skyline points, and points are represented by their *RowId*).

To compute each Skyline point's score, we use the formula 4. Thus, Skyline points' sorting in descending order is either 1, 2, 4, or 1, 4, 2. Intuitively, without taking formula 4 into account, one can see from figure 3 that from point 1, we can reach five points via some path, while from points 2 and 4, we can reach only three points in both cases. This is why point 1 is more important than points 2 and 4 and why points 2 and 4 are equally important.

In computation formula of idp, each point dominated by every Skyline points will have a 0 score. These points do not alter the Skyline ranking as they contribute equally to all Skyline points ([10]).

Based on our results (cf. table 2), we show the failure of dp-idp method to always distinguish two Skyline points as with values of *RowId* 2 and 4.

### 4.2.1 Improved algorithm
<table><caption>**Table 2** Improved dp-idp method score computation</caption><thead><tr><th>RowId of sp</th><th>RowId of p</th><th>lm(p, sp)</th><th>Score(sp)</th></tr></thead><tbody><tr><td rowspan="5">1</td><td>3</td><td>lm(3, 1) = 2</td><td rowspan="5">0.398</td></tr><tr><td>5</td><td>lm(5, 1) = 3</td></tr><tr><td>6</td><td>lm(6, 1) = 3</td></tr><tr><td>7</td><td>lm(7, 1) = 3</td></tr><tr><td>8</td><td>lm(8, 1) = 4</td></tr><tr><td rowspan="3">2</td><td>5</td><td>lm(5, 2) = 2</td><td rowspan="3">0</td></tr><tr><td>7</td><td>lm(7, 2) = 2</td></tr><tr><td>8</td><td>lm(8, 2) = 3</td></tr><tr><td rowspan="3">4</td><td>5</td><td>lm(5, 4) = 2</td><td rowspan="3">0</td></tr><tr><td>7</td><td>lm(7, 4) = 2</td></tr><tr><td>8</td><td>lm(8, 4) = 3</td></tr></tbody></table>

dp-idp algorithm with dominance hierarchy is composed of four parts: dominanceMatrix, coverageGraph, lm and score<sub>dp-idp</sub>. It is described in algorithm 1.

**Algorithm 1** dp-idp with dominance hierarchy

```pascal
Require:
    r relation.

Ensure:
    The dp-idp score table score.

    m<sub>d</sub>, S<sub>D+lm</sub> := dominanceMatrix(r);
    m<sub>d</sub>, S<sub>D+lm</sub>, S<sub>d</sub>C, idpC :=
        coverageGraph(m<sub>d</sub>, S<sub>D+lm</sub>);
    S<sub>D+lm</sub> := lm(m<sub>d</sub>, S<sub>D+lm</sub>, S<sub>d</sub>C); return score<sub>dp-idp</sub>(S<sub>D+lm</sub>, idpC);
```

▷ Calling four algorithm parts

*Example 8* The table 3 portrays the *Pokémon* relation which, for commodity reasons, carries no attribute or details, only tuples' *RowId*.

<table><caption>**Table 3** The simplified *Pokémon* relation</caption><thead><tr><th>RowId</th><th>Rarity</th><th>Duration</th><th>Win</th></tr></thead><tbody><tr><td>1</td><td>5</td><td>20</td><td>70</td></tr><tr><td>2</td><td>4</td><td>60</td><td>50</td></tr><tr><td>3</td><td>5</td><td>30</td><td>60</td></tr><tr><td>4</td><td>1</td><td>80</td><td>60</td></tr><tr><td>5</td><td>5</td><td>90</td><td>40</td></tr><tr><td>6</td><td>9</td><td>30</td><td>50</td></tr><tr><td>7</td><td>7</td><td>80</td><td>40</td></tr><tr><td>8</td><td>9</td><td>90</td><td>30</td></tr></tbody></table>
<caption>**Algorithm 2 dominanceMatrix (O(|r|^2 · |D|))**</caption>

**Require:**
r relation.

**Ensure:**
The dominance square matrix $m_{\prec_d}$.
The dimensionless Skyline intended to receive $lm(sp, p)$ of dominated points $S_{\setminus D+lm}$.
$D := \{d_1, \dots, d_n\}$: r's dimensions set.
$m_{\prec_d}$: an array of $|r|$ arrays of $|r|$ false values
$idpC$: a dimensionless relation of $|r|$ tuples with same RowId as r
**for** i := 0, ..., $|r|-1$ **do**
  **for** j := 0, ..., $|r|-1$ **do**
    if i≠j **then**
      $t_i$: $t_i \in r$, $t_i[RowId] = i$;
      $t_j$: $t_j \in r$, $t_j[RowId] = j$;
      gre := true;
    **for all** $d_k \in D$ **do**
      ▷ Dominance computation
      ▷ Comparator > if $\forall\{d_1, \dots, d_n\} \in D, \text{Pref}(d_k) = \text{MIN}$
      if $t_j[d_k] > t_i[d_k]$ **then**
        gre := false;
        break
      end if
      **end for**
      if gre **then**
        $t'_i$: $t'_i \in S_{\setminus D}, t'_i[RowId] = i$;
      ▷ Adding the edge to the graph
      $m_{\prec_d}[i][j] := true$;
      $S_{\setminus D} := S_{\setminus D} \setminus t'_i$;
      ▷ $t_j \prec_d t_i$
      ▷ $t_i \notin S$
      **end if**
      end if
      **end for**
      $S_{\setminus D+lm}$: a relation of $|r|$ dimensions of $S_{\setminus D+lm}$ tuples (0, ..., 0) with same RowId as $S_{\setminus D+lm}$
      **return** $m_{\prec_d}, S_{\setminus D+lm}$;

**Example 9** With the Pokémon relation (cf. table 3), result of the algorithm 2, the table 4 portrays the dominance matrix $m_{\prec_d}$, in a table representation with RowId both in row and column, and the table 5 portrays the dimensionless Skyline<fnref n="3" /> intended to receive layers of minima $S_{\setminus D+lm}$. However, note that the matrix $m_{\prec_d}$ requires a large amount of memory. With the table 4, the tuple having RowId 6 is dominated both by RowId 1 and by RowId 3. The table 5 presents Skyline tuples' RowId on rows, and relation tuples' RowId on columns.

The algorithm 3, coverageGraph, updates the dominance matrix $m_{\prec_d}$ considering only the coverage graph. The dimensionless Skyline $S_{\setminus D+lm}$ is also updated to receive layers of minima to compute, indicated by 1. The purpose of the algorithm 3 is to remove all transitive dominance relationships from the dominance matrix $m_{\prec_d}$. It is a transitive reduction, not a transitive closure.) To optimize, Skyline points' dominance cardinalities $S_{\prec_d C}$ and cardinalities $idpC$ needed to compute idp are also retrieved during the coverage graph navigation.

**Example 10** Considering again the Pokémon relation (cf. table 3), with the algorithm 3 we have $m_{\prec_d}[5][1] := false$ because of $m_{\prec_d}[3][1] = true$ and $m_{\prec_d}[5][3] = true$.

<footnote n="3">³We call dimensionless Skyline a Skyline without dimensions other than RowId.</footnote>
<table><caption>**Table 4** Dominance matrix $m_{<d}$</caption><thead><tr><th>RowId</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>✓</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>5</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td></td><td></td><td></td><td></td></tr><tr><td>6</td><td>✓</td><td></td><td>✓</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td></td><td></td><td></td></tr><tr><td>8</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td>✓</td><td></td></tr></tbody></table>

<table><caption>**Table 5** Dimensionless Skyline intended to receive $lm S_{\mathcal{D}+lm}$</caption><thead><tr><th>RowId</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>1</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>2</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr><tr><td>4</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td><td>0</td></tr></tbody></table>

**Example 11** With the *Pokémon* relation (cf. table 3), result of the algorithm 2, the table 6 portrays the dominance matrix $m_{<d}$ based on the coverage graph and the table 7 portrays the dimensionless Skyline intended to receive layers of *minima* $S_{\mathcal{D}+lm}$, merged with, on column, Skyline points' dominance cardinalities $S_{<d}C$ and, on row, cardinalities $idpC$ needed to compute idp. We adopt this representation for more practicality and comprehension. With the table 6, we have the dominance hierarchy graph for *Pokémon* Showdown! (cf. figure 3). And, with the table 7, we see (with values 1) all dominances of each Skyline point (whose RowId are on rows). We also see the count of dominated points for each Skyline point in the column $S_{<d}C$, and the count of dominant Skyline points for each relation point (whose RowId are on columns) with the row $idpC$.

<table><caption>**Table 6** $m_{<d}$ based on coverage graph</caption><thead><tr><th>RowId</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>1</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>2</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>3</td><td>✓</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>4</td><td></td><td></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>5</td><td></td><td>✓</td><td>✓</td><td>✓</td><td></td><td></td><td></td><td></td></tr><tr><td>6</td><td></td><td></td><td>✓</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>7</td><td></td><td>✓</td><td>✓</td><td>✓</td><td></td><td></td><td></td><td></td></tr><tr><td>8</td><td></td><td></td><td></td><td></td><td>✓</td><td>✓</td><td>✓</td><td></td></tr></tbody></table>
Algorithm 4 lm (O(|r| · |S|))

Require:

The dominance square matrix $m_{\prec d}$.

The dimensionless Skyline intended to receive $lm(sp, p)$ of dominated points $S_{\setminus D+lm}$.

$S$ points' dominance cardinalities $S_{\prec d}C$.

Ensure:

The $S$ Skyline with layers $lm(sp, p)$ of dominated points, $S_{lm}$.

for all $t \in S_{\setminus D+lm}$ do

$i := t[RowId];$

$layer := i$

$depth := 2$

while $S_{\prec d}C[i] > 0$ do

$layer_{+1} := layer$

for $j = 0, \dots, |m_{\prec d}| - 1$ do

if $m_{\prec d}[j][layer] \land t[j] > 0$ then

if $t[j] = 1 \lor t[j] \neq 1 \land t[j] > depth$ then

▷ Adjusting $lm(t, t_j), t_j \in r$ depth

$t[j] := t[j] + depth;$

end if

$S_{\prec d}C[i] := S_{\prec d}C[i] - 1;$

▷ Dominance handled

$layer_{+1} := j$

if $S_{\prec d}C[i] = 0$ then

▷ Processing of Skyline point stops when all dominances are handled

break

end if

end if

$depth := depth + 1$

if $layer_{+1} = layer$ then

break

▷ No more layer to handle

end if

$layer := layer_{+1}$

end for

end while

end for return $S_{\setminus D+lm}$;

<caption>Table 8 Dimensionless Skyline with $lm$</caption>

$S_{\setminus D+lm}$

<table><thead><tr><th>RowId</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><th>1</th><td>0</td><td>0</td><td>2</td><td>0</td><td>3</td><td>3</td><td>3</td><td>4</td></tr><tr><th>2</th><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>3</td></tr><tr><th>4</th><td>0</td><td>0</td><td>0</td><td>0</td><td>2</td><td>0</td><td>2</td><td>3</td></tr></tbody></table>

The algorithm 5, $score_{dp-idp}$, computes Skyline points scores using the dp-idp method. To this end, it requires layers of *minima* stored in the dimensionless Skyline $S_{\setminus D+lm}$, useful for dp computation, and also, for each relation point, the count *idpC* of Skyline points dominating it, useful for idp computation.

*Example 13* With the *Pokémon* relation (cf. table 3), result of the algorithm 5, the table 9 portrays respective scores of Skyline tuples' *RowId* 1, 2 and 4.
**Algorithm 5** score<sub>dp-idp</sub> (O(|S| · |D|))

**Require:**

The dimensionless Skyline with *lm(sp, p)* of dominated points *S*<sub>\D+lm</sub>.
S points' dominance cardinalities *S*<sub>\dC</sub>.

**Ensure:**

The array of dp-idp scores, *score*.

*score*: an associative array of |S<sub>\D+lm</sub>| 0

for all t ∈ S<sub>\D+lm</sub> do

i := t[RowId];

for j = 0, ..., |t| - 1 do

if t[j] > 0 then

score[i] := score[i] + 1/t[j] × log(|S<sub>\D+lm</sub>|/idpC[j]);

▷ cf. formula 4

end if

end for

end forreturn *score*;

<table><caption>**Table 9** Improved dp-idp score table</caption><thead><tr><th>RowId</th><th>1</th><th>2</th><th>4</th></tr></thead><tbody><tr><th>score</th><td>0.398</td><td>0</td><td>0</td></tr></tbody></table>

## 4.3 Preparation and comments for methods on vectorial model

### 4.3.1 Conversion of Skyline preferences

Let *r* be a relation composed of attributes *A*<sub>1</sub>, ..., *A*<sub>*m*</sub>. The conversion from *Pref*(*A*<sub>*i*</sub>) = *MIN* to *Pref*(*A*<sub>*i*</sub>) = *MAX*, or its reciprocal, is difficult in ordering schemas based on vectorial model like RankSky with matrix calculation or CoSky with Salton cosine. Inversion of Skyline attribute's values is therefore preferable to complement operation (and to a conversion from minimum to maximum or from maximum to minimum).

Typically, complement values computation formula used is $\forall t \in r, t[A'_i] = \bigvee A_i - t[A_i]$ where $\bigvee A_i$ is the *supremum* of $A_i$, a theoretical value high enough to ensure each converted value remains positive and interpretable. $\bigvee A_i$ can be either the $A_i$ attribute's current maximal value (*optimum*) or its highest possible value (*maximum*). An alternative approach will be to use $\forall t \in r, t[A'_i] = \bigwedge A_i + \bigvee A_i - t[A_i]$ where $\bigwedge A_i$ is $A_i$'s *infimum*. With this approach, *infimum* and *supremum* are, most of the time, respectively the minimum and maximum.

Value inversion is less problematic, mainly for strictly positive values. This method is indifferent to bounds' values, thus computing the *supremum* is irrelevant, and proportions are preserved.

However, even then this is not a perfect conversion due to data dispersion (range, variance, mean absolute deviation, sum, etc.).

*Example 14* With *Pokémon* relation (cf. table 1), to convert the highest possible *Win* rate to the lowest *Win*<sup>-1</sup> rate (or *Loss*), we can invert corresponding values. This produces table 18,
where, for convenience reasons, no attribute or comment are left, only tuples' RowId. However, even though dominance relations between tuples are preserved after transformation, Skyline points attributes values sums (for RowId 1, 2 and 4), respectively $Σ = 160$ and $Σ = 9/140 ≈ 0,0643$ are different. In this case, most normalizations, such as CoSky sum one, give different results when $Pref(Win) = MAX$ or $Pref(Win^{-1}) = MIN$.

### 4.3.2 Unification of Skyline preferences

In vector space model context as with matrix calculation, like in RankSky, or Salton cosine, like in CoSky, we must have comparable values, and therefore identical Skyline preferences. Indeed, in the case of vectors or matrix calculation, all preferences must be set to MAX. Also, for Salton cosine to give a significative similarity measure, it is mandatory for vectors' magnitudes to be on comparable scales and to have similar units.

This way, we can compute either a "mimimum ideal" score or a "maximum ideal" score, even though we recommend, for best precision and quickest computation to unify Skyline preferences selecting the most frequent one, except when a specific unification is required as with PageRank.

Skyline preferences unification process must be done prior to any computation.

**Example 15** In figure 4, we consider, for convenience, two evaluation criteria having, in the first case, unified Skyline preferences (MIN, MIN), and in the second case, mixed Skyline preferences (MIN, MAX): with MIN preference being X-axis, and MAX preference in y-axis.

Points A, B, C and D are not dominated. Whereas points E, F and G are not on the Pareto front (all colored segments) because they are dominated by other points. A, B, C and D are called efficient, and Pareto-optimal. The theoretical ideal point, or abstract, noted $I+$, with coordinates (30, 30) on the left of figure 4, and with coordinates (30, 80) on the right, dominates all Skyline points.

The Salton cosine respectively for angles $θ$ and $θ'$, each formed by the vector from origin to $I+$ and the vector from origin to $D$, has an approximative value of 0.534 rad on the left of figure 4, and an approximative value of 0.611 rad on the right.

Here, unification has been done using complement conversion (using supremum) instead of inversion, for convenience. Indeed, when values are inverted (with some being lower than 1 whereas other are much higher) representation becomes less readable. Nevertheless, in each case, the problematic remains.

**Example 16** To unify Pokémon relation Skyline preferences (cf. tableau 1), as the MIN preference is initially more frequent than the MAX one, it is preferable to use (MIN, MIN, MIN) by inverting Win attribute's values (becoming $Win^{-1}$ or Loss), as with table 18.

## 4.4 RankSky Method

In this subsection, in order to propose a Skyline ranking solution to differentiate and order dissociated Skyline points, we present the adaptation of Google's well-known PageRank algorithm to ranking Skylines, RankSky (for PageRank Skyline).
<figure><img src="image_5.png" /></figure>

$$ \theta' \approx 0.611 \text{ rad} $$

<figure><img src="image_6.png" /><figcaption>Fig. 4 Pref. (MIN, MIN) / (MIN, MAX)</figcaption></figure>

More than the original version, poor in theoretical basis and presenting a value-based approach ([11]), we will focus on the rigorous linear algebraic framework to understand search engine ranking algorithms, with a particular work on Google's PageRank mathematics, presenting a matrix-based approach ([12]). This method computes a column-stochastic matrix representing transition probabilities associated to Markov chains. The PageRank vector is defined as the principal eigenvector corresponding to the dominant eigenvalue $\lambda = 1$ of this matrix. Also, discussion about the role of the damping factor to ensure irreducibility and aperiodicity, guaranteeing a unique stationary distribution, is also of interest for our study.

RankSky is a multi-step approach not using dominance relation or a time-consuming mathematical function as logarithm<fnref n="4" />.

<footnote n="4">⁴Logarithm is a transcendental function way more costly, partly due to material optimization existing for adding and multiplying, than standard operations.</footnote>
It is regretfully not possible to embed this method in a relational DBMS.

This computation is presented in details in this subsection, and the algorithm 6 is proposed. For each step, we consider $i, j \in \{1, \dots, m\}$ (where $m$ is the Skyline tuple count).

*Example 17* RankSky method can be applied on the *Pokémon* relation (cf. table 10), with unified Skyline preferences (*MAX*, *MAX*, *MAX*). Indeed, for Google's PageRank ranking, it is mandatory to only use the preference *MAX*.

<table><caption>Table 10 *Pokémon*₂ relation</caption><thead><tr><th>RowId</th><th>Rarity<sup>-1</sup></th><th>Duration<sup>-1</sup></th><th>Win</th></tr></thead><tbody><tr><td>1</td><td>1/5</td><td>1/20</td><td>70</td></tr><tr><td>2</td><td>1/4</td><td>1/60</td><td>50</td></tr><tr><td>3</td><td>1/5</td><td>1/30</td><td>60</td></tr><tr><td>4</td><td>1/1</td><td>1/80</td><td>60</td></tr><tr><td>5</td><td>1/5</td><td>1/90</td><td>40</td></tr><tr><td>6</td><td>1/9</td><td>1/30</td><td>50</td></tr><tr><td>7</td><td>1/7</td><td>1/80</td><td>40</td></tr><tr><td>8</td><td>1/9</td><td>1/90</td><td>30</td></tr></tbody></table>

### 4.4.1 Step I: Making a square matrix

In addition to a preference unification configuration step, the first two steps of CoSky method can be applied to let $S$ be, prior to that step, a normalized and ponderated matrix representation of a SkyLine where all criteria have a *MAX* preference.

As RankSky Method is based on Google's well-known PageRank method, it requires a square matrix. We point out that a matrix multiplication of $M$ by its transpose $M^T$ provides a square matrix $A$. Thus we have:

$$ \forall M \in \mathbb{R}^{m \times n}, M^T \in \mathbb{R}^{n \times m} \land M \cdot M^T = \begin{cases} A \in \mathbb{R}^{m \times m}, \forall m \ge n \\ A \in \mathbb{R}^{n \times n}, \forall n \ge m \end{cases} \quad (5) $$

We chose that solution to ensure a square matrix, moreover its computation cost is relatively low.

Let $M$ be a matrix of a Skyline with unified Skyline preferences (*MAX*, ..., *MAX*), and $\top$ the transpose of a matrix operator, thus we have $M^T := \top(M)$ and:

$$ A := M \cdot M^T \quad (6) $$

With $A$ a square matrix.

*Example 18* Here is the matrix $M$ of the Skyline, with unified Skyline preferences (*MAX*, *MAX*, *MAX*), of the *Pokémon* relation.

Here is the Skyline's transpose matrix $M^T$ of the *Pokémon* relation.

Here is the square matrix $A = M \cdot M^T$.
$$M = \begin{pmatrix} 1/5 & 1/20 & 70 \\ 1/4 & 1/60 & 50 \\ 1/1 & 1/80 & 60 \end{pmatrix}$$

$$M^{\tau} = \begin{pmatrix} 1/5 & 1/4 & 1/1 \\ 1/20 & 1/60 & 1/80 \\ 70 & 50 & 60 \end{pmatrix}$$

$$A = M \cdot M^{\tau} \approx \begin{pmatrix} 4900 & 3500 & 4200 \\ 3500 & 2500 & 3000 \\ 4200 & 3000 & 3601 \end{pmatrix}$$

### 4.4.2 Step II: Making stochastic matrix

A matrix $P \in \mathbb{R}^{m \times m}$ is called a row-stochastic matrix, left-stochastic matrix or simply stochastic matrix or Markov matrix<fnref n="5" /> if it satisfies the following conditions, with $\forall (i, j), p_{ij} \in P$, thus we have:

* $p_{ij} \ge 0$

* $\sum_{j=1}^{m} p_{ij} = 1$

Furthermore, as a consequence of Perron-Frobenius theorem, which applies to non-negative matrices, there always exists at least an eigenvector, or characteristic vector, $v \in \mathbb{R}^n$ such that $P \cdot v = v$, i.e., 1 is always an eigenvalue, characteristic value, or characteristic root, $\lambda$ of P.

Moreover, if P is irreducible and aperiodic, then the eigenvalue $\lambda = 1$ is simple (i.e. it has multiplicity one) and there exists a unique, up to scaling, positive eigenvector $v$, called the stationary distribution, such that: $P \cdot v = v$ where $\sum_{i=1}^{n} v_i = 1$.

This property is required by Google's PageRank method. The transition matrix is modified by a teleportation, or damping factor, to guarantee these two properties, thus ensuring the existence and uniqueness of the eigenvector that represents PageRank scores.

Let A be a square matrix, $\forall (i, j), a_{ij} \in A$, thus we have P, a stochastic matrix, defined as follows:

$$p_{ij} = \frac{a_{ij}}{\sum_{i', j'=1}^{m} a_{i'j'}} \quad \forall (i, j), p_{ij} \in P \qquad (7)$$

*Example 19* Here is the stochastic matrix P of A, having each line's sum equal to 1.

### 4.4.3 Step III: Making Google's PageRank skyline matrix

Let A be a square and stochastic matrix representing a Skyline where all criteria have a MAX preference. We compute A using the two previous steps. We can then calculate Google's PageRank skyline matrix G, column-stochastic, irreducible and aperiodic. In

<footnote n="5">⁵Such matrices are named Markov matrix because they are commonly used to represent transition probabilities in Markov chains.</footnote>
$$P \approx \begin{pmatrix} 4900/12600 & 3500/12600 & 4200/12600 \\ 3500/9000 & 2500/9000 & 3000/9000 \\ 4200/10801 & 3000/10801 & 3601/10801 \end{pmatrix}$$

this context, G is considered as a transition matrix associated to Markov chains, in which each line's sum is equal to 1.

As a common practice ([12]), $\alpha = 0.85$ is a relevant damping factor so that, seeking the dominant eigenvector, the algorithm is efficient, i.e., it requires a limited iteration count.

Let P be a stochastic matrix, $\alpha = 0.85$, a damping factor and E a teleportation matrix such as $\forall (i, j), e_{ij} \in E \wedge e_{ij} = 1$, thus we have G, a Google PageRank skyline matrix, defined as follows:

$$G = \alpha \cdot P + \frac{1 - \alpha}{m} \cdot E \qquad (8)$$

*Example 20* Here is the Google's PageRank skyline matrix G with $\alpha = 0.85$.

$$G \approx 0.85 \cdot \begin{pmatrix} 4900/12600 & 3500/12600 & 4200/12600 \\ 3500/9000 & 2500/9000 & 3000/9000 \\ 4200/10801 & 3000/10801 & 3601/10801 \end{pmatrix} + 0.15/3 \cdot \begin{pmatrix} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{pmatrix} \\ \approx \begin{pmatrix} 0.38055071 & 0.28610903 & 0.33334026 \\ 0.38054699 & 0.2861075 & 0.33334551 \\ 0.38052694 & 0.28609908 & 0.33337398 \end{pmatrix}$$

### 4.4.4 Step IV: Score with IPL algorithm

Let G be a Google's PageRank skyline matrix, $\epsilon = 10^{-p}$ the machine epsilon in term of $10^{-p}$, with precision $p$, $V_k = (1/m, \dots, 1/m)$ the row score eigenvector, we iteratively calculate $V_k = V_{k-1} \cdot G$ using IPL (Iterated Power-Like) algorithm until $||V_k||_1 - ||V_{k-1}||_1 < \epsilon$, with $||V_x||_1$ the $l^1$ norm or Manhattan norm of vector $V_x$.

IPL generalizes power iteration, power method, or von Mises iteration, improving convergence and adapting to particular matrix structures. The classical power iteration is a simple method to calculate the dominant eigenvector, corresponding to the largest eigenvalue in magnitude, therefore the maximal value, of a matrix. In RankSky, we modify recurrence formulas, that still preserve the direction of convergence, although not always monotone, toward the dominant eigenvector.

IPL is relevant for matrices multiplications, including large but sparse matrices, like Google's PageRank calculation. The algorithm outputs a one-dimensional matrix, or 1-D matrix, which is the result of a matrix multiplication of a probability vector and a transition matrix.

We do not present the IPL algorithm implementation separately because it is integrated into Algorithm 6.
*Example 21* Here is the score vector $V_k$, which is the one-dimensional matrix, and eigenvector, provided by successive iterations of IPL algorithm on *G*.

$$V_k \approx (0.3805417230797888 \quad 0.2861052759746371 \quad 0.33335300094557424)$$

### 4.4.5 Step V: Sort outcomes

In the last step Skyline points are sorted by descending scores.

*Example 22* The table 17 portrays the *Pokémon* relation's Skyline ranked by RankSky method, with associated scores.

<table><caption>Table 17 Skyline ranking with RankSky</caption><thead><tr><th>RowId</th><th>Rarity</th><th>Duration</th><th>Win<sup>-1</sup></th><th>Score</th></tr></thead><tbody><tr><td>1</td><td>5</td><td>20</td><td>1/70</td><td>0.381</td></tr><tr><td>4</td><td>1</td><td>80</td><td>1/60</td><td>0.333</td></tr><tr><td>2</td><td>4</td><td>60</td><td>1/50</td><td>0.286</td></tr></tbody></table>

### 4.4.6 RankSky Algorithm

The algorithm 6 presents an RankSky Algorithm implementation, with skyline criteria preference unification, to MAX, as the only configuration step.

### 4.4.7 Strengths and limitations

By its very nature, the RankSky method pretty shares the same advantages and inconveniences as the well-known PageRank method.

Thus, RankSky captures global importance. It considers not only how many associations a point has, but also the importance of those linking to it. RankSky propagates influence, meaning a point is important if important points have a path to it. Unlike naive ranking, this method is resistant to simple manipulation because it is harder to exploit. It considers which points are associated, not just how many. RankSky is scalable for both sparse and large datasets and uses efficient iterative computation. Skyline points without outgoing edges, or dangling points, are still handled in a principled way using teleportation.

However, for the same reason, the RankSky method is also insensitive to content or context as it only considers the data structure and not the content of the Skyline points or user intent. Therefore, a high-ranked point may be irrelevant to a specific query or topic. This method is also a slow-to-update method that is computationally intensive, especially for very large datasets. It is not ideal for frequently changing needs unless they are optimized or approximated. In a shifting environment, the method presents
biases toward older or regarded as important Skyline points. These points dominate the ranking, which can lead to bias against new points or the overlooking of isolated but high-quality points.

Sure enough, this solution requires careful parameter tuning. Indeed, the damping factor, which is usually set to 0.85, affects the convergence and fairness of the ranking. Thus, poor tuning can impact outcomes or convergence speed.

The RankSky method could be improved by integrating a personalized PageRank variant to propose customization that provides no longer just a global ranking, even if this approach is more complex and expensive and must therefore be reserved for specific uses.

## 4.5 CoSky Method

In order to propose an alternative Skyline ranking solution to differentiate and order dissociated Skyline points, we now present the CoSky method. CoSky (for cosine Sky-line) is also a multi-step approach not using dominance relation, logarithm<fnref n="6" /> and matrix calculation. To our knowledge, it is the first TOPSIS method<fnref n="7" /> ([13], [14]) applied to this type of ranking. TOPSIS is based on a vectorial normalization, a weighting computation for each attribute, and a score computation for each point determined by a geometrical measure of distances between each alternative, represented by a point, and the ideal/anti-ideal solutions. In CoSky, attributes normalization is done with sum, an automatic normalized attributes weighting with Gini index, and the score with Salton cosine of the angle between a Skyline point and the ideal point.

This computation is presented in details in this subsection. For each step, we consider $i \in \{1, ..., m\}$ and $j \in \{1, ..., n\}$ (where m is the tuple count and n the attribute count).

*Example 23* CoSky method can be applied on the *Pokémon* relation (cf. table 18), with unified Skyline preferences (*MIN*, *MIN*, *MIN*).

<table><caption>Table 18 *Pokémon* relation</caption><thead><tr><td>RowId</td><td>Rarity</td><td>Duration</td><td>Win<sup>-1</sup></td></tr></thead><tbody><tr><td>1</td><td>5</td><td>20</td><td>1/70</td></tr><tr><td>2</td><td>4</td><td>60</td><td>1/50</td></tr><tr><td>3</td><td>5</td><td>30</td><td>1/60</td></tr><tr><td>4</td><td>1</td><td>80</td><td>1/60</td></tr><tr><td>5</td><td>5</td><td>90</td><td>1/40</td></tr><tr><td>6</td><td>9</td><td>30</td><td>1/50</td></tr><tr><td>7</td><td>7</td><td>80</td><td>1/40</td></tr><tr><td>8</td><td>9</td><td>90</td><td>1/30</td></tr></tbody></table>

<footnote n="6">⁶Most programming mathematical libraries implement, for the cosine function, an angle reduction follows by a fast series expansion like Taylor's, and for the logarithmic function, a more involved process with more steps and conditionals like an extraction of the exponent and mantissa from the floating-point representation follows by a computation of the logarithm of the mantissa via interpolation or polynomial approximation, once more completed by a result fusion.</footnote>

<footnote n="7">⁷TOPSIS for Technic for Order Preference by Similarity to Ideal Solution, is a method for ranking alternatives on a given order based on beneficial or unfavorable criteria.</footnote>
### 4.5.1 Step I: Normalization by sum

Skyline is normalized by using sum. This method assures all normalized values are between -1 and 1, with a sum 1 by dividing each value by the sum of all values. It is well suited when data relative scale is more important than their absolute values, and when proportion to the total are relevant, can remove anomalies, notably coming from different measure units or scales, while ensuring measurability and comparability of attributes. Let $x$ be a value and $\Sigma x$ the sum of all values, then $x$'s normalized value $x'$ is:

$$x' = \frac{x}{\Sigma x}$$

It is advised to prior transpose all values to natural real numbers. Moreover, this way every attribute value of every Skyline point is converted into a 0 to 1 value.

Let $S_N$ be a Skyline normalized points set, or normalized Skyline, and $u_i = (u_i[A_1], u_i[A_2], \dots, u_i[A_n]) \in S_N$ a tuple, thus we have:

$$u_i[A_j] = \frac{t_i[A_j]}{\sum_{i'=1}^{m} t_{i'}[A_j]}, \forall t_i \in S \quad (9)$$

Beware, this method implies a divide by 0 risk, on attributes non normalized values' sum: $\sum_{i'=1}^{m} t_{i'}[A_j] \neq 0$.

*Example 24* The table 19 portrays the Pokémon relation's Skyline normalized by sum.

<table><caption>**Table 19** Pokémon relation's Skyline normalized by using sum</caption><thead><tr><th>RowId</th><th>Rarity</th><th>Duration</th><th>Win<sup>-1</sup></th></tr></thead><tbody><tr><td>1</td><td>5/10</td><td>20/160</td><td>1/70 × 2100/107</td></tr><tr><td>2</td><td>4/10</td><td>60/160</td><td>1/50 × 2100/107</td></tr><tr><td>4</td><td>1/10</td><td>80/160</td><td>1/60 × 2100/107</td></tr></tbody></table>

Or, with approximate values:

<table><thead><tr><th>RowId</th><th>Rarity</th><th>Duration</th><th>Win<sup>-1</sup></th></tr></thead><tbody><tr><td>1</td><td>0.5</td><td>0.125</td><td>0.280</td></tr><tr><td>2</td><td>0.4</td><td>0.125</td><td>0.393</td></tr><tr><td>4</td><td>0.1</td><td>0.5</td><td>0.327</td></tr></tbody></table>

### 4.5.2 Step II: Gini index-based weighting

To strictly distinguish Skyline points, it is essential to set up a discriminating measure and several have been proposed in the literature. An entropy based method was used for multi criteria problems ([15], [16]). This method is well suited for Skylines, where decision making requires a simple comparison of attributes values. However, as entropy computation needs a time-consuming logarithm function, this method is inefficient.
We would rather set up another measure, the Gini index<fnref n="8" />, while being without logarithm, it is faster to compute than the entropy method. In the presented method, the Gini index is used to derive the attributes' weight in order to establish a divergence degree of attributes' values. Gini index $A_j$, Gini($A_j$), is calculated by the following equation:

$$Gini(A_j) = 1 - \sum_{i=1}^{m} u_i [A_j]^2 \qquad (10)$$

We call W the attribute $A_j$'s weight. ($W(A_1), W(A_2), \dots, W(A_m)$) can be specified by the decision-maker so that $\sum(W(A_1), W(A_2), \dots, W(A_m)) = 1$. The attribute's weight is defined as follows:

$$W(A_j) = \frac{Gini(A_j)}{\sum_{j'=1}^{n} Gini(A_{j'})} \qquad (11)$$

Let $S_P$ be a weighted Skyline, or Skyline weighted points set, and $v_i = (v_i[A_1], v_i[A_2], \dots, v_i[A_n]) \in S_P$ a tuple, thus we have:

$$v_i[A_j] = W(A_j) \times u_i[A_j], \forall u_i \in S_N \qquad (12)$$

*Example 25* The table 20 portrays the Pokémon relation's Skyline normalized weighted by Gini's index.

<table><caption>**Table 20** Pokémon relation's Skyline normalized weighted by Gini's index</caption><thead><tr><th>RowId</th><th>Rarity</th><th>Duration</th><th>Win<sup>-1</sup></th></tr></thead><tbody><tr><td>1</td><td>0.158</td><td>0.041</td><td>0.101</td></tr><tr><td>2</td><td>0.126</td><td>0.121</td><td>0.141</td></tr><tr><td>4</td><td>0.032</td><td>0.162</td><td>0.118</td></tr></tbody></table>

### 4.5.3 Step III: Determination of the ideal point

The theoretical, or abstract, ideal point, noted $I^+$, dominating every Skyline points, is a tuple that optimally matches all Skyline preferences.

Thus, with $I^+ = (I^+[A_1], I^+[A_2], \dots, I^+[A_n])$, we have:

$$I^+[A_j] = \begin{cases} \text{MAX}(v_i[A_j]) & \equiv \text{Pref}(A_j) = \text{MAX} \\ \text{MIN}(v_i[A_j]) & \equiv \text{Pref}(A_j) = \text{MIN} \end{cases} \qquad (13)$$

*Example 26* With the Pokémon relation (cf. table 18), the ideal Pokémon sequence in a fight combines conditions on the lowest possible Rarity, on the shortest possible Duration,

<footnote n="8">⁸The Gini index (or coefficient) is a statistical measure used to evaluate outliers variables in a given population. It is mainly used to measure a country's salary inequalities. It spans between 0 (full correlation) and 1 (no correlation), where the higher the index, the greater the inequality</footnote>
and on the lowest possible $Win^{-1}$ rate. The ideal attributes approximate values compute by CoSky method are:

* Rarity: 0.032

* Duration: 0.040

* $Win^{-1}$: 0.101

### 4.5.4 Step IV: Scores with Salton cosine

This step computes a Skyline point's score using Salton cosine<fnref n="9" />. To that end, we compute the cosine of the angle between the ideal point and the Skyline point. The narrower the angle (therefore, the higher the angle's cosine), the more important the Skyline point is.

Let $S_{Score}$ be a set of all Skyline point score, $v_i = (v_i[A_1], v_i[A_2], \dots, v_i[A_n]) \in S_P$ a tuple and $I^+ = (I^+[A_1], I^+[A_2], \dots, I^+[A_n])$ the ideal point, thus we have:

$$s_i = S_c(v_i, I^+) := \cos(\theta) = \frac{v_i \cdot I^+}{||v_i|| \cdot ||I^+||} \quad (14)$$

$$s_i = \frac{\sum_{j=1}^{n} v_i[A_j] \cdot I^+[A_j]}{\sqrt{\sum_{j=1}^{n} v_i[A_j]^2 \cdot \sum_{j=1}^{n} I^+[A_j]^2}}, \forall s_i \in S_{Score} \quad (15)$$

In consequence, $s_i = 1$ if and only if the Skyline point is considered as the most interesting one, and respectively $s_i = 0$ if and only if it is considered as the least interesting.

We can use TOPSIS' similarity principle to compute each Skyline point's score as follows: let $I^-$ be the anti-ideal point then, $\forall v_i \in S_P$, if we consider $I^- = (I^-[A_1], I^-[A_2], \dots, I^-[A_n])$, we have:

$$I^-[A_j] = \begin{cases} \max(v_i[A_j]) & \equiv \text{Pref}(A_j) = \min \\ \min(v_i[A_j]) & \equiv \text{Pref}(A_j) = \max \end{cases} \quad (16)$$

### 4.5.5 Step V: Sort outcomes

In the last step, as for RankSky, Skyline points are sorted by descending scores.

*Example 27* The table 21 portrays the Pokémon relation's Skyline ranked by CoSky method, with associated scores.

CoSky's Salton cosine gives different scores to each Skyline point, like RankSky but unlike dp-idp. Skyline points with RowId 2 and 4 have, with CoSky, different non null scores, despite having a 0 score with dp-idp. In this example, not only are Skyline point with RowId 2 and 4 differentiated, but also the sorting is different than RankSky and dp-idp.

<footnote n="9">⁹Salton cosine, or similarity measure cosine, or similarity cosine, measures, between 0 à 1, the similarity between vectors. A piece of information can be represented by a vector and its value by an angle in a vector space. It is traditionally used by search engines to rank Web pages.</footnote>
<table><caption>Table 21 Skyline ranking with CoSky</caption><thead><tr><td>RowId</td><td>Rarity</td><td>Duration</td><td>Win<sup>-1</sup></td><td>Score</td></tr></thead><tbody><tr><td>2</td><td>4</td><td>60</td><td>1/50</td><td>0.909</td></tr><tr><td>4</td><td>1</td><td>80</td><td>1/60</td><td>0.847</td></tr><tr><td>1</td><td>5</td><td>20</td><td>1/70</td><td>0.774</td></tr></tbody></table>

### 4.5.6 CoSky in SQL

CoSky method is fully integrable into relational database management systems (DBMS), and can be expressed in a SQL query.

*Example 28* CoSky method can be applied using the following SQL query<fnref n="10" />:

```
01 | WITH S AS (
02 | SELECT *
03 | FROM Pokémon
04 | SKYLINE OF Rarity MIN, Duration MIN, Loss MIN
05 | ), SN AS (
06 | SELECT RowId,
07 |     Rarity / TRarity AS NRarity,
08 |     Duration / TDuration AS NDuration,
09 |     Loss / TLoss AS NLoss
10 | FROM S,
11 |     (
12 |         SELECT SUM(Rarity) AS TRarity,
13 |             SUM(Duration) AS TDuration,
14 |             SUM(Loss) AS TLoss FROM S
15 |     ) AS ST
16 | ), SGini AS (
17 | SELECT 1 - SUM(NRarity * NRarity) AS GRarity,
18 |     1 - SUM(NDuration * NDuration) AS GDuration,
19 |     1 - SUM(NLoss * NLoss) AS GLoss
20 | FROM SN
21 | ), SW AS (
22 | SELECT GRarity / (GRarity + GDuration + GLoss) AS WRare,
23 |     GDuration / (GRarity + GDuration + GLoss) AS WDuration,
24 |     GLoss / (GRarity + GDuration + GLoss) AS WLoss
25 | FROM SGini
26 | ), SP AS (
27 | SELECT RowId,
28 |     WRare * NRarity AS PRarity,
29 |     WDuration * NDuration AS PDuration,
30 |     WLoss * NLoss AS PLoss
31 | FROM SN, SW
32 | ), Idéal AS (
33 | SELECT MIN(PRarity) AS IRarity,
34 |     MIN(PDuration) AS IDuration,
35 |     MAX(PLoss) AS ILoss
36 | FROM SP
37 | ), SScore AS (
38 | SELECT RowId,
39 |     (IRarity * PRarity + IDuration * PDuration + ILoss * PLoss) /
40 |     (
41 |         SQRT(PRarity * PRarity +
42 |             PDuration * PDuration +
43 |             PLoss * PLoss) *
44 |         SQRT(IRarity * IRarity +
45 |             IDuration * IDuration +
```

<footnote n="10">¹⁰If the Skyline is composed by only one point, its ranking is useless or shall be done using COALESCE(NULLIF(..., 0), 1) on each query denominator.</footnote>
<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>46</td><td></td><td>ILoss * ILoss)</td></tr><tr><td>47</td><td>)</td><td></td></tr><tr><td>48</td><td>AS Score</td><td></td></tr><tr><td>49</td><td>FROM Idéal, SP</td><td></td></tr><tr><td>50</td><td>)</td><td></td></tr><tr><td>51</td><td>SELECT P RowId AS RowId, Rarity, Duration, Loss, ROUND(Score, 3) AS Score</td><td></td></tr><tr><td>52</td><td>FROM S P</td><td></td></tr><tr><td>53</td><td>INNER JOIN SScore rs ON P RowId = rs RowId</td><td></td></tr><tr><td>54</td><td>ORDER BY Score DESC;</td><td></td></tr></tbody></table>

And, the associated query without the Skyline operator is schematically depicted as follows:

<table><thead><tr><th></th><th></th><th></th></tr></thead><tbody><tr><td>01</td><td>WITH S AS (</td><td></td></tr><tr><td>02</td><td>SELECT *</td><td></td></tr><tr><td>03</td><td>FROM Pokémon AS P1</td><td></td></tr><tr><td>04</td><td>WHERE NOT EXISTS (</td><td></td></tr><tr><td>05</td><td>SELECT *</td><td></td></tr><tr><td>06</td><td>FROM Pokémon AS P2</td><td></td></tr><tr><td>07</td><td>WHERE (P2.Rarity &lt;= P1.Rarity</td><td></td></tr><tr><td>08</td><td>AND P2 Duration &lt;= P1 Duration</td><td></td></tr><tr><td>09</td><td>AND P2.Win &gt;= P1.Win)</td><td></td></tr><tr><td>10</td><td>AND (P2.Rarity &lt; P1.Rarity</td><td></td></tr><tr><td>11</td><td>OR P2 Duration &lt; P1 Duration</td><td></td></tr><tr><td>12</td><td>OR P2.Win &gt; P1.Win))</td><td></td></tr><tr><td>13</td><td>), SN AS (</td><td></td></tr><tr><td>14</td><td>...</td><td></td></tr><tr><td>15</td><td>)</td><td></td></tr><tr><td>16</td><td>...</td><td></td></tr><tr><td>17</td><td>SELECT P RowId AS RowId, Rarity, Duration, Loss, ROUND(Score, 3) AS Score</td><td></td></tr><tr><td>18</td><td>FROM S P</td><td></td></tr><tr><td>19</td><td>INNER JOIN SScore rs ON P RowId = rs RowId</td><td></td></tr><tr><td>20</td><td>ORDER BY Score DESC;</td><td></td></tr></tbody></table>

### 4.5.7 CoSky Algorithm

Sometimes, a code integrable algorithm can be more useful than a relational DBMS integrated one, as it is the case with a high dimensional cardinality, or as part of a library.

To this end, we propose the naive algorithm<fnref n="11" /> 7.

CoSky algorithm does not really compute the Skyline. It is, therefore, needed to use an external solution. Thus, we chose to use branch-and-bound Skyline (BBS) ([(17)]) for its efficiency.

CoSky algorithm is, obviously, close to the CoSky SQL implementation. Method steps are conserved even if, for optimization purpose, their instructions and order can be altered.

For readability purpose, algorithm has been documented using the Pokémon relation example (cf. table 18), with unified Skyline preferences (MIN, MIN, MIN).

<footnote n="11">¹¹CoSky algorithm has been optimized, but without use of data statistics, parallelism, cache management, etc.</footnote>
## 4.6 Strengths and limitations

By its very nature, the CoSky method shares many of the same advantages and inconveniences as the The Salton cosine, backed by a rich body of literature in IR and form the basis for many benchmarks and retrieval models.

Thus, CoSKy measures the angle between vectors, not their magnitude, which allows comparison of Skyline points that may have dimension values with large deviations, but that are comparable in importance. This solution only requires dot products and vector norms, both of which are efficiently computable and scalable to large datasets. For non-negative vectors, the similarity score lies in the range of [0, 1], with 1 indicating identical orientation. These scores are easy to interpret, which makes them useful for analysis and evaluation. CoSky is domain-agnostic and can be applicable wherever data can be represented as vectors.

However, for the same reason, the CoSky method relies on raw vector alignment and does not capture semantic similarity. It assumes a linear vector space structure. In highly sparse vector spaces, the Salton cosine may be undefined or uninformative, especially in the case of Skyline composed by few points. Therefore, in that case, CoSky does not really provide exploitable information. As CoSky lacks a statistical foundation, which makes it less interpretable in probabilistic terms.

## 4.7 Top-k method

For this last method, we use the multilevel Skyline principle ([18]) to find the top-k Skyline points, unordered. A top-k $Q_k$ Skyline query on a relation $r$ computes top-k points, based on $S'$ Skyline preferences. Let $S_0(r)$ be the 0 level points from the multilevel Skyline, or Skyline points, such as $S_0(r) = S$, and $Card(r)$ r's cardinality such as $Card(r) > k$, then:

* if $Card(S_0(r)) > k$: $Q_k$ only returns k points from $S_0(r)$;

* if $Card(S_0(r)) = k$: $Q_k$ returns the whole Skyline (i.e. all points from $S_0(r)$);

* if $Card(S_0(r)) < k$: $S_0(r)$ do not have enough points to compute a valid answer with $Q_k$. A multilevel Skyline approach shall be applied. Thus, not only $S_1(r)$ points from $(r \setminus S_0(r))$ are returned, but also possibly $S_2(r)$ points from $(r \setminus (S_0(r) \cup S_1(r)))$, from $S_3(r)$... as long as the cumulative result count is lower than $k$.

### 4.7.1 DeepSky

The algorithm 8, DeepSky, uses this multilevel principle allied to a skyline ranking solution such as CoSky to find top-k ranked Skyline points. It returns k multilevel Skyline points with k highest scores computed by such a skyline ranking solution.

*Example 29* With pokémon relation (cf. table 18), and $k = 4$, DeepSky algorithm (cf. algorithm 8) returns Skyline points with RowId 1, 4 and 2, those at level 0, and with RowId 3, the only level 1 point.
# 5 Discussion

RankSky is an original method of ranking Skylines, inspired by the widely studied PageRank method. However, it may be more efficient in some cases to adapt the use of IPL to improve the convergence rate of the method when considering the dominant eigenvalue and the spectral ratio.

CoSky is an original method of ranking skylines that uses the flexible, easy-to-compute, and easy-to-interpret Salton cosine method. It is also invariant to vectors' linear transformations (such as values scaling) and is well fitted to compare vectors in high dimension spaces. However, it is weak against null vectors and does not take into account vectors' magnitude, only their direction. Thus, in the rare occasion where a Skyline point vector is overlapping the ideal point vector, with a distinct magnitude, it will be considered, wrongly, as optimal. Likewise, several Skyline points can have the same similarity measure.

We assume an ideal point as optimal on the whole dimension set. We could consider, instead, a closer theoretical point dominating all Skyline points.

The method chosen depends on the context and the meaning the user wants to convey through the ranking. With dp-idp, a point's importance is inversely proportional to the count of Skyline points dominating it, which can be detrimental in some cases, like with a dense cluster of points close to the Pareto front. RanKSky, uses a well-tested ranking method, yet sensitive to the needed Skyline preferences unification, which can contribute to roundoff errors, thus possibly altering ranking Skyline in case of high cardinality. CoSky, in turn, measures distance with an ideal, that always makes sense.

Other Skyline points ranking methods have been proposed in the literature with the same aim to reduce result sets. Among these, we could compare with, even if only experimentally, the method using regret minimisation ([19]).

# 6 Experimental evaluations

The experimental evaluation was performed on an AMD Ryzen 5 5600X 6-Core CPU @ 3.7GHz, with 32GB RAM, powered by Linux. The source code was written in Python 3.8 and interpreted with PyPy 3.10. PyPy is an alternative implementation of the Python programming language, designed to be faster and more efficient in terms of memory consumption than the standard Python implementation CPython. On average, PyPy 3.10 is 4.8 times faster than CPython 3.7. Times shown are in seconds, measured as processor processing time and assuming a default value of 8 ms per page default.

Specifically concerning the evaluation of SkyIR-UBS algorithm, considered datasets have been indexed using R\*-tree aggregation with 4Kb page size. An associated cache with 20 % of the corresponding R-tree's blocks was used with every experiment.

We have generated synthetic sets of data where dimensions are independent composed of 10 to 1 billion tuples for respectively 3, 6 and 9 dimensions coming from the example use case.
## 6.1 Comparison of ranking methods

To compare all methods we used the most efficient dp-idp algorithm, SkyIR-UBS.

Even though, figure 5, portraying different solutions response times, when the dataset cardinality is up to 50000 tuples, for 3 dimensions, declares SkyIR-UBS as the least efficient of all methods. Our proposition, dp-idp with dominance hierarchy, explodes about twice as slow. However, its efficiency is negligible compared to RankSky and CoSky implementations. In the worst case (50000 tuples and 3 dimensions), RankSky implementation, algorithmic and SQL CoSky implementations have respective response times of 1 minute and 46 seconds, 2 minutes and 16 seconds, 0.172 seconds while our dp-idp version and SkyIR-UBS have respective response times of less than 3 hours and more than 6 hours!

In the following evaluations, we dismiss SkyIR-UBS and dp-idp with dominance hierarchy, less efficient than RankSky and CoSky implementations, in order to study higher cardinalities and higher dimensions.

<figure><img src="image_7.png" /><figcaption>Fig. 5 Response time of different solutions</figcaption></figure>
## 6.2 RankSky and CoSky implementations

To compare RankSky and CoSky's implementations, we consider figure 6 with logarithmic scale representation for ordinate axis that, in our humble opinion, provides a more relevant visualization. Evaluation are made for cardinalities up to 200000 tuples with, respectively, 3, 6 and 9 dimensions. In the worst case, response times are approximately 34 minutes, 44 minutes and 1 hour 20 minutes respectively, for RankSky, while they are approximately 38 minutes, 57 minutes and 1 hour 31 minutes respectively, for algorithmic CoSky while they are approximately 1 second, 58 seconds and 7 minutes and 56 seconds respectively, for SQL CoSky. Even though, RankSky and both CoSky propositions are particularly efficient, notably in regards to existing methods. RankSky and algorithmic CoSky are quite similar. The DBMS integrated CoSky method is significantly faster.

<figure><img src="image_8.png" /><figcaption>Fig. 6 CoSky response time SQL query vs Algorithm (3, 6 and 9 attributes)</figcaption></figure>
## 6.3 SQL CoSky

To compare SQL CoSky implementations, we consider figure 7. Evaluation are made for cardinalities up to 2 000 000 tuples with, respectively, 3, 6 and 9 dimensions. In the worst case, response times are approximately about 11.08 seconds for 3 dimensions, about 18 minutes for 6 dimensions and about 4 hours 26 minutes for 9 dimensions. As expected, our SQL CoSky implementation is sensitive to an increase in the number of dimensions, as is the case with any kind of computation in a Skyline context. This problem is known to be difficult for high dimensions even with a RAM model ([4]).

<figure><img src="image_9.png" /><figcaption>Fig. 7 CoSky response time for SQL queries</figcaption></figure>

## 6.4 CoSky with 3 dimensions

To compare CoSky implementations with 3 dimensions, we consider figure 8. Evaluation are made for cardinalities up to 1 billion tuples. In the worst case, response time is a little more than 3 hours.

## 7 Conclusion

In this article, we have presented new efficient Skyline ranking methods.

The first is an improvement of the id-idp method using dominance hierarchy, faster than the original. An algorithmic implementation has been proposed.
<figure><img src="image_10.png" /><figcaption>Fig. 8 CoSky response time forSql query with 3 attributes</figcaption></figure>

The second is the RankSky method, the adaptation of Google's well-known PageRank algorithm, using the IPL algorithm. It is regretfully not possible to embed this method in a relational DBMS, but an algorithmic implementation have been proposed.

The third is the CoSky method, based on both TOPSIS approach, coming from multi-criteria analysis, and the similarity measure Salton cosine, coming from information retrieval. A SQL and an algorithmic implementations have, nevertheless, been proposed.

DeepSky algorithm has been introduced in order to find top-k ranked Skyline points, i.e. with the highest scores, using multilevel Skyline principle associated to a skyline ranking solution such as CoSky, Ransky or dp-idp methods.

Seeing their relevance and performance highlighted during experimental evaluations, we think the exposed methods could be the subject of future work and a future open source algorithmic platform.

## References

[1] Borzsony, S., Kossmann, D., Stocker, K.: The Skyline operator. In: Proceedings 17th International Conference on Data Engineering, pp. 421–430. IEEE Comput. Soc, Heidelberg, Germany (2001). https://doi.org/10.1109/ICDE.2001.914855

[2] Bentley, J.L., Kung, H.T., Schkolnick, M., Thompson, C.D.: On the Average Number of Maxima in a Set of Vectors and Applications. Journal of the ACM
25(4), 536–543 (1978) https://doi.org/10.1145/322092.322095

[3] Martin Nevot, M., Lakhal, L.: Classement d'objets Skylines dans les bases de données. In: 40ème Conférence Sur La Gestion de Données, Orléans, France (2024)

[4] Chan, C.-Y., Jagadish, H.V., Tan, K.-L., Tung, A.K.H., Zhang, Z.: On High Dimensional Skylines. In: Hutchison, D., Kanade, T., Kittler, J., Kleinberg, J.M., Mattern, F., Mitchell, J.C., Naor, M., Nierstrasz, O., Pandu Rangan, C., Steffen, B., Sudan, M., Terzopoulos, D., Tygar, D., Vardi, M.Y., Weikum, G., Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., Boehm, K., Kemper, A., Grust, T., Boehm, C. (eds.) Advances in Database Technology - EDBT 2006, vol. 3896, pp. 478–495. Springer, Berlin, Heidelberg (2006). https://doi.org/10.1007/11687238_30

[5] Yiu, M., Mamoulis, N.: Efficient processing of top-k dominating queries on multi-dimensional data. In: Proceedings of the 33rd International Conference on Very Large Data Bases, University of Vienna, Austria, September 23-27, 2007, pp. 483–494. ACM, Vienna, Austria (2007)

[6] Bartolini, I., Ciaccia, P., Oria, V., Özsu, M.T.: Flexible integration of multimedia sub-queries with qualitative preferences. Multimedia Tools and Applications 33(3), 275–300 (2007) https://doi.org/10.1007/s11042-007-0103-1

[7] Lakhal, L., Nedjar, S., Cicchetti, R.: Multidimensional skyline analysis based on agree concept lattices. Intelligent Data Analysis 21(5), 1245–1265 (2017) https://doi.org/10.3233/IDA-163111

[8] Vlachou, A., Vazirgiannis, M.: Ranking the sky: Discovering the importance of skyline points through subspace dominance relationships. Data & Knowledge Engineering 69(9), 943–964 (2010) https://doi.org/10.1016/j.datak.2010.03.008

[9] Gao, Y., Liu, Q., Chen, L., Chen, G., Li, Q.: Efficient algorithms for finding the most desirable skyline objects. Knowledge-Based Systems 89, 250–264 (2015) https://doi.org/10.1016/j.knosys.2015.07.007

[10] Valkanas, G., Papadopoulos, A.N., Gunopulos, D.: Skyline ranking à la IR. In: Candan, K.S., Amer-Yahia, S., Schweikardt, N., Christophides, V., Leroy, V. (eds.) Proceedings of the Workshops of the EDBT/ICDT 2014 Joint Conference (EDBT/ICDT 2014), Athens, Greece, March 28, 2014. CEUR Workshop Proceedings, vol. 1133, pp. 182–187. CEUR-WS.org, ??? (2014)

[11] Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Libraries Technologies Project (1998)

[12] Langville, A.N., Meyer, C.D.: Google's PageRank and Beyond: The Science of
[13] Lai, Y.-J., Liu, T.-Y., Hwang, C.-L.: TOPSIS for MODM. European Journal of Operational Research 76(3), 486-500 (1994) https://doi.org/10.1016/0377-2217(94)90282-8

[14] Behzadian, M., Khanmohammadi Otaghsara, S., Yazdani, M., Ignatius, J.: A state-of-the-art survey of TOPSIS applications. Expert Systems with Applications 39(17), 13051-13069 (2012) https://doi.org/10.1016/j.eswa.2012.05.056

[15] Huang, J.: Combining entropy weight and TOPSIS method for information system selection. In: 2008 IEEE Conference on Cybernetics and Intelligent Systems, pp. 1281-1284. IEEE, Chengdu, China (2008). https://doi.org/10.1109/ICCIS.2008.4670971

[16] Lotfi, F.H., Fallahnejad, R.: Imprecise Shannon's Entropy and Multi Attribute Decision Making. Entropy 12(1), 53-62 (2010) https://doi.org/10.3390/e12010053

[17] Papadias, D., Tao, Y., Fu, G., Seeger, B.: Progressive skyline computation in database systems. ACM Transactions on Database Systems 30(1), 41-82 (2005) https://doi.org/10.1145/1061318.1061320

[18] Preisinger, T., Endres, M.: Looking for the best, but not too many of them: Multi-level and top-k skylines. International Journal on Advances in Software, 467-480 (2015)

[19] Fabris, V.: Flexible Skylines, Regret Minimization and Skyline Ranking: A Comparison to Know How to Select the Right Approach. arXiv (2022). https://doi.org/10.48550/ARXIV.2201.10179
<caption>Algorithm 6 RankSky (O(|r| log |r| + |S| · |D|^2 + k · |S|^2))</caption>

**Require:**
r relation.
Number of results k.

**Ensure:**
RankSky's ordered score table score.

S: r's Skyline
D: {d₁, ..., dₙ}: r's dimensions set.
M: an array of |S| arrays of |D| 0
M': an array of |D| arrays of |S| 0
A: an array of |S| arrays of |S| 0
P: an array of |S| arrays of |S| 0
E: an array of |S| arrays of |S| 1
G: an array of |S| arrays of |S| 0
α := 0.85;
p := 3;
Vₖ: an array of |S| 1/|S|
Zₖ: an array of |S| 0
||Vₖ||₁: a positive integer
||Zₖ||₁ := 0:
score: an associative array of |D| + 1 0

for all t ∈ S do
  i := t[RowId];
  for all dⱼ ∈ D do
    M[i][dⱼ] := t[dⱼ];
    score[i][dⱼ] := t[dⱼ];
  end for
end for
M' := T(M);
A := M · M';

P = A;
for i := 0, ..., |P| − 1 do
  tot := 0;
  for j := 0, ..., |P| − 1 do
    tot := tot + P[i][j];
  end for
  for j := 0, ..., |P| − 1 do
    P[i][j] := P[i][j]/tot;
  end for
end for

G := α · P + (1 − α)/|P| · E;

ε := 10⁻⁵;
||Zₖ||₁ := 0;
loop
  ||Vₖ||₁ := ||Zₖ||₁;
  Zₖ := Vₖ · G;
  ||Zₖ||₁ := 0;
  for i := 0, ..., |Zₖ| − 1 do
    ||Zₖ||₁ := ||Zₖ||₁ + |Zₖ[i]|;
  end for
  Vₖ := Zₖ/||Zₖ||₁;
  if ||Zₖ||₁ − ||Vₖ||₁ < ε then
    break
  end if
end loop

for all t ∈ Vₖ do
  i := t[RowId];
  score[i][|D|] := Vₖ[i];
end for
score := reverseQuickSort(score, 0, |S| − 1);

▷ score descending sort on score[i][|D|] values, with ∀t ∈ S, i := t[RowId] return score

▷ Computed with BBS

▷ The transpose matrix
▷ The square matrix
▷ The stochastic matrix
▷ The teleportation matrix
▷ The Google matrix
▷ The α factor
▷ The calculation precision

▷ Step I: Making M a square matrix

▷ With T(M): M ∈ ℝ<sup>m×n</sup> → M' ∈ ℝ<sup>n×m</sup>
▷ Step II: Making A a stochastic matrix

▷ Step III: Making Google's PageRank skyline matrix
▷ Step IV: Score with IPL (Iterated Power-Like) algorithm
▷ The machine epsilon in term of 10⁻⁵, with precision p

▷ l¹ norm or Manhattan norm: ||Zₖ||₁ = Σ<sub>i=1</sub><sup>n</sup> |Zₖ<sub>i</sub>|

▷ Step V: Sort outcomes
Algorithm 7 CoSky (O(|S|·|D| + |r|·log(|r|)))

Require:

r relation.

Ensure:

CoSky's ordered score table score.

S: r's Skyline
D: {d₁, ..., dₙ}: r's dimensions set.
sumDS: an associative array of |D| 0
S_N: the future Skyline S normalized
sumDS_N: an associative array of |D| 0
gini: a new associative array of |D| integers
sumgini: 0;
S_NP: the future Skyline S normalized and weighted
sumDS_NP: an associative array of |D| 0
ideal: an associative array of |D| 1
sum²ideal: 0;
sqrtsum²ideal: a positive integer
score: an associative array of |D| + 1 0
for all t ∈ S do
  i := t[RowId];
  for all dⱼ ∈ D do
    sumDS[dⱼ] := sumDS[dⱼ] + t[dⱼ];
    score[i][dⱼ] := t[dⱼ];
  end for
end for
for all t ∈ S_N do
  u: u ∈ S, u[RowId] = t[RowId];
  for all dⱼ ∈ D do
    t[dⱼ] := u[dⱼ]/sumDS[dⱼ];
    sumDS²[dⱼ] := sumDS²[dⱼ] + t[dⱼ]²;
  end for
end for
for all dⱼ ∈ D do
  gini[dⱼ] := 1 - sumDS²_N[dⱼ];
  sumgini := sumgini + gini[dⱼ];
end for
for all t ∈ S_NP do
  i := t[RowId];
  u: u ∈ S_N, u[RowId] = i;
  for all dⱼ ∈ D do
    t[dⱼ] := gini[dⱼ]/sumgini × u[dⱼ];
    sumDS²_NP[i] := sumDS²_NP[i] + t[dⱼ]²;
  end for
  if t[dⱼ] < ideal[dⱼ] then
    ideal[dⱼ] := t[dⱼ];
  end if
end for
end for
for all dⱼ ∈ D do
  sum²ideal := sum²ideal + ideal[dⱼ]²;
end for
sqrtsum²ideal := √sum²ideal;
for all t ∈ S_NP do
  i := t[RowId];
  scoreₙumerator := 0;
  for all dⱼ ∈ D do
    scoreₙumerator := scoreₙumerator + ideal[dⱼ] × t[dⱼ];
  end for
  score[i][D] := scoreₙumerator / (√sumDS²_NP[i] × sqrtsum²ideal);
end for
score := reverseQuickSort(score, 0, |S| - 1);

▷ score descending sort on score[i][|D|] values, with ∀t ∈ S, i := t[RowId] return score;
<caption>Algorithm 8 DeepSky (O(k · (|S| · |D| + |r| · log(|r|))))</caption>

**Require:**
Algorithm for ranking Skyline <Algo>.
* r relation.
* Number of results k.

**Ensure:**
Top-k tuples/points with top_k highest scores.

top_k := ∅;
tot := 0;
$r_l := r$;
while tot < k ∨ $r_l = ∅$ do
    $S := <Algo>$(r_l);
    tot := tot + |S|;
    if tot ≤ k then
        top_k := top_k ∪ S;
        $r_l := r_l \setminus S$;
    else
        $S_{trunc} := S'$ k firsts points
        top_k := top_k ∪ $S_{trunc}$; return top_k
    end if
end while
return top_k