Q: Top-K query: k-Nearest-Neigbor, algoritmi per la risoluzione di middleware query (top-k join 1:1 query)
A:
Le Top-K query sono interrogazioni che richiedono come risultato solo i K migliori valori.
Migliori secondo determinati criteri: ad esempio si potrebbero richiedere i migliori ristoranti di una determinata città, in base al rapporto qualità prezzo medio, oppure richiedere i K voli tra due città, ordinate in base ad un qualche criterio.
Questo tipo di interrogazioni sono utili nel caso in cui si voglia fornire un insieme di risultati, ordinati in base a delle preferenze. Quindi è possibile anche fornire risultati che non rispecchiano perfettamente la richiesta fatta, ma che ci si avvicinano, cioè si assomigliano a quanto richiesto.
Se, ad esempio, il volo che cerchiamo per una determinata ora non esiste, il sistema deve fornirci alternative valide (e quindi simili).
Ma come è possibile ottenere solo K risultati?
Si potrebbe pensare di sfruttare, lato client, il metodo
Questa soluzione non è la migliore, in quanto i DBMS effettuano il row blocking per la trasmissione del risultato al cliente.
Il row-blocking consiste nel
Questo per ridurre l'overhead che una serie di trasmissioni causerebbe. Quindi, in realtà, quando il cliente invoca il metodo next(), usa un cursore su un blocco locale.
Inoltre il DBMS è totalmente ignorante del fatto che il cliente fermerà la sua esecuzione solo dopo K invocazioni del metodo next(), per cui è naturale pensare ad una soluzione migliore cche permetta di non sprecare risorse.
È possibile effettuare questo tipo di interrogazioni in SQL-extended. SQL standard, infatti, non permette di limitare la cardinalità del risultato.
I DBSM mettono a disposizione sintassi apposite per poter limitare la cardinalità del risultato, ad esempio troviamo
Avendo esteso la sintassi SQL, ora il DBMS è conscio del fatto che il cliente necessita di solo k tuple, per cui potrà utilizzare algoritmi adatti a questo scopo.
Oltre ad ottenere solo K risultati, vogliamo che questi K abbiamo un'ordine.
L'ordine viene specificato nella maniera standard di SQL, cioè tramite la clausola
Di conseguenza, è possibile anche estendere l'algebra relazionale, introducendo l'operatore [m]\tau_{k,S}[/m], detto Top, che permette di ottenere k risultati, ordinati in base alla funzione di scoring S.
L'implementazione fisica dell'operatore top può avvenire in due modi
Quasi mai i dati in ingresso all'operatore top saranno già ordinati per scrore, di conseguenza l'implementazione più usata sarà la top-sort.
È possibile (anzi è usuale) che le top-k query coivolgano più attributi, anche di relazioni diverse.
Nella seguente query possiamo individuare:
Se la funzione di score coinvolge un solo attributo, il caso è poco interessate e ci si riconduce a metodologie classiche per la ricerca, in quanto che se vi è un peso, basterà accedere (nella maniera più efficiente, quindi se c'è un indice usarlo, ecc) all'attributo e scorrerlo (e se necessario ordinarlo) e restituire le k tuple individuate.
Quando la funzione di score coinvolge più di un attributo, le cose si fanno più interessanti. In quanto passiamo in uno spazio a più di una dimensione, dove le cose si complicano (ma che permette di ottenere informazioni più utili).
Nella query presentata precedentemente, abbiamo due attributi. Ognuno dei quali può essere rappresentato come coordinata di un piano cartesiano.
Ci troviamo quindi ora in uno spazio 2-d, un cui sulle asse delle ascisse troviamo il prezzo e sull'asso delle ordinate il chilometraggio.
Ogni tupla è identificata dalla combinazione di questi due attributi (quindi ogni tupla è identificata da un punto nel piano).
Bigona valutare come eseguire la query nella maniera più efficiente possibile.
È necessario innanzitutto analizzare la geometria del problema in questo caso.
La funzione di scoring è rappresentata da una retta. Per ogni coppia (price,mileage) assume un valore costante. Quindi è possibile esprimere mileage in funzione di price e del valore costante e rappresentare la retta sul piano.
È evidente che i pesi variano l'inclinazione della retta (difatti rappresentano il coefficiente angolare). Inoltre, per ogni valore costante, abbiamo rette perpendicolari "ugualmente buone". Cioè la retta si sposta ed ogni punto che incontra è un valore valido.
Fino ad ora abbiamo assunto che l'obiettivo della query fosse trovare le auto con il miglior rapporto prezzo/chilometraggio, in base alla scoring function.
Quindi si è sottinteso il fatto che l'obiettivo della scoring function fosse il punto di origine (cioè si vuole un auto a prezzo 0 e chilometraggio 0).
In realtà ogni punto può essere un obiettivo.
In generale, per determinare la migliore tupla t fra un insieme di tuple, calcoliamo la sua distanza dal punto obiettivo q.
Minore è la distanza, migliore sarà t.
Notare che la distanza tra i valori può essere sempre convertita in bontà del punteggio, in modo che punteggio migliore significhi distanza minore e viceversa.
Introdurre il concetto di distanza, fa sì che sia possibile chiedersi quali siamo le k tuple migliori rispetto ad una tupla obiettivo, cioè quali siamo le k tuple più vicine all'obiettivo.
K-Nearest Neighbor (k-NN)
Quando abbiamo un indice sugli attributi di ranking, è utile considerare le distanze anziché i punteggi. Il modello che ne deriva è il seguente
Sotto questo modello, una top-k query è trasformata in una k-Nearest Neighbor: dato un punto q, una relazione R, un intero k>=1 ed una funzione distanza d, determinare le tuple in R più vicina a q, secondo d.
Le distanze più comunemente utilizzate sono le funzioni norme in [m]L_p[/m]:[math]L_p(t,q) = \left(\sum_{i=1}^{D}{|t_i - q_i|^{p}}\right)^{\frac{1}{p}}[/math]
di cui i casi più rilevanti sono:
Aggiungendo coefficienti (pesi) ai vari attributi, otteniamo ovviamente le norme pesate. Questo tipo di norme si usano per dare un maggior peso ad un attributo anziché ad un altro.
Supponendo di avere un R-tree sugli attributi di ranking, l'algoritmo per la risoluzione di una k-NN query si basa sul concetto di regione.
Dato un raggio r, si definisce regione di un punto q: [m]Reg(q) = \left\{p | d(p,q) \le r\right\}[/m]
Dato che stiamo utilizzando un R-tree, ogni nodo contiene un insieme di punti, per ogni nodo si calcola la distanza minima dal punto obiettivo, che fornisce un lower bound sulla distanza tra q ed un punto qualsiasi dalla regione identificata dal nodo N.
In quanto, intuitivamente, la distanza minima fra un punto q ed una regione N è sicuramente minore o uguale alla distanza minima tra il punto q ed un qualsiasi punto appartenente alla regione stessa.
Per cui, la k-NN viene risolta in base alla seguente considerazione: [math]Reg(q) \cap Reg(N) \Leftrightarrow d_{MIN}(q,Reg(N)) \le r[/math]
Dato che la nostra k-NN ha un raggio di copertura, fisso, verrà restituito in output solo l'insieme di punti le cui regioni hanno intersezioni con la regione della query, ordinati in base alla distanza minima, limitati a k risultati.
Esiste una variante dell'algoritmo appena mostrato, chiamato k-NNOptimal.
Questo algoritmo, come è facile intuire, è ottimo dal punto di vista delle operazioni di I/O: ovvero si legge il numero minore di nodi dell'albero per la risoluzione della query.
Questo algoritmo fa uso di una coda prioritaria, i cui valori sono ordinati per valori crescenti della distanza minima tra la regione e la query.
Utilizzando questa cosa, non utilizza più un raggio di copertura della query fisso, ma cerca all'interno delle regioni con distanza minima (quindi quelle più promettenti).
Estrae dalla coda la prima regione, la espande, se trova delle foglie allora per ognuna di queste effettua il calcolo della distanza.
Se la distanza trovata è minore del raggio attualmente utilizzato, allora rimuove il k-esimo elemento della risulta risultato, inserisce in cima a questa lista il nuovo nodo trovato, ed aggiorna il raggio di ricerca con la distanza trovata.
Se non trova delle foglie, ma trova altri nodi, ne calcola la distanza minima e se trova una regione con distanza minima minore del raggio di ricerca attuale, inserisce la regione all'interno della coda prioritaria, che andrà analizzata (non è detto che questa regione a distanza minima contenga punti a distanza minima, quindi va inserita in coda ed analizzata per questo motivo, finché non si trova una foglia ed in tal caso eseguire quanto detto precedentemente).
Fino ad ora abbiamo considerato top-k query sulla stessa relazione. Come è necessario comportarsi quando gli attributi di ranking appartengono a relazioni differenti?
È necessario fare join.
Il caso più semplice (che è quello di maggior utilizzo) è il cado delle top-k join 1:1 query. In cui abbiamo n>1 relazione in input e una funzione di scoring S definita sul risultato di join (cioè su una combinazione di preferenze, appartenenti a più relazioni collegate tra di loro tramite il join).
Il caso in cui siano presenti più relazioni, è assimilabile al caso in cui i risultati delle subquery provengano da fonti (data source) diverse. Parliamo in questo caso di middleware scenario:
Query di questo tipo sono dette middleware query, dato che richiedono la presenza di middleare (intermediare) tra utente/client e i vari data source/server.
È intuitivo il funzionamento per quanto riguarda i classici join, semplicemente ogni server effettua la subquery ed il mediatore accumula i vari risultati ed esegui il join, infine è lui a restituire il risultato al client.
Il funzionamento delle top-k middleware query (altro nome per top-k 1:1 join query) è meno immediato e necessita di algoritmi in grado di rendere efficiente il processo si sorting e limiting di dati provenienti da fonti diverse.
Quanto detto per le fonti diverse (su server diversi) vale anche per relazioni diverse, il funzionamento è identico.
Per trattare gli algoritmi presentati nel seguito è necessario introdurre una nuova terminologia per trattare le relazioni e le tuple.
Difatti d'ora in poi ogni input (relazione) sarà indicata con [m]L_i[/m], dove L sta per lista.
Inoltre non si lavorerà più con tuple, ma con oggetti. Questo perché è ragionevole dire che un oggetto o appartiene a due differenti input, mentre è errato dire lo stesso per una tupla.
Inoltre, onde evitare di dover leggere ogni oggetto di ogni input, è bene assumere che:
Per cui supponiamo che ogni input sia una lista ordinata in base ad una determinata scoring function parziale (cioè la scoring function che considera solo gli attributi di ranking presenti su quell'input).
Inoltre, dobbiamo considerare che
Alcune delle scoring function più utilizzate sono:
NB: anche se si usa la funzione MIN, si vogliono sempre ottenere i k oggetti con il più alto punteggio globale.
Finalmente è possibile domandarsi: come è possibile calcolare in maniera efficiente una top-k 1:1 join query?
Abbiamo a disposizione diversi algoritmi, in cui un prerequisito fondamentale è che la scoring function utilizzata S sia monotona.
Questo perché aiutano ad effettuare considerazioni geometriche che permettono di ottimizzare gli algoritmi (non di poco) ed inoltre riflettono la realtà: infatti ci si aspetta migliorando la bontà di una determinata caratteristica, la bontà globale non risulti peggiore.
Nel seguito esamineremo gli algoritmi:
Algoritmo [m]B_0[/m]
Questo algoritmo permette di ottenere il risultato della top k 1:1 join query calcolando i k valori migliori per ogni risorsa, a patto che la funzione di scoring globale usata sia MAX.
Inoltre, non effettua alcun accesso casuale.
Ricorare che stiamo supponendo che ogni lista ci fornisce l'oggetto ed il punteggio parziale assegnato. Punteggio parziale che identifica una preferenza.
Il funzionamento è semplice:
Predisponiamo un buffer B ed inizializziamo gli insiemi Obj(j) uno per ogni risorsa, vuoti.
Per ogni input j si tenta di riempire l'insieme associato utilizzando solamente il metodo getNext() (che in questo caso prende il nome di next_NN() in quanto ritorna il NN prossimo) fino ad averne k: ogni volta che trovo un oggetto (da una qualsiasi lista) controllo se l'avevo già incontrato ed in tal caso aggiungo all'oggetto anche il risultato parziale appena trovato, oppure lo inserisco bel buffer B.
Infine, per ogni oggetto che ho visto almeno una volta, ovvero che ha almeno un risultato parziale, calcolo la scoring function MAX su di esso e infine restituisco i primi k oggetti.
L'algoritmo [m]B_0[/m] adopera k accesso ordinati su ogni lista (k s.a. round) e successivamente calcola il risultato senza bisogna di ottenere i risultati parziali mancanti, quindi non è necessario alcun accesso casuale.
Questo algoritmo, funziona solo con la funzione di scoring MAX e la dimostrazione di ciò è dovuta a considerazioni geometriche.
In sostanza, la funzione MAX cerca il valore del punteggio totale maggiore. Questo significa che è come se effettuasse una scansione dei punti a partire dal punto [1,1] fino ad arrivare al punto [0,0].
Se troviamo un punto le cui preferenze si trovano in questa dirazione, il primo che troviamo è sicuramente quello con il punteggio globale MAX maggiore degli altri.
Per questo motivo non richiede nemmeno accessi casuali per poter ottenenere i rimanenti punteggi (magari troviamo per primo il punteggio lungo l'asse x, ma non lungo l'asse y. Questo non ci servirà se prima di incontrarlo troviamo altri k punti durante la scansione).
Algoritmo FA
L'algoritmo FA funziona con qualsiasi scoring function monotona. È un algoritmo in tre passi, il cui lato negativo è che utilizza S solo nell'ultimo passo, evitando ottimizzazioni.
La scelta di utilizzare solo alla fine la funzione S ha come svantaggio quello di non produrre ottimizzazioni basate su questa, ma rende più flessibile l'algoritmo in quanto è possibile (avendo bufferizzato tutti i risultati richiesti) calcolare il risultati per una qualsiasi altra funzione S, in quanto del tutto generali non essendo collegati ad alcuna scoring function.
Algoritmo TA
È una specializzazione del FA, che fa uso del concetto di soglia per interrompere la ricerca.
Sfrutta la funzione S per il calcolo della soglia, quindi a differenza di FA non la utilizza solo all'ultimo passo d'esecuzione.
Anche in questo caso, l'algoritmo è abbastanza intuitivo.
In generale TA funziona molto meglio di FA poiché riesce ad adattarsi alla specifica scoring function S.
Sicuramente è più efficiente di FA in quanto la condizione di stop di FA implica quella di TA.
In particolare è dimostrabile che FA è ottimale per le istanze (concetto più forte della semplice ottimalità nel caso peggiore).
Algoritmo NRA
È un algoritmo applicabile per qualsiasi funzione di scoring monotona S, nelle situazioni in cui non vi è possibile effettuare accessi casuali alle liste.
L'algoritmo ritorna i top-k oggetti, ma il loro punteggio potrebbe essere sbagliato, questo per limitare il costo dell'algoritmo stesso (nb: i punteggi sono errati, non la posizione).
L'idea dietro NRA è di mantenere un lower bound ed un upper bound per ogni oggetto incontrato, durante un accesso ordinato, sul loro punteggio.
Evidentemente bisogna scorrere la lista solo tramite accessi sequenziali e per ogni accesso fatto calcolare questi valori.
L'algoritmo si ferma quando nessun oggetto non appartenente al risultato, non può essere migliore di uno appartenente al risultato. Cioè quando [math]S^{+}(o') \le S^{-}(o) \forall o' \not{\in} Res, o \in Res[/math].
Cioè quando l'upper bound di un oggetto non presente nel risultato risulta minore o uguale al lower bound del k-esimo oggetto il Res (poiché Res è ordinata per valori di lower bound non crescenti).
In pratica l'algoritmo si ferma quando nessun oggetto che non è tra i primi k-oggetti (quindi quelli [m]\in Res[/m]) possa modificare Res.
Algoritmo CA
L'algoritmo CA è un tentativo di ridurre l'influenza negativa degli alti costi degli accessi casuali. L'idea dietro CA è semplice:
piuttosto che eseguire accessi casuali ad ogni round, li si esegue ogni [m]\frac{c_{RA}}{c_{SA}}[/m] round (con il numeratore = costo degli accessi casuali, e denominatore costo degli accessi sequenziali).
Nella pratica CA si comporta come NRA e mantiene per ogni oggetto incontrato un lower ed upper bound sui punteggi, inoltre ogni [m]\frac{c_{RA}}{c_{SA}}[/m] round ne esegue uno casuale.
Il punto chiave sta nella scelta relativa a quali oggetti è necessario richiedere l'accesso casuale.
L'euristica applicata è quella di scegliere gli oggetti o per i quali mancano alcuni risultati parziali e per i quali l'upper bound è massimo (cioè si scelgono i più promettenti).
A:
Le Top-K query sono interrogazioni che richiedono come risultato solo i K migliori valori.
Migliori secondo determinati criteri: ad esempio si potrebbero richiedere i migliori ristoranti di una determinata città, in base al rapporto qualità prezzo medio, oppure richiedere i K voli tra due città, ordinate in base ad un qualche criterio.
Questo tipo di interrogazioni sono utili nel caso in cui si voglia fornire un insieme di risultati, ordinati in base a delle preferenze. Quindi è possibile anche fornire risultati che non rispecchiano perfettamente la richiesta fatta, ma che ci si avvicinano, cioè si assomigliano a quanto richiesto.
Se, ad esempio, il volo che cerchiamo per una determinata ora non esiste, il sistema deve fornirci alternative valide (e quindi simili).
Ma come è possibile ottenere solo K risultati?
Si potrebbe pensare di sfruttare, lato client, il metodo
row.next() ed iterarlo per k volte.Questa soluzione non è la migliore, in quanto i DBMS effettuano il row blocking per la trasmissione del risultato al cliente.
Il row-blocking consiste nel
- eseguire la query
- collezionare un blocco di tuple soddisfacenti il risultato
- inviare il blocco di tuple al chiamante
Questo per ridurre l'overhead che una serie di trasmissioni causerebbe. Quindi, in realtà, quando il cliente invoca il metodo next(), usa un cursore su un blocco locale.
Inoltre il DBMS è totalmente ignorante del fatto che il cliente fermerà la sua esecuzione solo dopo K invocazioni del metodo next(), per cui è naturale pensare ad una soluzione migliore cche permetta di non sprecare risorse.
È possibile effettuare questo tipo di interrogazioni in SQL-extended. SQL standard, infatti, non permette di limitare la cardinalità del risultato.
I DBSM mettono a disposizione sintassi apposite per poter limitare la cardinalità del risultato, ad esempio troviamo
limit k in PostgreSQL, FETCH FIRST k ROWS ONLY in 2DB, ecc.Avendo esteso la sintassi SQL, ora il DBMS è conscio del fatto che il cliente necessita di solo k tuple, per cui potrà utilizzare algoritmi adatti a questo scopo.
Oltre ad ottenere solo K risultati, vogliamo che questi K abbiamo un'ordine.
L'ordine viene specificato nella maniera standard di SQL, cioè tramite la clausola
ORDER BY. La differenza principale rispetto agli ordinamenti classici, è che nelle top-k query l'ordinamento viene fatto in base ad una funzione di scoring S, che è funzione degli attributi delle relazioni coinvolte nell'interrogazione.Di conseguenza, è possibile anche estendere l'algebra relazionale, introducendo l'operatore [m]\tau_{k,S}[/m], detto Top, che permette di ottenere k risultati, ordinati in base alla funzione di scoring S.
L'implementazione fisica dell'operatore top può avvenire in due modi
- Top-sort: considera i dati in ingresso non ordinati secondo S, quindi deve ottenere prima tutti i dati su cui lavorare per poi applicare la funzione S ed ordinare i valori e quindi restituire le prime k tuple. Di conseguenza non può lavorare in pipeline.
- Top-scan: considera i dati in ingresso ordinati secondo S, quindi deve semplicemente leggere le prime k tuple in ingresso e restituirle in output. Quindi può lavorare in pipeline.
Quasi mai i dati in ingresso all'operatore top saranno già ordinati per scrore, di conseguenza l'implementazione più usata sarà la top-sort.
È possibile (anzi è usuale) che le top-k query coivolgano più attributi, anche di relazioni diverse.
sql:Text version
SELECT * FROM cars
WHERE color='red'
ORDER BY 0.8*price + 0.2*mileage
FETCH FIRST 5 ROWS ONLYNella seguente query possiamo individuare:
- Un predicato di selezione
WHERE - Un ordinamento in base ad una scoring function [m]0.8\cdot\text{price} + 0.2\cdot\text{mileage}[/m], in cui 0.8 e 0.2 sono pesi usati per normalizzare i valori, mentre price e mileage sono gli attributi di ranking appartenenti alla stessa relazione cars.
- Un predicato che indica di limitare la cardinalità del risultato a 5 record
Se la funzione di score coinvolge un solo attributo, il caso è poco interessate e ci si riconduce a metodologie classiche per la ricerca, in quanto che se vi è un peso, basterà accedere (nella maniera più efficiente, quindi se c'è un indice usarlo, ecc) all'attributo e scorrerlo (e se necessario ordinarlo) e restituire le k tuple individuate.
Quando la funzione di score coinvolge più di un attributo, le cose si fanno più interessanti. In quanto passiamo in uno spazio a più di una dimensione, dove le cose si complicano (ma che permette di ottenere informazioni più utili).
Nella query presentata precedentemente, abbiamo due attributi. Ognuno dei quali può essere rappresentato come coordinata di un piano cartesiano.
Ci troviamo quindi ora in uno spazio 2-d, un cui sulle asse delle ascisse troviamo il prezzo e sull'asso delle ordinate il chilometraggio.
Ogni tupla è identificata dalla combinazione di questi due attributi (quindi ogni tupla è identificata da un punto nel piano).
Bigona valutare come eseguire la query nella maniera più efficiente possibile.
- Se non abbiamo alcun indice (ne su color, ne sugli attributi di ranking) dobbiamo per forza usare il top-sort
- Se abbiamo un indice su color, allora possiamo usarlo per effettuare pruning e ridurre così lo spazio di ricerca (e dopo applicare il top-sort)
- Se abbiamo un indice sugli attributi di ranking, come comportarsi?
È necessario innanzitutto analizzare la geometria del problema in questo caso.
La funzione di scoring è rappresentata da una retta. Per ogni coppia (price,mileage) assume un valore costante. Quindi è possibile esprimere mileage in funzione di price e del valore costante e rappresentare la retta sul piano.
È evidente che i pesi variano l'inclinazione della retta (difatti rappresentano il coefficiente angolare). Inoltre, per ogni valore costante, abbiamo rette perpendicolari "ugualmente buone". Cioè la retta si sposta ed ogni punto che incontra è un valore valido.
Fino ad ora abbiamo assunto che l'obiettivo della query fosse trovare le auto con il miglior rapporto prezzo/chilometraggio, in base alla scoring function.
Quindi si è sottinteso il fatto che l'obiettivo della scoring function fosse il punto di origine (cioè si vuole un auto a prezzo 0 e chilometraggio 0).
In realtà ogni punto può essere un obiettivo.
In generale, per determinare la migliore tupla t fra un insieme di tuple, calcoliamo la sua distanza dal punto obiettivo q.
Minore è la distanza, migliore sarà t.
Notare che la distanza tra i valori può essere sempre convertita in bontà del punteggio, in modo che punteggio migliore significhi distanza minore e viceversa.
Introdurre il concetto di distanza, fa sì che sia possibile chiedersi quali siamo le k tuple migliori rispetto ad una tupla obiettivo, cioè quali siamo le k tuple più vicine all'obiettivo.
K-Nearest Neighbor (k-NN)
Quando abbiamo un indice sugli attributi di ranking, è utile considerare le distanze anziché i punteggi. Il modello che ne deriva è il seguente
- Uno spazio degli attributi D>1 dimensionale A=(A1,A2,...,Ad), di attributi di ranking
- Una relazione R(A1,...,Ad,B1,B2,...) con i vari attributi Bi "superflui" della relazione
- Un punto obiettivo della query q=(q1,q2,...,qd) in cui ovviamente [m]q \in A[/m]
- Una funzione [m]d: A \times A \rightarrow \mathbb(R)[/m] che misura la distanza tra i punti di A.
Sotto questo modello, una top-k query è trasformata in una k-Nearest Neighbor: dato un punto q, una relazione R, un intero k>=1 ed una funzione distanza d, determinare le tuple in R più vicina a q, secondo d.
Le distanze più comunemente utilizzate sono le funzioni norme in [m]L_p[/m]:[math]L_p(t,q) = \left(\sum_{i=1}^{D}{|t_i - q_i|^{p}}\right)^{\frac{1}{p}}[/math]
di cui i casi più rilevanti sono:
- La distanza euclidea: [m]L_2(t,q) = \left(\sum_{i=1}^{D}{|t_i - q_i|^{2}}\right)^{\frac{1}{2}}[/m]
- La distanza di Manthattan, per p=1
- La distanza di Čebyšëv:, [m]L_{\infty}(t,q) = max_i\left\{|t_i - q_i|\right\}[/m]
Aggiungendo coefficienti (pesi) ai vari attributi, otteniamo ovviamente le norme pesate. Questo tipo di norme si usano per dare un maggior peso ad un attributo anziché ad un altro.
Supponendo di avere un R-tree sugli attributi di ranking, l'algoritmo per la risoluzione di una k-NN query si basa sul concetto di regione.
Dato un raggio r, si definisce regione di un punto q: [m]Reg(q) = \left\{p | d(p,q) \le r\right\}[/m]
Dato che stiamo utilizzando un R-tree, ogni nodo contiene un insieme di punti, per ogni nodo si calcola la distanza minima dal punto obiettivo, che fornisce un lower bound sulla distanza tra q ed un punto qualsiasi dalla regione identificata dal nodo N.
In quanto, intuitivamente, la distanza minima fra un punto q ed una regione N è sicuramente minore o uguale alla distanza minima tra il punto q ed un qualsiasi punto appartenente alla regione stessa.
Per cui, la k-NN viene risolta in base alla seguente considerazione: [math]Reg(q) \cap Reg(N) \Leftrightarrow d_{MIN}(q,Reg(N)) \le r[/math]
Dato che la nostra k-NN ha un raggio di copertura, fisso, verrà restituito in output solo l'insieme di punti le cui regioni hanno intersezioni con la regione della query, ordinati in base alla distanza minima, limitati a k risultati.
Esiste una variante dell'algoritmo appena mostrato, chiamato k-NNOptimal.
Questo algoritmo, come è facile intuire, è ottimo dal punto di vista delle operazioni di I/O: ovvero si legge il numero minore di nodi dell'albero per la risoluzione della query.
Questo algoritmo fa uso di una coda prioritaria, i cui valori sono ordinati per valori crescenti della distanza minima tra la regione e la query.
Utilizzando questa cosa, non utilizza più un raggio di copertura della query fisso, ma cerca all'interno delle regioni con distanza minima (quindi quelle più promettenti).
Estrae dalla coda la prima regione, la espande, se trova delle foglie allora per ognuna di queste effettua il calcolo della distanza.
Se la distanza trovata è minore del raggio attualmente utilizzato, allora rimuove il k-esimo elemento della risulta risultato, inserisce in cima a questa lista il nuovo nodo trovato, ed aggiorna il raggio di ricerca con la distanza trovata.
Se non trova delle foglie, ma trova altri nodi, ne calcola la distanza minima e se trova una regione con distanza minima minore del raggio di ricerca attuale, inserisce la regione all'interno della coda prioritaria, che andrà analizzata (non è detto che questa regione a distanza minima contenga punti a distanza minima, quindi va inserita in coda ed analizzata per questo motivo, finché non si trova una foglia ed in tal caso eseguire quanto detto precedentemente).
Fino ad ora abbiamo considerato top-k query sulla stessa relazione. Come è necessario comportarsi quando gli attributi di ranking appartengono a relazioni differenti?
È necessario fare join.
Il caso più semplice (che è quello di maggior utilizzo) è il cado delle top-k join 1:1 query. In cui abbiamo n>1 relazione in input e una funzione di scoring S definita sul risultato di join (cioè su una combinazione di preferenze, appartenenti a più relazioni collegate tra di loro tramite il join).
Il caso in cui siano presenti più relazioni, è assimilabile al caso in cui i risultati delle subquery provengano da fonti (data source) diverse. Parliamo in questo caso di middleware scenario:
- Abbiamo un numero > 1 di datasource
- Le query possono coinvolgere diverse data source allo stesso tempo
- Il risultato della query è ottenuto combinando il risultato ritornato dalle diverse sorgenti
Query di questo tipo sono dette middleware query, dato che richiedono la presenza di middleare (intermediare) tra utente/client e i vari data source/server.
È intuitivo il funzionamento per quanto riguarda i classici join, semplicemente ogni server effettua la subquery ed il mediatore accumula i vari risultati ed esegui il join, infine è lui a restituire il risultato al client.
Il funzionamento delle top-k middleware query (altro nome per top-k 1:1 join query) è meno immediato e necessita di algoritmi in grado di rendere efficiente il processo si sorting e limiting di dati provenienti da fonti diverse.
Quanto detto per le fonti diverse (su server diversi) vale anche per relazioni diverse, il funzionamento è identico.
Per trattare gli algoritmi presentati nel seguito è necessario introdurre una nuova terminologia per trattare le relazioni e le tuple.
Difatti d'ora in poi ogni input (relazione) sarà indicata con [m]L_i[/m], dove L sta per lista.
Inoltre non si lavorerà più con tuple, ma con oggetti. Questo perché è ragionevole dire che un oggetto o appartiene a due differenti input, mentre è errato dire lo stesso per una tupla.
Inoltre, onde evitare di dover leggere ogni oggetto di ogni input, è bene assumere che:
- Ogni input supporti un interfaccia ad accesso ordinato (s.a.)
getNext() -> (OID, attributes, pj)
Un accesso ordinato ottiene l'id del prossimo miglior oggetto secondo il suo score parziale pj (ovvero lo score che ottiene su quel determinato input seguendo una determinata scoring function parziale), assieme agli altri attributi richiesti per la query. - Ogni input supporti un interfaccia ad accesso casuale (r.a.)
getScore(OID) -> pj - L'OID sia globale, cioè identifichi lo stesso oggetto in ogni datasource (cosa ovvia nel caso locale, un po' meno nel caso distribuito)
- Ogni input comprende lo stesso set di oggetti. Se un oggetto è presenti nell'input [m]L_j[/m] dev'essere presente anche in ogni altro input. Altra assunzione che nel caso locale è banalmente verificta, nel caso globale è di più difficile trattazione.
Per cui supponiamo che ogni input sia una lista ordinata in base ad una determinata scoring function parziale (cioè la scoring function che considera solo gli attributi di ranking presenti su quell'input).
Inoltre, dobbiamo considerare che
- Una top-k 1:1 join query è formata da j subquery, fatta alle varie relazioni/datasource
- Ogni oggetto o ritornato dall'input Lj ha associato un punteggio locale /parziale [m]p_j(o) \in [0,1][/m], opportunamente normalizzato.
- Il punto [m]p(o) = (p_1(o), ... , p_m(o)) \in [0,1]^m[/m] rappresenta l'oggetto o nello spazio dei punteggi, in cui dunque un oggetto può essere rappresentato come un punto dell'ipercubo che identifica lo spazio dei punteggi (score space).
- Il punteggio totale/glogale S(o) dell'oggetto o è calcolato mediante una funzione di successo (scoring function) S che combina in qualche modo tutti i punteggi locali di o.
[math]S: [0,1]^m \rightarrow \mathbb{R} \\ S(o) = S(p(o)) = S(p_1(o),...,p_m(o))[/math]
Alcune delle scoring function più utilizzate sono:
- SUM (o AVG): si sommano i valori delle preferenze
- WSUM: somma attribuendo diversi pesi alle preferenze
- MIN: considera semplicemente il peggior punteggio parziale
- MAX: considera semplicemente il miglior punteggio parziale
NB: anche se si usa la funzione MIN, si vogliono sempre ottenere i k oggetti con il più alto punteggio globale.
Finalmente è possibile domandarsi: come è possibile calcolare in maniera efficiente una top-k 1:1 join query?
Abbiamo a disposizione diversi algoritmi, in cui un prerequisito fondamentale è che la scoring function utilizzata S sia monotona.
Questo perché aiutano ad effettuare considerazioni geometriche che permettono di ottimizzare gli algoritmi (non di poco) ed inoltre riflettono la realtà: infatti ci si aspetta migliorando la bontà di una determinata caratteristica, la bontà globale non risulti peggiore.
Nel seguito esamineremo gli algoritmi:
- [m]B_o[/m]: che permette in solo k iterazioni, di ottenere il risultato corretto da una top-k join 1:1 query se e solo se la funzione di scoring è MAX
- FA: che permette di ottenere il risultato corretto per qualsiasi funzione monotona S
- TA: che migliora FA, utilizzando il concetto di thresold (soglia). Evitando quindi iterazioni inutili.
- NRA: acronimo per Non Random Access, utilizzabile quando gli input non consentono accessi casuali (cioè non vi sono indici sulla relazione rappresentante l'input)
- CA: acronimo per Combined Algorith, che cerca di ridurre l'influenza negativa degli accessi casuali, combinando gli algoritmi precedenti.
Algoritmo [m]B_0[/m]
Questo algoritmo permette di ottenere il risultato della top k 1:1 join query calcolando i k valori migliori per ogni risorsa, a patto che la funzione di scoring globale usata sia MAX.
Inoltre, non effettua alcun accesso casuale.
Ricorare che stiamo supponendo che ogni lista ci fornisce l'oggetto ed il punteggio parziale assegnato. Punteggio parziale che identifica una preferenza.
Il funzionamento è semplice:
Predisponiamo un buffer B ed inizializziamo gli insiemi Obj(j) uno per ogni risorsa, vuoti.
Per ogni input j si tenta di riempire l'insieme associato utilizzando solamente il metodo getNext() (che in questo caso prende il nome di next_NN() in quanto ritorna il NN prossimo) fino ad averne k: ogni volta che trovo un oggetto (da una qualsiasi lista) controllo se l'avevo già incontrato ed in tal caso aggiungo all'oggetto anche il risultato parziale appena trovato, oppure lo inserisco bel buffer B.
Infine, per ogni oggetto che ho visto almeno una volta, ovvero che ha almeno un risultato parziale, calcolo la scoring function MAX su di esso e infine restituisco i primi k oggetti.
L'algoritmo [m]B_0[/m] adopera k accesso ordinati su ogni lista (k s.a. round) e successivamente calcola il risultato senza bisogna di ottenere i risultati parziali mancanti, quindi non è necessario alcun accesso casuale.
Questo algoritmo, funziona solo con la funzione di scoring MAX e la dimostrazione di ciò è dovuta a considerazioni geometriche.
In sostanza, la funzione MAX cerca il valore del punteggio totale maggiore. Questo significa che è come se effettuasse una scansione dei punti a partire dal punto [1,1] fino ad arrivare al punto [0,0].
Se troviamo un punto le cui preferenze si trovano in questa dirazione, il primo che troviamo è sicuramente quello con il punteggio globale MAX maggiore degli altri.
Per questo motivo non richiede nemmeno accessi casuali per poter ottenenere i rimanenti punteggi (magari troviamo per primo il punteggio lungo l'asse x, ma non lungo l'asse y. Questo non ci servirà se prima di incontrarlo troviamo altri k punti durante la scansione).
Algoritmo FA
L'algoritmo FA funziona con qualsiasi scoring function monotona. È un algoritmo in tre passi, il cui lato negativo è che utilizza S solo nell'ultimo passo, evitando ottimizzazioni.
- Fase 1: accede ad ogni lista in modalità round robin (accesso ordinato) e colleziona un insieme di k oggetti per i quali ha trovato almeno uno score parziale per lista.
- Fase 2: per ogni oggetto presente nell'insieme per il quale non conosco tutti gli score parziali effettuo accessi casuali alle liste che possono fornire i dati mancanti.
Al termina di questa fase abbiamo una lista completa di k elementi, frutto dell'accesso ordinato iniziale (e quindi i potenziali migliori) e dell'accesso casuale (per ottenere i dati completi) - Fase 3: calcola la scoring function S monotona per ogni oggetti presente nell'insieme, ed in base al punteggio ottenuto ordino i dati e li restituisce in output.
La scelta di utilizzare solo alla fine la funzione S ha come svantaggio quello di non produrre ottimizzazioni basate su questa, ma rende più flessibile l'algoritmo in quanto è possibile (avendo bufferizzato tutti i risultati richiesti) calcolare il risultati per una qualsiasi altra funzione S, in quanto del tutto generali non essendo collegati ad alcuna scoring function.
Algoritmo TA
È una specializzazione del FA, che fa uso del concetto di soglia per interrompere la ricerca.
Sfrutta la funzione S per il calcolo della soglia, quindi a differenza di FA non la utilizza solo all'ultimo passo d'esecuzione.
Anche in questo caso, l'algoritmo è abbastanza intuitivo.
- Calcolo la soglia come T = S(1,1,...,1), dove 1 è l'estremo sueriore di ogni coordinata.
- legge un oggetto per ogni lista Lj, ne calcola gli score parziali tramite accessi casuali alle altre liste e ne calcola lo score globale S(o).
Aggiunge l'oggetto alla lista del risultato, ordinata in base al punteggio ottenuto.
A seguito di ogni accesso ad ogni lista, aggiorna il valore del punteggio peggiore associato alla lista.
In seguito calcola la nuova soglia (che si sposta verso il basso) come [m]T = S(wp_1,wp_2,...,wp_m)[/m] dove [m]wp_j[/m] è il peggior punteggio incontrato nella lista j-esima. - Se il valore del k-esimo elemento della lista risultato è migliore del valore di soglia, allora si può interrompere l''iterazione in quanto nessun altro valore potrà entrare nella lista, a causa della monotonicità della funzione S
In generale TA funziona molto meglio di FA poiché riesce ad adattarsi alla specifica scoring function S.
Sicuramente è più efficiente di FA in quanto la condizione di stop di FA implica quella di TA.
In particolare è dimostrabile che FA è ottimale per le istanze (concetto più forte della semplice ottimalità nel caso peggiore).
Algoritmo NRA
È un algoritmo applicabile per qualsiasi funzione di scoring monotona S, nelle situazioni in cui non vi è possibile effettuare accessi casuali alle liste.
L'algoritmo ritorna i top-k oggetti, ma il loro punteggio potrebbe essere sbagliato, questo per limitare il costo dell'algoritmo stesso (nb: i punteggi sono errati, non la posizione).
L'idea dietro NRA è di mantenere un lower bound ed un upper bound per ogni oggetto incontrato, durante un accesso ordinato, sul loro punteggio.
Evidentemente bisogna scorrere la lista solo tramite accessi sequenziali e per ogni accesso fatto calcolare questi valori.
L'algoritmo si ferma quando nessun oggetto non appartenente al risultato, non può essere migliore di uno appartenente al risultato. Cioè quando [math]S^{+}(o') \le S^{-}(o) \forall o' \not{\in} Res, o \in Res[/math].
Cioè quando l'upper bound di un oggetto non presente nel risultato risulta minore o uguale al lower bound del k-esimo oggetto il Res (poiché Res è ordinata per valori di lower bound non crescenti).
In pratica l'algoritmo si ferma quando nessun oggetto che non è tra i primi k-oggetti (quindi quelli [m]\in Res[/m]) possa modificare Res.
Algoritmo CA
L'algoritmo CA è un tentativo di ridurre l'influenza negativa degli alti costi degli accessi casuali. L'idea dietro CA è semplice:
piuttosto che eseguire accessi casuali ad ogni round, li si esegue ogni [m]\frac{c_{RA}}{c_{SA}}[/m] round (con il numeratore = costo degli accessi casuali, e denominatore costo degli accessi sequenziali).
Nella pratica CA si comporta come NRA e mantiene per ogni oggetto incontrato un lower ed upper bound sui punteggi, inoltre ogni [m]\frac{c_{RA}}{c_{SA}}[/m] round ne esegue uno casuale.
Il punto chiave sta nella scelta relativa a quali oggetti è necessario richiedere l'accesso casuale.
L'euristica applicata è quella di scegliere gli oggetti o per i quali mancano alcuni risultati parziali e per i quali l'upper bound è massimo (cioè si scelgono i più promettenti).