Marcus Fontoura
Vanja Josifovski
Ravi Kumar
Christopher Olston
Sergei Vassilvitskii
Relaxation in Text Search using Taxonomies
Gruppo 16
Luca Bueti (relatore)
Jacopo De Benedetto
Information Retrieval
• Scenario tipico: ranking dei
risultati
• Modelli esistenti
consentono alcune
estensioni
• Nuove problematiche
(local search, multifaceted
product search) richiedono
nuovi modelli di query
processing
Gruppo 16 - Relaxation in Text Search using Taxonomies
2
Rilassamenti multidimensionali

Possibili formulazioni:
Rilassamento di
neluna
riconoscimento
posizione attraverso
di una frase
una sfera
usando
di
raggio
misurecrescente
linguistiche di similarità (es.: STEMMING)
a
aaron
abaissiez
abandon
abandoned
abase
abash
abate
abated
abatement
abatements
abates
abbess
abbey
abbeys
Gruppo 16 - Relaxation in Text Search using Taxonomies
a
aaron
abaissiez
abandon
abandon
abas
abash
abat
abat
abat
abat
abat
abbess
abbei
abbei
3
Rilassamenti multidimensionali
Rilassamento attraverso gerarchie multiple
Principali ragioni:


Descrivono meglio la maggior parte dei
rilassamenti
Possono essere viste come generalizzazione della
maggior parte dei rilassanti

Permettono di formulare il problema in modo
combinatorio
Gruppo 16 - Relaxation in Text Search using Taxonomies
4
Tassonomia
Classificazione gerarchica
“Secondo la matematica, una tassonomia è una struttura
ad albero di istanze (o categorie) appartenenti ad un dato
gruppo di concetti. A capo della struttura c'è un'istanza
singola, il nodo radice, le cui proprietà si applicano a tutte
le altre istanze della gerarchia (sotto-categorie).
I nodi sottostanti a questa radice costituiscono categorie più
specifiche le cui proprietà caratterizzano il sotto-gruppo del
totale degli oggetti classificati nell'intera tassonomia” Wikipedia
Gruppo 16 - Relaxation in Text Search using Taxonomies
5
Tassonomia
Nel nostro caso definiamo una tassonomia come un
albero i cui rami hanno un peso non negativo:
Attività
Commerciale
BO
4
6
Bologna
4
6
Imola …
5
3
Saragozza San Donato …
2
2
2
Cinese …
Italiano
1
Via
Via Turati …
Saragozza
…
Ristorante
Pizzeria
Gruppo 16 - Relaxation in Text Search using Taxonomies
1
Trattoria
…
6
Background

Inverted index (& posting lists)

Free-text queries (DAAT, zig-zag join)

Scoring
Gruppo 16 - Relaxation in Text Search using Taxonomies
7
Background

Inverted index (& posting lists)
Gruppo 16 - Relaxation in Text Search using Taxonomies
8
Background

Free-text queries (DAAT, zig-zag join)
“Turtle and Flood classify evaluation strategies into two main
classes:
• Term-at-a-time (TAAT ) strategies process query terms one by
one and accumulate partial document scores as the contribution
of each query term is computed.
• Document-at-a-time (DAAT ) strategies evaluate the
contributions of every query term with respect to a single
document before moving to the next document.“
A. Z. Broder, D. Carmel, M. Herscovici, A. Soffer, and J. Y. Zien. Efficient query
evaluation using a two-level retrieval process. In Proc. 12th ACM CIKM, 2003.
Gruppo 16 - Relaxation in Text Search using Taxonomies
9
Background

Free-text queries (DAAT, zig-zag join)
In DAAT, i documenti che soddisfano la query sono spesso ottenuti attraverso un
zig-zag join sulle posting lists dei termini della query.
A tal fine viene creato un cursore Ct per ogni termine t della query usato per
accedere alla t-esima posting list.
Ct.docid e Ct.payload accedono rispettivamente al docid e al payload del posting
su cui Ct è posizionato.
Durante uno zig-zag join i cursori vengono spostati in maniera coordinata per
trovare documenti che soddisfano la query.
Operazioni sul cursore Ct:
–
Ct.getNext()
avanza il cursore C al posting successivo nella posting list;
–
Ct.fwdBeyond(d) avanza il cursore C al primo posting nella posting list il cui
docid è maggiore o uguale a quello del documento d (le
posting lists devono essere ordinate per docid).
Gruppo 16 - Relaxation in Text Search using Taxonomies
10
Background

Scoring
static(d) indica lo score
query-indipendent
relativo alla
”importanza” del
documento d (es.:
PageRank)
tax(d,topic(Q)) indica lo score
rispetto alla tassonomia (es.:
un insieme dei costi di
rilassamento per il documento
d rispetto ad una lista di nodi di
tassonomia topic(Q))
scored , Q    staticd     textd , keywQ    taxd , topicQ
text(d,keyw(Q)) indica la
rilevanza text-based del
documento d rispetto alle
keywords della query Q
nota: per tutti i componenti dello score, minore è il valore, migliore è il risultato;
α, β e γ sono pesi assegnati ai diversi componenti dello score assegnati da un esperto del dominio
Gruppo 16 - Relaxation in Text Search using Taxonomies
11
Un po' di formule...

Tassonomia T, documento d, query Q

T1, … , Tm tassonomie

topic(d) ϵ T1 indica che ogni documento d è associato
esattamente ad un nodo della tassonomia

topicj(d) ϵ Tj indica che il nodo della j-esima tassonomia è
associato al documento d

keyw(Q) indica le parole chiave contenute nella query
Gruppo 16 - Relaxation in Text Search using Taxonomies
12
...quasi finito
• Lo score relativo alla tassonomia è BO
definito come la somma degli score
in ogni tassonomia presente

   tax j topic




taxd , topicQ Bologna
d
,
topic
Q
j
j
Imola
m
j 1
• Lo score di ogni tassonomia è la somma dei pesi lungo il cammino tra
due nodi
SaragozzaSan Donato …
tax j topic j s , topic j Q   wdist j topic j Q , lca topic j Q , topic j d 
wdist (nodeA, nodeB) è la
Via
Via
Turati
somma
dei costi di …
Saragozzarilassamento lungo il cammino
j
tra i nodi A e B della
tassonomia Tj
dove lca sta per least(lowest)-common ancestor
Gruppo 16 - Relaxation in Text Search using Taxonomies
13
Problematiche
• Creazione della tassonomia e selezione dei pesi
appropriati
• Mappaggio nella tassonomia dei termini della query,
dei documenti e delle informazioni dell’utente
• Efficiente indicizzazione e processamento della query
Gruppo 16 - Relaxation in Text Search using Taxonomies
14
Approccio
APPROCCIO CLASSICO
Processamento della query attraverso text-matching e
utilizzo dei meta-dati (tassonomia) nella fase di postprocessing
META-DATI
http://www.esempio1.it
http://www.esempio2.it
http://www.esempio3.it
http://www.esempio4.it
http://www.esempio5.it
Gruppo 16 - Relaxation in Text Search using Taxonomies
15
Approccio
APPROCCIO UTILIZZATO
Estensione dell'indice di testo per includere anche i nodi
della tassonomia e processamento simultaneo delle
porzioni di testo e tassonomia della query attraverso
l'indice
OTTIMIZZAZIONE DELLA RICERCA
http://www.esempio2.it
http://www.esempio3.it
http://www.esempio4.it
Gruppo 16 - Relaxation in Text Search using Taxonomies
16
Approccio Utilizzato
• Viene creata una posting list per ogni nodo della
tassonomia
• In fase di processamento della query vengono
selezionati i nodi iniziali e si incomincia a scorrere
le loro posting lists alla ricerca dei risultati
• Viene adattato dinamicamente il livello di
rilassamento per cercare risultati con score
migliore
Gruppo 16 - Relaxation in Text Search using Taxonomies
17
Index structure



Una posting list addizionale per ogni nodo della
tassonomia
Ognuna di queste posting list contiene una entry per ogni
documento appartenente al corrispondente sotto-albero
del nodo della tassonomia
I payloads di queste posting list identificano l'esatta
posizione del documento nella tassonomia corrispondente
Gruppo 16 - Relaxation in Text Search using Taxonomies
18
Index structure
d1(Saragozza, Cinese)
d2(Via Saragozza, Pizzeria)
d3(Saragozza, Trattoria)
d4(San Donato, Italiano)
BO
Imola
…
Saragozza San Donato
…
Bologna
Via Saragozza
Via Turati
OVERHEAD
Inferiore all'1% !!!
…
d1(Saragozza) d2(Via
d3(Saragozza)
Saragozza)
Saragozza
Gruppo 16 - Relaxation in Text Search using Taxonomies
19
d1(Saragozza, Cinese)
d2(Via Saragozza, Pizzeria)
Index structure
d3(Saragozza, Trattoria)
Attività Commerciale
d4(Pilastro, Italiano)
Ristorante …
BO
Imola
…
Saragozza San Donato
…
Bologna
Via Saragozza
Via Turati
Italiano
Pizzeria
…
d1(Cinese)
Cinese
Trattoria
…
…
d2(Pizzeria)
d3(Trattoria)
d4(Italiano)
d2(Pizzeria)
d3(Trattoria)
d4(Italiano)
d2(Pizzeria)
d3(Trattoria)
d4(Italiano)
Attività Commerciale
d1(Saragozza) d2(Via Saragozza)
d3(Saragozza)
d4(San Donato)
BO
d1(Cinese)
Ristorante
d1(Saragozza) d2(Via Saragozza)
d3(Saragozza)
d4(San Donato)
Bologna
Italiano
d1(Saragozza) d2(Via Saragozza)
d3(Saragozza)
d1(Cinese)
Saragozza
Cinese
d4(San Donato)
San Donato
d2(Pizzeria)
Pizzeria
d2(Via Saragozza)
Via Saragozza
d3(Trattoria)
Trattoria
Query processing
OBIETTIVO
trovare i k documenti di minor costo
secondo la scoring function definita
scored , Q    staticd     textd , keywQ    taxd , topicQ
IPOTESI SEMPLIFICATIVA: il costo del risultato corrisponde solo al costo di rilassamento.
Gruppo 16 - Relaxation in Text Search using Taxonomies
21
Decomposizione del problema
SOTTO-PROBLEMI:
determinare il budget minimo di rilassamento
per ottenere almeno k risultati
→
Top-k relaxation search

Ottenere i k risultati con il minimo sforzo
computazionale
→
Budgeted relaxation search

Gruppo 16 - Relaxation in Text Search using Taxonomies
22
Decomposizione del problema
SOTTO-PROBLEMI:
determinare il budget minimo di rilassamento
per ottenere almeno k risultati
→
Top-k relaxation search

Ottenere i k risultati con il minimo sforzo
computazionale
→
Budgeted relaxation search

Gruppo 16 - Relaxation in Text Search using Taxonomies
23
Top-k relaxation search
Spazio dei possibili rilassamenti
Q=“Via Saragozza AND Pizzeria”
T2
Attività
commerciale
S(b) indica il simplesso
generato dal vincolo sul
costo di rilassamento
Cost ≤ b
Cost ≤ 10
6
docs(S(b)) indica tutti i
documenti contenuti
all’interno del simplesso
S(b), ovvero tutti i
documenti ottenibili con
costo di rilassamento
non superiore a b
S(10)
Ristorante
S(4)
3
Cost ≤ 4
Italiano
1
Pizzeria
2 Quartiere
Via
Saragozza Saragozza
4
Bologna
4
BO
T1
Top-k relaxation search
OBIETTIVO
trovare il budget minimo di rilassamento b* per cui
|docs(S(b*))| ≥ k
ALGORITMO BASE: ConservativeSearch
1. l = initialLevel();
2. levelDone = false;
3. while (|R|<k) v !levelDone)
4. levelDone = processNextDoc(Q,R,bl);
5. if((|R|>=k) v levelDone)
6.
l = getNextLevel(l);
NOTA: Per livello si intende il costo totale di rilassamento, ovvero la somma dei costi dei
rilassamenti in tutte le tassonomie.
Gruppo 16 - Relaxation in Text Search using Taxonomies
25
Strategie di ricerca
OBIETTIVO
trovare i k documenti di minor costo
Bottom-up search
• Si parte dalla query più specifica possibile, ad esempio
Q=(Via Saragozza, Pizza);
• se troviamo almeno k documenti, fine. Altrimenti:
• rilassiamo incrementando il livello.
Top-down search
• Si parte dal livello più generale possibile (l=L);
• se troviamo non più di k documenti, fine. Altrimenti:
• specializziamo per ottenere k documenti con score migliore (nota:
non vengono persi i risultati ottenuti finora).
Binary search
• Si parte dal livello intermedio (l=L/2);
• a seconda del numero di documenti trovati, ci sposteremo più in alto o
più in basso nei livelli.
Gruppo 16 - Relaxation in Text Search using Taxonomies
26
Strategie di ricerca
OBIETTIVO
trovare i k documenti di minor costo
Bottom-up search
• Si parte dalla query più specifica possibile, ad esempio
Q=(Via Saragozza, Pizza);
• se troviamo almeno k documenti, fine. Altrimenti:
• rilassiamo incrementando il livello.
Top-down search
• Si parte dal livello più generale possibile (l=L);
• se troviamo non più di k documenti, fine. Altrimenti:
• specializziamo per ottenere k documenti con score migliore (nota:
non vengono persi i risultati ottenuti finora).
Binary search
• Si parte dal livello intermedio (l=L/2);
• a seconda del numero di documenti trovati, ci sposteremo più in alto o
più in basso nei livelli.
Gruppo 16 - Relaxation in Text Search using Taxonomies
27
Strategie di ricerca
Bottom-up search
d1(Saragozza, Cinese)
d2(Via Saragozza, Pizzeria)
Q=(Via Saragozza, Pizza)
k=2
d3(Saragozza, Trattoria)
d2(Via Saragozza)
d4(San Donato, Italiano)
Via Saragozza
level = 0
BO
4
T1
6
Bologna
4
Imola
2
Pizzeria
…
5
Saragozza San Donato
d2(Pizzeria)
…
# cursor movements: 8
d2(Via Saragozza)
2
Via Saragozza
…
Via Turati
Via Saragozza
level = 1
d2(Pizzeria)
d3(Trattoria)
d4(Italiano)
Italiano
Attività Commerciale
6
T2
Ristorante …
Italiano
1
Pizzeria
d1(Saragozza) d2(Via Saragozza)
2
3
Cinese
Trattoria
Saragozza
…
level = 3
1
…
d3(Saragozza)
d2(Pizzeria)
Italiano
d3(Trattoria)
d4(Italiano)
Strategie di ricerca
OBIETTIVO
trovare i k documenti di minor costo
Bottom-up search
• Si parte dalla query più specifica possibile, ad esempio
Q=(Via Saragozza, Pizza);
• se troviamo almeno k documenti, fine. Altrimenti:
• rilassiamo incrementando il livello.
Top-down search
• Si parte dal livello più generale possibile (l=L);
• se troviamo non più di k documenti, fine. Altrimenti:
• specializziamo per ottenere k documenti con score migliore (nota:
non vengono persi i risultati ottenuti finora).
Binary search
• Si parte dal livello intermedio (l=L/2);
• a seconda del numero di documenti trovati, ci sposteremo più in alto o
più in basso nei livelli.
Gruppo 16 - Relaxation in Text Search using Taxonomies
29
getNextLevel(10)…????????
Nessun documento non appartenente al sottoalbero
“Bologna” o “Ristorante” potrà entrare nel ResultSet,
perché avrà un costo > 6
 il costo di un documento associato
aiSaragozza,
nodi Bologna
Q=(Via
Pizza)
in T1 e Ristorante in T2 è pari a 10
k=2
Strategie di ricerca
Top-down search
d1(Saragozza, Cinese)
d2(Via Saragozza, Pizzeria)
d3(Saragozza, Trattoria)
d1(Saragozza) d2(Via Saragozza)
d4(San Donato, Italiano)
d3(Saragozza)
d4(Pilastro)
d3(Trattoria)
d4(Italiano)
d3(Saragozza)
d4(Pilastro)
BO
level = 20
BO
4
T1
6
Bologna
4
Imola
2
…
…
# cursor movements: 7
d1(Saragozza) d2(Via Saragozza)
Bologna
2
Via Saragozza
d2(Pizzeria)
Attività Commerciale
5
Saragozza San Donato
d1(Cinese)
…
Via Turati
Già processati tutti i documenti con docid<3
level = 10
d1(Cinese)
d2(Pizzeria)
d3(Trattoria)
d4(Italiano)
Ristorante
Attività Commerciale
6
T2
Ristorante …
Italiano
1
Pizzeria
d1(Saragozza) d2(Via Saragozza)
2
3
Cinese
1
Trattoria
…
Saragozza
level = 3Nessun documento con
docid>3
d2(Pizzeria)
…
d3(Saragozza)
Italiano
d3(Trattoria)
d4(Italiano)
Strategie di ricerca
OBIETTIVO
trovare i k documenti di minor costo
Bottom-up search
• Si parte dalla query più specifica possibile, ad esempio
Q=(Via Saragozza, Pizza);
• se troviamo almeno k documenti, fine. Altrimenti:
• rilassiamo incrementando il livello.
Top-down search
• Si parte dal livello più generale possibile (l=L);
• se troviamo non più di k documenti, fine. Altrimenti:
• specializziamo per ottenere k documenti con score migliore (nota:
non vengono persi i risultati ottenuti finora).
Binary search
• Si parte dal livello intermedio (l=L/2);
• a seconda del numero di documenti trovati, ci sposteremo più in alto o
più in basso nei livelli.
Gruppo 16 - Relaxation in Text Search using Taxonomies
31
Strategie di ricerca
Binary search
d1(Saragozza, Cinese)
d2(Via Saragozza, Pizzeria)
Q=(Via Saragozza, Pizza)
k=2
d3(Saragozza, Trattoria)
d4(San Donato, Italiano)
BO
4
T1
6
Bologna
4
Imola
5
Saragozza San Donato
2
…
…
d2(Via Saragozza)
d3(Saragozza)
d4(Pilastro)
k=2 ma d1(Saragozza)
non possiamo
specializzare
Ora
sappiamo che
nessun
nuovo
documento
Bologna
ulteriormente
senza
rischiare
di perdere
risultati
potrà
avere
costo
>
3
per
entrare
nel
ResultSet
level = 
10 continuiamo con la stessa posting list
d1(Cinese)
d2(Pizzeria)
d3(Trattoria)
d4(Italiano)
Ristorante
# cursor movements:
7
2
Via Saragozza
…
Via Turati
d1(Saragozza) d2(Via Saragozza)
Attività Commerciale
T2
Ristorante …
Italiano
1
Pizzeria
Cinese
1
Trattoria
…
d2(Pizzeria)
Italiano
2
3
Saragozza
Nessun documento con docid>3
level = 3
6
…
d3(Saragozza)
d3(Trattoria)
d4(Italiano)
Strategie di ricerca
Confronto
Bottom Up search
PRO: Funziona bene se ci sono molti documenti che fanno match con la query,
richiedendo poco rilassamento
CONTRO: A ogni rilassamento rielabora, oltre ai nuovi, gli stessi documenti del passaggio
precedente
Top Down search
PRO: Funziona bene se è necessario rilassare molto la query per ottenere k documenti;
i risultati accumulati vengono mantenuti durante l’esplorazione della tassonomia;
permette di accumulare statistiche necessarie per l’esecuzione della budgeted search
(stima dei costi di esecuzione delle query)
CONTRO: Poco efficace se esistono molti documenti specifici che fanno match con la
query
Binary search
PRO: Utile se non si hanno informazioni sulla distribuzione dei documenti nelle
tassonomie
CONTRO: Apparentemente nessuno …
Gruppo 16 - Relaxation in Text Search using Taxonomies
33
Decomposizione del problema
SOTTO-PROBLEMI:
determinare il budget minimo di rilassamento
per ottenere almeno k risultati
→
Top-k relaxation search

Ottenere i k risultati con il minimo sforzo
computazionale
→
Budgeted relaxation search

Gruppo 16 - Relaxation in Text Search using Taxonomies
34
Budgeted relaxation search
OBIETTIVO
Ottenere tutti i documenti con costo di
rilassamento cost ≤ b con il minimo sforzo
computazionale


ALGORITMO RISOLUTIVO
2 tassonomie → esiste algoritmo efficiente di
programmazione dinamica
3 o più tassonomie → problema NP-difficile
Gruppo 16 - Relaxation in Text Search using Taxonomies
35
Budgeted relaxation search
• 2 tassonomie
Bx0   min Cx, S b, x0   Bnextx 
x x0
T2
Cx, y   costo di esecuzione della query (x,y)
x, S b, x
docsx' , y'  docs( x, y)
Nota: x'  x, y '  y
y
y'
T1
x' x
Gruppo 16 - Relaxation in Text Search using Taxonomies
36
Budgeted relaxation search
• 2 tassonomie
Bx0   min Cx, S b, x0   Bnextx 
x x0
T2
nodo successivo lungo il cammino verso la
next(x)  radice della tassonomia
C x, S b, x0 
Bnext(x)
T1
x
next(x)
Gruppo 16 - Relaxation in Text Search using Taxonomies
37
Budgeted relaxation search
• 2 tassonomie
Bx0   min Cx, S b, x0   Bnextx 
T2
x x0
C x, S b, x0 
Bnext(x)
T1
x
next(x)
Gruppo 16 - Relaxation in Text Search using Taxonomies
38
Budgeted relaxation search
• 2 tassonomie
Bx0   min Cx, S b, x0   Bnextx 
x x0
T2
C x, S b, x0 
Bnext(x)
x
•
T1
next(x)
Gruppo 16 - Relaxation in Text Search using Taxonomies
39
Budgeted relaxation search
• 2 tassonomie
Bx0   min Cx, S b, x0   Bnextx 
x x0
T2
C x, S b, x0 
Bnext(x)
T1
x
Gruppo 16 - Relaxation in Text Search using Taxonomies
40
Budgeted relaxation search
Falsi positivi
T2
Falsi positivi
T2
2 volte
3 volte
T1
Gruppo 16 - Relaxation in Text Search using Taxonomies
T1
41
Budgeted relaxation search
• 3 o più tassonomie
• Si dimostra che il Set Covering Problem (NP-difficile, come
dimostrato da Fowler et al.) è riconducibile al problema in
esame, il quale è quindi di NP-difficile
• Per la soluzione del Set Covering Problem esistono efficienti
algoritmi approsimati: sia n il numero totale di documenti con
costo di rilassamento abbastanza basso, il “greedy set cover
algorithm” può ottenere una approssimazione del problema di
query planning con complessità O(log n)
…(per chi fosse interessato all’argomento consigliamo il corso: “Algoritmi di
Ottimizzazione LS” del prof. P. Toth)
Gruppo 16 - Relaxation in Text Search using Taxonomies
42
Risultati sperimentali
Baseline algorithm: recupera i documenti che soddisfano la parte
testuale della query e utilizza i metadati della tassonomia per postprocessare i documenti e calcolarne lo score finale. Questo
algoritmo rappresenta una diretta applicazione del processamento
IR standard al nostro contesto, ovvero le tassonomie non vengono
sfruttate durante la fase di query processing
Per ottenere indipendenza da dettagli di basso livello (come hardware,
compressione delle posting lists, ecc.), gli autori utilizzano come
misura delle prestazioni degli algoritmi il numero degli spostamenti
del cursore, ovvero il numero delle entry delle postings list accedute
dalle chiamate del zig-zag join
Gruppo 16 - Relaxation in Text Search using Taxonomies
43
Risultati sperimentali
Analisi delle prestazioni al variare di:
• # taxonomy restrictions: numero delle tassonomie
• depth: profondità della tassonomia
• fanout: fattore di ramificazione della tassonomia
• selectivity of keywords: 1=tutti i documenti contengono le
keywords o la query non specifica keywords
• # number of results (k): numero di risultati richiesti
Le tassonomie degli esperimenti sono alberi bilanciati con fanout e
depth variabili. Ogni tassonomia ha profondità fissata d e fanout f
I risultati terranno conto solo delle restrizioni testuali e di tassonomia
delle query (no text-independent score)
Gruppo 16 - Relaxation in Text Search using Taxonomies
44
One query per level
Si assume che ad ogni livello della tassonomia,
i documenti vengano recuperati attraverso un’unica interrogazione
depth=4; fanout=2
1
depth=8; fanout=2
1.2
# cursor movements
# cursor movements
1
0.1
0.8
0.6
0.4
0.2
0.01
0
1
2
3
4
1
# taxonomy restrictions
2
3
4
# taxonomy restrictions
Per fanout bassi, nessun algoritmo fa peggio del baseline e binary search in alcuni casi
migliora le prestazioni di molto.
Gruppo 16 - Relaxation in Text Search using Taxonomies
45
One query per level
depth=4; fanout=6
depth=8; fanout=6
1.6
1.4
1.4
1.2
1.2
# cursor movements
# cursor movements
1.6
1
0.8
0.6
0.4
0.2
1
0.8
0.6
0.4
0.2
0
1
2
3
4
0
1
# taxonomy restrictions
2
3
4
# taxonomy restrictions
Per fanout e numero di tassonomie più alti, il miglior algoritmo di ricerca è quello topdown, che non fa mai peggio del baseline e, in alcuni casi, fa molto meglio. Nelle stesse
condizioni gli altri algoritmi non riescono a migliorare il baseline e, in alcuni casi, fanno
peggio.
Gruppo 16 - Relaxation in Text Search using Taxonomies
46
Dati reali
Reuters dataset RCV1 contenente articoli di
giornale in lingua inglese dal 20-08-1996 al
19-08-1997.
Dimensione dei dati non compressa: 2.5GB
Documenti classificati in 2 tassonomie:
1. “industry” taxonomy: 996 foglie, profondità
max 7
2. “date taxonomy”: 3 livelli (anno, mese,
giorno)
Average number of cursor movements
Algorithm
Number of results
k=10
baseline
k=100
11277
bottom up
819
1582
top down
61
242
binary search
62
242
depth=4; fanout=2; #taxonomies=2
# cursor movements (baseline=1)
10
Top-down ha ottime prestazione, in
particolare perché la seconda tassonomia è
poco profonda.
Binary search è alla pari e potrebbe essere più
robusta per tassonomie più profonde.
Entrambe le strategie migliorano di gran lunga
le prestazioni di baseline e bottom up.
1
0.1
0.001
baseline
bottom up
top down
0.01
0.1
1
keyword selectivity
Gruppo 16 - Relaxation in Text Search using Taxonomies
47
Multiple queries per level
Si effettuano più query secondo la stima dei costi ottenuta (budgeted search). Se non sono
disponibili stime, allora i costi di qualunque query vengono assunti identici.
Binary search: depth=4; fanout=2; #taxonomies=2
10000000
# cursor movements (absolute)
depth=4 (multi)
depth=4 (single)
1000000
depth=8 (multi)
depth=8 (single)
100000
10000
1000
2
4
6
8
fanout
Dalla figura si può vedere che per profondità e fanout maggiori, i benefici
che si hanno dalla esecuzione di query multiple aumentano.
Gruppo 16 - Relaxation in Text Search using Taxonomies
48
GRAZIE PER L’ATTENZIONE
Gruppo 16 - Relaxation in Text Search using Taxonomies
49