| Risoluzione di
query approssimate |
Paolo Ciaccia e Marco Patella
Descrizione
Il prototipo realizzato estende la libreria M-tree implementando gli
algoritmi PAC (Probabilmente Approssimativamente Corretti) per la
risoluzione di query di similarità dettagliati nel prodotto D3.R3
(parte III). Tali algoritmi garantiscono la possibilità, in fase di
interrogazione, di controllare in maniera probabilistica l’approssimazione
del risultato e di ottenere, quindi, un compromesso tra velocità di
risoluzione della query e qualità del risultato.
È stato considerato lo
scenario generale degli spazi metrici, in cui ad ogni query di similarità
corrisponde un'interrogazione di prossimità. In particolare, sono state
considerate query di
range (con le quali si cercano tutti i punti
aventi una distanza dal punto query minore di una soglia) e
k nearest
neighbor (per le quali sono richiesti i
k punti più vicini al
punto query).
L'utilizzo degli algoritmi PAC richiede una definizione di un errore
ERR sul risultato della query. Per le query di range tale errore è
definito sulla cardinalità dell'insieme risultato, in quanto il risultato
approssimato può escludere alcuni punti che soddisfano la query; per le
query k-NN, invece, l'errore è definito sulla distanza di ciascuno dei
k punti dalla query. In ogni caso, dato il valore per i due
parametri di precisione e e confidenza d, gli algoritmi garantiscono che l'errore ERR non
superi il valore e per più di una frazione d dei casi. Per garantire ciò gli algoritmi sfruttano
(un campione del) la distribuzione delle distanze F(x), che definisce la
probabilità che la distanza di un punto dalla query sia minore o uguale a
x: F(x) = Pr{d(q,p)<=x}.
Ambiente di sviluppo e di esecuzione
Sviluppato in
C++.
Richiede la libreria GiST 0.9.
Back