Raymond Chi-Wing Wong, Ada Wai-Chee Fu, Jian Pei, Yip Sing Ho, Tai Wong, Yubao Liu
EFFICIENT SKYLINE QUERYING
WITH VARIABLE USER
PREFERENCES ON
NOMINAL ATTRIBUTES
1
Gruppo 3
Alessandro Cangini (Relatore)
Marco Casadio
Valerio Sandri
SCENARIO
Le attuali tecniche di valutazione dello skyline si
basano sull’ordinamento fisso degli attributi.
 Esistono attributi il cui ordinamento non è
prefissato e varia da utente a utente.
 E’ il caso degli attributi nominali.

Auto
Prezzo
Cilindrata
Colore
Alimentazione
a
13.500
1400
Nero
Gpl
b
18.000
1600
Nero
Gpl
c
23.000
1800
Verde
Diesel
d
19.500
1400
Azzurro
Diesel
e
13.500
1200
Nero
Benzina
f
26.000
1600
Verde
Benzina
g
19.500
1600
Azzurro
Diesel
h
11.000
1200
Rosso
Diesel
2
SCENARIO

Assumiamo che un’auto sia universalmente
migliore quanto inferiore è il prezzo e superiore
la cilindrata.


Questo non vale per gli attributi Colore e
Alimentazione.
Consideriamo, per ora, solo preferenze
sull’attributo colore.
Preferenze del genere
si dicono preferenze
implicite
Utente
Preferenze
Skyline
Brian
V>A>*
{a,b,c,g,h}
Chris
N>A>*
{a,b,c,h}
Lois
R>*
{a,b,c,g,h}
Peter
A>V>*
{a,b,c,g,h}
Stewie
N>A>R>*
{a,b,c,h}
3
SCENARIO - ESEMPIO


Consideriamo le tuple:
Auto
Prezzo
Cilindrata
Colore
A
18.000
1600
Nero
B
23.000
1400
Verde
Come
Gpl
Facciamo???
Diesel
Se consideriamo solo gli attributi numerici:


Alimentazione
A > B, in quanto ha minore prezzo e maggiore
cilindrata
Tuttavia se consideriamo una preferenza del tipo
Verde > Nero


I.e. una macchina Verde e’ preferibile ad una Nera
A non domina più B in quanto e’ preferibile per
Prezzo e Cilindrata, ma non per Colore.
4
DEFINIZIONE DEL PROBLEMA


Gli algoritmi tradizionali (tipo BBS) non sono
applicabili: la funzione distanza, in questo caso, non è
calcolata solamente su attributi numerici.
Primo approccio: determinare gli skyline di tutte le
possibili preferenze implicite.
Numero di tutte le possibili preferenze implicite
proporzionale a:
O((c*c!)m’ )
 Es. con 3 ( = m’ ) attributi nominali ognuno dei quali ha 40
( = c ) possibili valori. Il numero totale di preferenze
implicite è nell’ordine di 109.


Problema: Trovare un modo efficiente di calcolare
gli skyline su attributi nominali con preferenze utente
variabili.
5
ANDIAMO OLTRE…

Un primo tentativo è stato quello di adattare
qualcosa di già esistente. Algoritmi quali BBS e
NN richiedono, ad ogni nuova preferenza
implicita, una generazione di un indice
sull’attributo categorico sul quale l’algoritmo
lavora.

Es. Supponiamo di avere 10.000 query con preferenze
implicite. Per ognuna di esse bisogna calcolare
l’indice.
Troppo
oneroso!!!
6
SFS (SORT-FIRST-SKYLINE)

E’ un algoritmo nel quale tutte le tuple sono
ordinate con una funzione f di preferenza in base
a un loro punteggio e lo skyline viene ricavato
sulla base di tale ordinamento.

Es. f come somma di tutte le dimensioni di un punto.
Vale solo per attributi numerici totalmente
ordinati.
 Se possiamo sfruttare la possibilità di variare i
valori dei punteggi in base alle preferenze
implicite, non abbiamo costi aggiuntivi in preprocessing e possiamo sfruttare solo raffinamenti
sulle preferenze implicite e non più sugli attributi
numerici.

7
SFS - ADAPTIVE


Calcolo dello skyline senza preferenze implicite
Auto
Prezzo
Cilindrata
Colore
a
13.500
1400
Nero
b
18.000
1600
Nero
c
23.000
1800
Verde
d
19.500
1400
Azzurro
e
13.500
1200
Nero
f
26.000
1600
Verde
g
19.500
1600
Azzurro
h
11.000
1200
Rosso
HOW TO: per ogni valore
dell’attributo “Colore” si
calcola uno skyline. Lo skyline
totale si ottiene dall’unione
degli skyline parziali
Calcolo del punteggio per ogni punto dello
skyline
Auto
Punteggio
a
15.904
b
18.204
c
23.004
g
19.704
h
11.604
Punteggio calcolato come:
Prezzo + (1800 – Cilindrata) + |Colore|
Monotonicità
Un’auto è ora più preferibile se Prezzo e
Cilindrata sono inferiori.
8
SFS - ADAPTIVE


Per ogni nuova query occorrono
Modifica (1)una
del ranking
in base
ad unaO(n)
preferenza
nuova modifica
del ranking;
ordinamento;
n)
implicita(2)un
e si nuovo
ordina
per valoriO(n*log
crescenti
di score.
2
(3)un nuovo check di dominanza. O (n )
Auto
Punteggio
Query: N > A > *
Auto
Punteggio
PROBLEMA: non scalabilità a fronte di
a
15.902
a
15.904
skyline grandi ed alto numero di query…
b
18.202
b
18.204
c
23.004
g
19.704
h
11.604
N = 2 , A = 1 e si
INFATTIBILE!!!
ricalcola
il punteggio
c
23.004
g
19.703
h
11.604
Si applica SFS coi valori modificati

Poiché b > g, si elimina g; lo skyline
risultante è { a,b,c,h }
IT WORKS!
Auto
Punteggio
h
11.604
a
15.902
b
18.202
g
19.703
c
23.004
9
IPO – TREE: PRESENTAZIONE
(IMPLICIT PREFERENCE ORDER)



Idea di base: memorizzare alcuni risultati
parziali che, combinati tra loro, generino il
risultato richiesto.
Come? IPO – tree: albero che memorizza
risultati per certe combinazioni di preferenze
implicite.
Come lo usiamo? Esiste la possibilità di
dividere la query in sotto-query più semplici e di
trovare i relativi skyline. Questi risultati parziali
saranno poi composti per formare il totale.
10
E con preferenze del
tipo “N > A > *” ??
IPO – TREE: COSTRUZIONE
Root
N>*
A = {}
R>*
A = {}
S:{a,b,c,e,f,g,h}
V>*
A = {}
A>*
A = {}
…
G>*
A = {e,f,g}
D>*
A = {e,f}
B>*
Φ
A = {g}
A = {e,f,g}
Φ
A = {}
…
…
G>*
D>*
B>*
A = {e,f}
A = {e,f}
A = {}
Φ
…
A = {e,f}
3. Le ogni
2.Ad
1.Per
foglie
ognilivello
combinazione
contengono
dell’albero
ledei
tuple
civalori
sono
“squalificate”
degli
i nodiattributi
relativi
dallo
alle
categorici
skyline
preferenze
della
si calcola
implicite
lo
radice
skyline
perdi
sugli
quella
solamente
attributi
combinazione
unnumerici
attributo
di preferenze
e (inclusa
questo silaimplicite
inserisce
preferenza
nella
nulla
radice.
Φ).
11
IPO – TREE: PROPRIETÀ DI MERGE

Date due preferenze implicite su uno stesso
attributo categorico e i rispettivi skyline
v1 > v2 > … > vx-1 > * e
SKY1
2. vx > *
e
SKY2
Lo skyline relativo alla preferenza implicita
v1 > v2 > … > vx-1 > vx > *
(indicato con SKY3) si calcola come
SKY3 = (SKY1 ∩ SKY2) ∪ PSKY1
dove PSKY1 è l’insieme dei punti di SKY1 che hanno
valori in v1, … , vx-1
(quelli esplicitati nella preferenza implicita)
1.

Oss: La definizione è ricorsiva su (1).
12
IPO – TREE: PROPRIETÀ DI MERGE

Es. Consideriamo le preferenze sul colore di Chris
N>A>*
Molto
Bene!!!
N>A>R>*
A>*
N>*
/
\
SKYN = {a,b,c,h} N > A > *
R > *SKYA = {a,b,c,g,h}
PSKYN = {a,b} /
\
N>*
A>*
(SKYN ∩ SKYA) ∪ PSKYN = {a,b,c,h}
Utente
Preferenze
Skyline
Brian
V>A>*
{a,b,c,g,h}
Chris
N>A>*
{a,b,c,h}
Lois
R>*
{a,b,c,g,h}
Peter
A>V>*
{a,b,c,g,h}
Stewie
N>A>R>*
{a,b,c,h}
Come la
mettiamo con le
mie
preferenze?!
IT
WORKS!!!
13
IPO – TREE: APPLICAZIONE DEL MERGE
S:{a,b,c,e,f,g,h}
Root
N>*
R>*
G>*
D>*
A = {e,f,g}
A = {e,f}
V>*
B>*
Φ
G>*
A = {g}
A = {e,f,g}
A = {e,f}
D>*
A = {e,f}
B>*
A = {}
Φ
A = {e,f}
A > *, B > *
N > *, B > *
SKY1 = {a,b,c,e,f,h}
PSKY1 = {e}
Φ
A>*
N > A > *, B > *
MERGE: SKY3 = {a,b,c,e,f,h}
SKY2 = {a,b,c,e,f,g,h}
14
IPO – TREE: DIMENSIONE

L’albero così creato ha un numero di nodi
proporzionale a:
O(cm’ )


Es. con 3 ( = m’ ) attributi nominali ognuno dei quali
ha 40 ( = c ) possibili valori. Il numero totale di nodi è
nell’ordine di 104.
Oss: la generazione di tutte le preferenze
implicite e’ nell’ordine di 109.
Che
risparmio!!!
15
RISULTATI COMPUTAZIONALI

Misuriamo l’efficienza confrontandola con SFS-A
su di un Dataset Reale (Nursery Dataset from
UCI Machine Learning Repository) in termini di:
Memoria impiegata.
 Costo temporale in fase di preparazione
(preprocessing)
 Costo temporale in fase di esecuzione (query time)


Parametri di Riferimento:
DB Size
 Numero di attributi non nominali
 Ordine delle preferenze implicite delle query

16
RISULTATI COMPUTAZIONALI

Misuriamo l’efficienza in termini di
Memoria impiegata
 Costo temporale in fase di preparazione
(preprocessing)
 Costo temporale in fase di esecuzione
(query time)

DB size
Numero di
attributi non
nominali
Ordine delle
preferenze implicite
delle query
17
RISULTATI COMPUTAZIONALI

Misuriamo l’efficienza in termini di
Memoria impiegata
 Costo temporale in fase di preparazione
(preprocessing)
 Costo temporale in fase di esecuzione
(query time)

DB size
Numero di
attributi non
nominali
Ordine delle
preferenze implicite
delle query
18
RISULTATI COMPUTAZIONALI

Misuriamo l’efficienza in termini di
Memoria impiegata
 Costo temporale in fase di preparazione
(preprocessing)
 Costo temporale in fase di esecuzione
(query time)

DB size
Numero di
attributi non
nominali
Ordine delle
preferenze implicite
delle query
19
CONCLUSIONI E SVILUPPI FUTURI

A fronte di una maggiore costo in fase di preprocessing e in termini di memoria impiegata, si
hanno notevoli miglioramenti a run-time


Maggiore efficienza!
Sviluppi futuri:
Aggiornamento IPO-tree;
 Studio di metodologie alternative (introdurre negli
attuali algoritmi di skyline il concetto di attributo
nominale qualora ne siano sprovvisti).

20
GRUPPO 3 - FINE
Alessandro Cangini (Relatore)
Marco Casadio
Valerio Sandri
21