skyline-query-pareto-set-maxima.md

Skyline Query

Skyline, also known as Pareto Frontier or Pareto Set in Business Management or Maxima in Computional Geometry, is a useful technique in multi-criteria analysis and decision support. Skyline aims to identify points in n-dimensions that are not dominated by any other point. In other words, a Skyline is formed using points that are best in at least one dimension and at least as good as other best points in every other dimension. The following plot illustrates a Skyline in 2-dimensional space

Input data

HOTEL	DISTANCE_TO_DESTINATION	PRICE
a	4	400
b	24	380
c	14	340
d	36	300
e	26	280
f	8	260
g	40	200
h	20	180
i	34	140
j	28	120
k	16	60

Skyline Query using SQL

select 
  hotel
  , price
  , distance_to_destination
from scratch.saqib_ali.hotels as o
where not exists (
  select 1
  from scratch.saqib_ali.hotels as i
  where i.price <= o.price and i.distance_to_destination <= o.distance_to_destination
  and (i.price < o.price or i.distance_to_destination < o.distance_to_destination)
);

HOTEL	PRICE	DISTANCE_TO_DESTINATION
a	400	4
f	260	8
k	60	16

Skyline using Python

#!pip install paretoset
 
from paretoset import paretoset
import pandas as pd
import matplotlib.pyplot as plt

hotels = pd.DataFrame({"price": [400, 380, 340, 300, 280, 260, 200, 180, 140, 120, 60], 
                       "distance_to_destination": [4, 24, 14, 36, 26, 8, 40, 20, 34, 28, 16]})
skyline = paretoset(hotels, sense=["min", "min"])
skyline_hotels = hotels[skyline]



plt.scatter(hotels.loc[:, 'price'], hotels.loc[:, 'distance_to_destination'], alpha=0.5)
plt.scatter(skyline_hotels.loc[:, 'price'], skyline_hotels.loc[:, 'distance_to_destination'], alpha=0.1, s=300)
plt.plot(skyline_hotels.loc[:, 'price'], skyline_hotels.loc[:, 'distance_to_destination'], alpha=0.1)
plt.xlabel("price")
plt.ylabel("distance to destination")

plt.gca().invert_xaxis()
plt.gca().invert_yaxis()
plt.show()

print(skyline_hotels)

hotel	price	distance_to_destination
0	400	4
5	260	8
10	60	16

See also

{% for page in site.pages %} {% if page.title contains "Skyline" %}
• {{ page.title | escape }}
{% endif %} {% endfor %}