Marcus Fontoura Vanja Josifovski Ravi Kumar Christopher Olston Sergei Vassilvitskii

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

2Gruppo 16 - Relaxation in Text Search using Taxonomies

Rilassamenti multidimensionaliPossibili formulazioni:

Rilassamento nel riconoscimento di una frase usando misure linguistiche di similarità (es.: STEMMING)

Rilassamento di una posizione attraverso una sfera di raggio crescente

aaaron

abaissiezabandon

abandonedabaseabashabate

abatedabatementabatements

abatesabbessabbeyabbeys

aaaron

abaissiezabandonabandon

abasabashabatabatabatabatabat

abbessabbeiabbei


Rilassamenti multidimensionaliRilassamento 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


TassonomiaClassificazione 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


TassonomiaNel nostro caso definiamo una tassonomia come un

albero i cui rami hanno un peso non negativo:

BO

Bologna Imola

Saragozza San Donato

Via Saragozza

Via Turati

…

…

4 6

4 5

2 2

Attività Commerciale

Ristorante …

Italiano Cinese

Pizzeria Trattoria

…

6

3 2

1 1

… …


Background

Inverted index (& posting lists)

Free-text queries (DAAT, zig-zag join)

Scoring


Background

Inverted index (& posting lists)


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.


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).


Background Scoring

QtopicdtaxQkeywdtextdstaticQdscore ,,,

static(d) indica lo score query-indipendent

relativo alla ”importanza” del

documento d (es.: PageRank)

text(d,keyw(Q)) indica la rilevanza text-based del

documento d rispetto alle keywords della query Q

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))

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

new


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


...quasi finito

dove lca sta per least(lowest)-common ancestor

m

jjjj QtopicdtopictaxQtopicdtax

1

,,

dtopicQtopiclcaQtopicwdistQtopicstopictax jjjjjjj ,,,

BO

Bologna Imola

SaragozzaSan Donato

Via Saragozza

Via Turati

…

…wdistj(nodeA, nodeB) è la

somma dei costi di rilassamento lungo il

cammino tra i nodi A e B della tassonomia Tj

• Lo score relativo alla tassonomia è definito come la somma degli score in ogni tassonomia presente

• Lo score di ogni tassonomia è la somma dei pesi lungo il cammino tra due nodi


Problematiche

• Efficiente indicizzazione e processamento della query

• Creazione della tassonomia e selezione dei pesi appropriati

• Mappaggio nella tassonomia dei termini della query, dei documenti e delle informazioni dell’utente


ApproccioAPPROCCIO CLASSICO

Processamento della query attraverso text-matching e utilizzo dei meta-dati (tassonomia) nella fase di post-processing

http://www.esempio1.ithttp://www.esempio2.ithttp://www.esempio3.ithttp://www.esempio4.ithttp://www.esempio5.it


http://www.esempio1.it/





ApproccioAPPROCCIO 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'indiceOTTIMIZZAZIONE DELLA RICERCA

http://www.esempio2.ithttp://www.esempio3.ithttp://www.esempio4.it





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


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


Index structure

OVERHEADInferiore all'1% !!!

d1(Saragozza, Cinese)

d2(Via Saragozza, Pizzeria)

d3(Saragozza, Trattoria)

d4(San Donato, Italiano)

BO

Bologna Imola

San Donato

Via Saragozza Via Turati

…

Saragozza

…

…

Saragozza

d1(Saragozza) d3(Saragozza)d2(Via Saragozza)


Index structured1(Saragozza, Cinese)



d4(Pilastro, Italiano)

BO

Bologna Imola

San Donato


…

Saragozza

…

…

BO


Bologna


Saragozza



Ristorante

Cinese

Pizzeria Trattoria

…

Italiano

…

…

San Donato

Via Saragozza

d2(Via Saragozza)

d4(San Donato)

d4(San Donato)

d4(San Donato)


d1(Cinese) d3(Trattoria)d2(Pizzeria) d4(Italiano)


d3(Trattoria)d2(Pizzeria) d4(Italiano)

d1(Cinese)

d2(Pizzeria)

d3(Trattoria)

Ristorante

Italiano

Cinese

Pizzeria

Trattoria

Query processing

OBIETTIVOtrovare i k documenti di minor costo

secondo la scoring function definita

QtopicdtaxQkeywdtextdstaticQdscore ,,,

IPOTESI SEMPLIFICATIVA: il costo del risultato corrisponde solo al costo di rilassamento.


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 search22Gruppo 16 - Relaxation in Text Search using Taxonomies


SOTTO-PROBLEMI:





Top-k relaxation searchSpazio dei possibili rilassamenti

BOBolognaQuartiereSaragozza

ViaSaragozza

Attivitàcommerciale

Ristorante

Italiano

Pizzeria

Cost ≤ 10

Cost ≤ 4

Q=“Via Saragozza AND Pizzeria”

1

2

3

6

4 4T1

T2

S(4)

S(10)

S(b) indica il simplesso generato dal vincolo sul costo di rilassamento Cost ≤ b

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

Top-k relaxation searchOBIETTIVO

trovare il budget minimo di rilassamento b* per cui |docs(S(b*))| ≥ k

ALGORITMO BASE: ConservativeSearch1. 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.


Strategie di ricerca

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.



Strategie di ricercaBottom-up searchd1(Saragozza, Cinese)




BO

Bologna Imola

San Donato


…

Saragozza

…

…

T14 6

4 5

2 2


Ristorante

Cinese

Pizzeria Trattoria

…

Italiano

…

…

T2

6

3 2

1 1

d2(Pizzeria)

Pizzeria

Via Saragozza

d2(Via Saragozza)

level = 0

Via Saragozza

d2(Via Saragozza)

level = 1d3(Trattoria)d2(Pizzeria) d4(Italiano)

Italiano


Italiano

Saragozza


# cursor movements: 8

Q=(Via Saragozza, Pizza)k=2

Strategie di ricercaTop-down search


Ristorante

Cinese

Pizzeria Trattoria

…

Italiano

…

…

T2

6

3 2

1 1

level = 20

BO

d1(Saragozza) d3(Saragozza)d2(Via Saragozza) d4(Pilastro)



level = 10

Bologna



Ristorante

Già processati tutti i documenti con docid<3


Italiano

Saragozza


Nessun documento con docid>3



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 ai nodi Bologna in T1 e Ristorante in T2 è pari a 10





BO

Bologna Imola

San Donato


…

Saragozza

…

…

T14 6

4 5

2 2

Strategie di ricercaBinary search


Ristorante

Cinese

Pizzeria Trattoria

…

Italiano

…

…

T2

6

3 2

1 1


level = 10

Bologna



Ristorante


Italiano

Saragozza


Nessun documento con docid>3

k=2 ma non possiamo specializzare ulteriormente senza rischiare di perdere risultati continuiamo con la stessa posting list

Ora sappiamo che nessun nuovo documento potrà avere costo > 3 per entrare nel ResultSet






BO

Bologna Imola

San Donato


…

Saragozza

…

…

T14 6

4 5

2 2

Strategie di ricercaConfronto

Bottom Up searchPRO: Funziona bene se ci sono molti documenti che fanno match con la query,

richiedendo poco rilassamentoCONTRO: A ogni rilassamento rielabora, oltre ai nuovi, gli stessi documenti del passaggio

precedente

Top Down searchPRO: 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 searchPRO: Utile se non si hanno informazioni sulla distribuzione dei documenti nelle

tassonomieCONTRO: Apparentemente nessuno …



SOTTO-PROBLEMI:





Budgeted relaxation search

OBIETTIVOOttenere 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

Budgeted relaxation search• 2 tassonomie

T2

T1

x

xnextBxbSxCxBxx

00 ,,min0

yxC , costo di esecuzione della query (x,y)

Nota: yyxx ','

xbSx ,,

),(',' yxdocsyxdocs

'x

y

'y

36



T2

T1

x )(xnext

0,, xbSxC

)(xnextB

37

)(xnext nodo successivo lungo il cammino verso la radice della tassonomia

• 2 tassonomie xnextBxbSxCxB

xx

00 ,,min0



T2

T1

x )(xnext

)(xnextB 0,, xbSxC

38


xx

00 ,,min0



T2

T1

x

)(xnextB

0,, xbSxC

• )(xnext39


xx

00 ,,min0



T2

T1

x

)(xnextB 0,, xbSxC

40


xx

00 ,,min0


T2

T1

T2

T1

Falsi positiviFalsi positivi

2 volte

3 volte


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)


Risultati sperimentaliBaseline algorithm: recupera i documenti che soddisfano la parte

testuale della query e utilizza i metadati della tassonomia per post-processare 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


Risultati sperimentaliAnalisi 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)


One query per levelSi assume che ad ogni livello della tassonomia,

i documenti vengano recuperati attraverso un’unica interrogazione

Per fanout bassi, nessun algoritmo fa peggio del baseline e binary search in alcuni casimigliora le prestazioni di molto.


One query per level

Per fanout e numero di tassonomie più alti, il miglior algoritmo di ricerca è quello top-down, 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.


Dati realiAverage number of cursor movements

AlgorithmNumber of results

k=10 k=100

baseline 11277

bottom up 819 1582

top down 61 242

binary search 62 242

Reuters dataset RCV1 contenente articoli digiornale in lingua inglese dal 20-08-1996 al19-08-1997.Dimensione dei dati non compressa: 2.5GBDocumenti classificati in 2 tassonomie:1.“industry” taxonomy: 996 foglie, profondità max 72.“date taxonomy”: 3 livelli (anno, mese, giorno)

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.


Multiple queries per levelSi 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.

Dalla figura si può vedere che per profondità e fanout maggiori, i beneficiche si hanno dalla esecuzione di query multiple aumentano.


GRAZIE PER L’ATTENZIONE


Marcus Fontoura Vanja Josifovski Ravi Kumar Christopher Olston Sergei Vassilvitskii

Documents

Transcript of Marcus Fontoura Vanja Josifovski Ravi Kumar Christopher Olston Sergei Vassilvitskii