Oltre le top-$k$: skyline queries

Le query top k hanno dei limiti in termine di espressività, in quanto possono solo catturare preferenze che si traducono in valori numerici

Dominanza delle tuple

Un concetto fondamentale per le skyline query e la dominanza delle tuple:

data una relazione $R(A_1,A_2,...,A_m,...)$ dove $A_i$ sono gli attributi di rank una tupla $t$ domina una tupla $t^{{}^{\prime }}$ ($t\succ t^{{}^{\prime }}$) quando $\forall j\in [1,m]t_{Aj}\le t_{Aj}^{{}^{\prime }}\wedge \exists j:t_{Aj}<t_{Aj}^{{}^{\prime }}$

ovvero $t$ ha valori non peggiori di $t^{{}^{\prime }}$ e almeno un valore di $t$ e strettamente migliore di $t^{{}^{\prime }}$

Si definiscono di conseguenza le regioni di dominanza e anti-dominanza di una tupla $t$

Di conseguenza l’output della skyline query e definito come segue:

data una relazione $R(A_1,A_2,...,A_m)$ la sua skyline e definita come $sky(R)=\{t|t\in R,\nexists t^{{}^{\prime }}\in R:t^{{}^{\prime }}\succ t\}$

Cosa c’e’ di speciale nelle query skyline

Se si prende in considerazione il set di funzioni di distanza monotone $MD$ si ha che il primo nearest neighbor per una funzione di distanza $d$ e parte della skyline e che un punto della skyline $t$ e minimizza sempre una qualche funzione di distanza $d\in DM$

$$t\in sky(R)\iff \exists d\in MD:\forall t^{{}^{\prime }}\in R,t^{{}^{\prime }}\ne t:d(t,q)<d(t^{{}^{\prime }},q)$$

Inoltre l’output della query skyline non corrisponde a quello di nessuna query top-$k$

Data una relazione $R(A_1,...,A_m)$ non esiste nessuna funzione di distanza $d$ che per tutte le istanze possibili di $R$ contiene tutti i punti della skyline nelle prime $k$ posizioni

Quindi la skyline ha più potere espressivo

Valutare le query skyline

Il problema con la valutazione delle query skyline sta nel fatto che nel caso peggiore la complessità segue $\Theta (N^2)$ per un database con $N$ oggetti, i possibili approcci sono i seguenti:

• computare la skyline sfruttando una scansione sequenziale del file
• sfruttare un indici

Naive nested loops

La soluzione più semplice e quella di scandire $R$ per comparare una tupla con tutte le altre

Sky = []
for t in R:
	undominated := true;
	# comparazione con tutte le tuple di R
	for c in R:
		if c.dominates(t): 
			undominated = False 
			break
	# aggiunge la tupla se non dominata
	if undominated:
		Sky.append(t)
retun Sky

non molto efficiente...

Block nested loops

Un miglioramento lo si ha sfruttando un blocco di memoria di dimensione $w$ e ogni tupla letta dal file viene comparata con quelle nel buffer e di conseguenza scartata se non dominante

Performance del block nested loops

Evidenze sperimentali hanno dimostrato che BNL e CPU intensive e con un basso costo di I/O, inoltre la dimensione $w$ della window degrada le performance in quanto si effettuano più controlli sulle tuple

SFS Sort-Filter-Skyline

L’idea e quella di ridurre il numero di confronti, per fare ciò si introduce un ordinamento topologico completo che garantisce che $t\succ t^{{}^{\prime }}\Rightarrow t<t^{{}^{\prime }}$ in questo modo si ha che una tupla letta non può dominarne una già letta

Questo approccio ha diversi vantaggi tra cui:

• non si effettuano comparazioni tra punti non della skyline
• le tuple nella window possono essere date in output subito in quanto non ci sono tuple nel file in grado di dominarle
• viene effettuato il minor numero di iterazioni $\lceil |\frac{sky(R)}{W}|\rceil$

Salsa sort and limit skyline algorithm

SaLSa e un miglioramento di SFS in quanto se le tuple sono ordinate topologicamente non e necessario leggere tutto il file, il punto di arresto e stabilito quando nessuna tupla e nell’area di dominanza di un dato stopping point $t_{stop}$ in particolare si ha che la scelta ottimale e data da $t_{stop}=argmi{n}_{t\in sky(R)}(ma{x}_i(t_{Ai}))$ ovvero il punto della skyline per cui la coordinata maggiore e minima

Computare la skyline con r-tree

L’idea di base sta nel non accedere a nodi che rappresentano aree completamente dominate da punti della skyline

#Input: index tree with root node RN
#Output: Sky, the skyline of the indexed data
PQ = TreeRoot
Sky = []
while ! PQ.empty():
	node = pq.next()
		for t in sky:
			dominate = False
			if t.dominates(node):
				dominate = True
		if  ! dominate:
		if node.isTuple():
			sky.append(node)
		else(PQ.append(node.childs))
return Sky

l'algoritmo BBS e ottimale e corretto :)

Skyline in domini a bassa cardinalita

Molte situazioni reali prevedono che gli attributi di interesse per la skyline abbiano un numero limitato di valori (booleani o enumerazioni)

In questo caso si possono sfruttare le peculiarità di questi domini

Algoritmo LS-B

Viene predisposta una matrice data da tutte le possibili combinazioni degli attributi di interesse

Si scandisce il file e si marcano le tuple corrispondenti nella matrice come presenti, successivamente si determinano le dominanti tra quelle presenti e si rilegge il file fornendo in output quelle nella matrice

PREVIOUS NEXT