View
115
Download
0
Category
Preview:
Citation preview
CONTEXT-SENSITIVERANKING
Rakesh Agrawal / Ralf Rantzau /Evimaria Terzi
Sumário
� 1. Introdução
� 2. Preferências contextuais
� 3. The rank selection problem
� 4. Constructing orders from preferences� 5. Finding representative orders� 6. Ranked Top-k Queries� 7. Trabalhos relacionados
� 8. Conclusões
Rakesh Agrawal
� Microsoft Research Labs� Entre um dos top 50 cientistas em 2003� M.S. and Ph.D. degrees in Computer Science from the
University of Wisconsin-Madison� 60 patentes� Mais de 150 artigos� Google scholar: 63762 citações� Áreas de estudo:
� Web Technologies; Privacy & Security; Data Mining; Text Mining;OLAP; Object-Oriented Type Systems; Active DatabaseSystems; Object-Oriented Database Systems; DeductiveDatabase Systems; Distributed Systems; TransactionManagement; Database Machines.
Ralf Rantzau
� Assistant professor in Aalborg University
� Membro dos comitês: COMAD; KDD; SIGMOD IDAR
� Ph.D. degrees in Computer Science from the Universityof Stuttgart
� Áreas de estudo: Privacy; Real-time analytics; All thingsdatabases.
Evimaria Terzi
� Professor of Computer Science, Boston University� Membro de comitês: ICDM, SDM, IDA, PKDD, SIGKDD,
ICDE, SIGMOD, WWW, CIKM, DBSOCIAL� Áreas de estudo: algorithmic data mining with emphasis
on social-network analysis, analysis of sequential data,ranking, clustering and bioinformatics.
� Google Scholar: 791 citações
1.Introdução
30.000.000 ofertas de produtos
40.000 lojas
Introdução
� Select * from produtos
Introdução
� Tuplas ranqueadas, baseadas no contexto daconsulta sem sacrificar a sua performance.
� Proposta:� Uma base de dados já carregada de preferências� Técnicas para usar essas preferências para gerar
ordenações representativas das tuplas e seuscontextos associados
� Técnicas para usar essas pré-ordenações parafornecer rapidamente respostas ranqueadas àsconsultas tendo em consideração a condição daconsulta.
Introdução
>
>
>
Introdução
� SELECT ATORFROM FILMEWHEREGENERO = ‘Drama’ E LINGUA = ‘Espanhol’
� As preferências que se referem à cláusula where devem serlevadas em consideração no ranking dos resultados daconsulta.
Problema
R
P
2.Preferências Contextuais
p1 = {A1 = A > A1 = B | A4 = U}
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
A1 A2 A3 A4
t3 B M W U>
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
Preferências Contextuais
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
p = {Ai=ai1 > Ai=ai2 | X}contextoescolha
Relação R= {t1, t2, ..., tn}
Esquema R (A1,A2,...,Ad)
ai1 e ai2 ∈ Dom(Ai)
l ⊆ {1, . . . , d}
X é Λ j∈l (Aj = aj )
aj ∈ Dom(Aj)
p1 = {A1 = A > A1 = B | A4 = U}
PREF(t1,t3,p1)= 1
PREF(t3,t2,p1)= 0
PREF(t1,t4,p1)= ┴
Preferências Contextuais
p2 = {A2 = K > A2 = M | A4 = U}
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
>
A1 A2 A3 A4
t1 A K X U
t3 B M W U
A1 A2 A3 A4
t1 A K X U
A1 A2 A3 A4
t3 B M W U
PREF(t1,t3,p2)= 1 PREF(t3,t1,p2)= 0 PREF(t1,t4,p2)= ┴
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
Preferências Contextuais
p3 = {A3 = W > A3 = X | A4 = U}
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
>
A1 A2 A3 A4
t1 A K X U
t3 B M W U
A1 A2 A3 A4
t3 B M W U
A1 A2 A3 A4
t1 A K X U
PREF(t3,t1,p3)= 1 PREF(t1,t3,p3)= 0 PREF(t1,t4,p3)= ┴
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
Preferências Contextuais
p4 = {A1=C > A1=A | A3=Y ∧∧∧∧ A4=U}
A1 A2 A3 A4
t2 A L Y U
t4 C N Y U
>A1 A2 A3 A4
t4 C N Y U
A1 A2 A3 A4
t2 A L Y U
PREF(t4,t2,p4)= 1 PREF(t2,t4,p4)= 0 PREF(t1,t4,p4)= ┴
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
Preferências Contextuais
∈ PA4=U
X1 = Λ j∈l1 (Aj = aj) X2 = Λ j∈l2 (Aj = bj) l1 , l2 ⊆ {1, 2, . . . , d}l1 = l2 = l aj = bj para todos os j ∈ l.
p4 = {A1=C > A1=A | A3=Y ∧∧∧∧ A4=U}
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
Classes de Preferências
Preferências Contextuais
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
A1 A2 A3 A4
t4 C N Y U
t5 A L Z V
Indiferente para o contexto X, se:
∀p ∈ PX
∀ t’<> t, PREF(t, t’, p) =⊥ ∧ PREF(t’, t, p) =⊥.
Asserted Indiferent
Tuplas indiferentes e asserted
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
PA4=U
Preferências Contextuais
Preferência Efetiva (EFF-P)
Existe um p ∈ PX , tal que PREF(t,t’)=1 V PREF(t’,t)=1
Se não existe p
Se as tuplas são indiferentes, EFF-P (t, t’, PX) = ⊥
Preferências Contextuais
A1 A2 A3 A4
t1 A K X U
t2 A L Y U
Preferência Efetiva (EFF-P)
EFF-P(t1,t2, PA4=U) t1 e t2 são asserted,mas não há preferência que envolva as duas.
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
PA4=U
Preferências Contextuais
EFF-P(t1,t3, PA4=U)t1 e t3 são asserted, e existe preferência (p1, p2, p3) que envolvem as duas.
A1 A2 A3 A4
t1 A K X U
t3 B M W U
Preferência Efetiva (EFF-P)
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
PA4=U
66.03
2
1)(00)(10)(1
011==
+++++
++
Preferências Contextuais
EFF-P(t3,t1, PA4=U)
A1 A2 A3 A4
t1 A K X U
t3 B M W U
Preferência Efetiva (EFF-P)
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
PA4=U
33.03
1
)0(1)1(0)1(0
100==
+++++
++
Preferências Contextuais
EFF-P(t2,t3, PA4=U)
A1 A2 A3 A4
t2 A L Y U
t3 B M W U
Preferência Efetiva (EFF-P)
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
PA4=U
11
1
)0(1
1==
+
Preferências Contextuais
Eff-P(t1,t2,PA4=U) = ½
Eff-P(t1,t3,PA4=U) = 2/3
Eff-P(t3,t1,PA4=U) = 1/3
Eff-P(t2,t3,PA4=U) = 1
Grafo de Preferências do contexto X = A4=UGX (VX, EX)
VX = asserted tuplasEX = e (t � t’)
Preferências Contextuais
� Preferência� Pref(t1,t2,p1)� Classe de preferências� Tuplas asserted e indiferentes� Preferência efetiva� Grafo de preferência
3. The rank selection problem
PROBLEMA 1A1 A2 A3 A4
t1 A K X U
t2 A L Y U
t3 B M W U
t4 C N Y U
t5 A L Z V
r = {t1, ..., tn}
R (A1, ..., Ad)
q (r)
A1 A2 A3 A4
t1 A K X U
t3 B M W U
t4 C N Y U
A1 A2 A3 A4
t1 A K X U
t3 B M W U
t4 C N Y U
A1 A2 A3 A4
t1 A K X U
t4 C N Y U
t3 B M W U
A1 A2 A3 A4
t3 B M W U
t4 C N Y U
t1 A K X U
A1 A2 A3 A4
t4 C N Y U
t1 A K X U
t3 B M W U
p3 = {A3 = W > A3 = X | A4 = U}
p2 = {A2 = K > A2 = M | A4 = U}
p1 = {A1 = A > A1 = B | A4 = U}
P = {PX1, ..., PXm}
The rank selection problem
PROBLEMA 1 M = qnt de classes
The rank selection problem
Similaridade por cossenoN = |D| = 13
0 A1 A
1 A1 B
2 A1 C
3 A2 K
4 A2 L
5 A2 M
6 A2 N
7 A3 X
8 A3 Y
9 A3 W
10 A3 Z
11 A4 U
12 A4 V
D
OD
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 1
12 0
VA4 = U
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 1
9 0
10 0
11 1
12 0
VA4=U ΛA3=Y
VXVq
The rank selection problem
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
10 0
11 1
12 0
VX
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0
8 1
9 0
10 0
11 1
12 0
Vq
709,01,41
1
21
010000000000==
×
+++++++++++
Similaridade por cosseno
Abordagem
� Gargalo: todas as preferências deveriam ser consultadas a cada par de tupla.
� Framework proposto:� Processamento offline
� Construir ordenações entre as tuplas� Reduzir o número de ordenações
� Processamento online� Usa os pré-processamentos para retornar resultados
de forma rápida
Abordagem
� Processamento Offline - Passo 1
PX1
T1T2T3T4
PX2
T2T3T1T4
PX3
T4T2T3T1
PX4
T3T2T1T4
s(t1|X1) = 4 – 0+1 = 5
<Xi, Ti> = <contexto, ordem>
Abordagem
� Processamento Offline - Passo 2� Encontrar l ordenações representativas� Divide as permutações iniciais em l grupos� Cada grupo i é caracterizado por e uma
disjunção de contextos Xi
Ti
Abordagem
� Processamento Online� A única tarefa é combinar as ordenações das
tuplas já definidas offline
Abordagem
� Processamento offline� Passo 1
� Como conseguir as ordenações? (Problema 2)
� Passo 2� Como conseguir as ordenações representativas?
(Problema 3)
� Processamento online� Como conseguir a resposta da melhor ordenação?
(Problema 4)
4.Construting orders frompreferences
� Problema 2� Encontrar uma ordenação entre as tuplas de
acordo com cada classe de preferência
Construting orders frompreferences
� Subgrafo acíclico maximal: encontrar o subgrafo acíclico de peso máximo de um grafo G
� Três algoritmos� Pick-perm� Greedy-order� MC-order
Construting orders from preferences
� PICK-PERM
Construting orders from preferences
� GREEDY-ORDER
Construting orders frompreferences
� MC-ORDER� Cria um grafo com todas as arestas reversas� Se ti -> tj, entao tj -> ti� Um caminho aleatório é feito e as tuplas são
rankeadas de acordo com seus valores
Experimentos
� Geração dos dados sintéticos : general andstrictly acyclic
� Um único contexto X.� Comparação dos algoritmos com o resultado
que deveria ser alcançado.
5.Finding representative orders
T1T2T5T8
T4T7T9T11
T6T3T10T12
Finding representative orders
� Problema 3 – CLUSTERORDERS – OFFLINE� Dado o conjunto de ordenações do passo 1
� Da forma
� Encontrar o conjunto
� Da forma
},...,{ 1 mm TTT =
},...,{ 1 ll TTT =
>< ii TX ,
>< iTXi,
Finding representative orders
� Cada
� Tal que
� Cada contexto
� É mapeado para um conjunto final de contextos
},...,{ mii XXX ⊆
),(minarg; ' jiiiij TTdTXX =∈∀
jX
iX
Finding representative orders
� Spearman footrule
� Kendall tau
Finding representative orders
� GREEDY
Finding representative orders
� THE FURTHEST
Finding representative orders
� Refinamentos� Discrete: aplicar novamente um dos algoritmos
em cada partição para encontrar o melhor representante entre eles
� Continuous: aplicar novamente um dos algoritmos em cada partição para encontrar qual, entre todas as ordenações, é o melhor representante para a partição
Experimentos
� Não consideraram tuplas indiferentes.� N = numero de tuplas em cada ordenação,
500� M = numero de ordenações de entrada, 1000� L = numero de clusters verdadeiros, {2, 4, 8,
16}� Geração de l ordens aleatórias que serão o
centro de cada cluster� Geração de mais ordens para cada cluster
adicionando ruído (swap, shift) de um tipo específico, {2,4,8 ..., 128}
Experimentos
� F(A)� Custo total da solução pelo algoritmo
� F(INP)� Custo da estrutura de agrupamento utilizado no
processo de geração de dados.
ExperimentosDistancia footrule
6.Ranked Top-k queries
� Problema 4 – Querying Online
� Adaptação do algoritmo TA� q(r) = conjunto de tuplas que respondem q
},...,{ 1 ll TTT =
1)()( +−= tTnXts ii
>< iTXi,
Ranked Top-k queries
<X1,T1
>t1t2t3t4
<X2,T2
>t3t4t1t2
<X3,T3
>t1t3t4t2
<X4,T4
>t4t3t2t1
q(r)
t1t3
t1
t1
t1
t1
t1
t2
t3
t3t3 t3
t3
t4
Ranked Top-k queries
� O score final da tupla t para a query q é:
Ranked Top-k queries
� Como o acesso é round-robin nem todas as tuplas são acessadas no passo anterior.
� é o escore da ultima tupla visitada da ordenação Ti do último ciclo.
� O parâmetro� O algoritmo para quando k tuplas com o
escore maior ou igual a s foram vistos.� A saída são os k maiores valores de escore.
Experimentos
� Dados gerados da mesma forma do Experimento II
� L = {2,4,8,16}, noise de 64 swaps, n = 500 e m = 1000
� R(OPT,k) = resultado usando todas as ordens� R(A,k) = resultado usando as ordens
representativas� Compara usando o coeficiente Jaccard
Experimentos
Experimentos
� Dados reais� www.imdb.com (32000 filmes)
� R= (TID, titulo, genero, ano, linguagem, ator, diretor)
� Geração de preferências a partir da mineração de regras de associação
� Confiança: 0.2, 883 classes de preferencias� Uso do MC-ORDER para a construção das
ordens e GREEDY para o problema de cluster.
O tempo de resposta aumenta linearmente de acordo com o numero de clusters
50 tupla
s
Experimentos
� Resultados encorajadores� Workstation NT 2.3 GHz, para a implementação
não otimizada, levou 3 segundos para 50 clusters� Mesmo com a criação de 883 classes de
preferências e 50 clusters, níveis de acurácia foram satisfatórios para a maioria das consultas testadas
7.Trabalhos Relacionados
� Similar a ferramentas de web-search� Ordenação das tuplas apriori, independente da
consulta, para usar na realização de consultas� O uso de contextos também aparece em outros
trabalhos� Na web a estrutura de hiperlinks já apresenta um
estrutura natural de grafo que permite uma boa classificação das páginas.
� Este trabalho usa um grafo induzido por preferências do usuário para esta finalidade.
Trabalhos Relacionados
� Há trabalhos que induzem grafos baseados nos conteúdos das tuplas de um BD.� As arestas são induzidas por chave estrangeira� As respostas às consultas são rankeadas usando
a noção de ‘prestigio’ dos nós baseado nas arestas de entrada
� Entretanto, não há uma estrutura de grafo aceita globalmente para representação de dados relacionais.
Trabalhos Relacionados
� Há trabalhos que definem a importância de uma tupla através de scores. � Ou fornecidas pelos usuários, ou mineradas.� Os autores consideram a possibilidade de
mineração de preferências contextuais.� E então incorporam pares de preferências na
formulação dos ranks finais, sendo uma análise mais precisa das preferências do usuário.
Trabalhos Relacionados
� Incorporação de preferências pessoais para acriação de ranks personalizados já tem sidoestudado� Um dos trabalhos apresenta uma preferência por
simples predicados. Cada predicado é associado aum valor que corresponde ao nível do usuárioàquela preferência. O resultado é um perfil depreferência do usuário.
� O foco deste trabalho não é na personalizaçãode respostas para usuários individuais, masusar um conjunto de preferências comuns pararesponder eficientemente e rankear resultadosde consultas de um grande numero de usuários.
Trabalhos Relacionados
� Há uma expressiva literatura para linguagens de preferência. � Em alguns trabalhos as preferências são expressas
em fórmulas de primeira ordem, incorporadas na álgebra relacional. Os resultados de saída são aqueles que atendem a todas as restrições.
� Abordagem: a partir do momento que se assume que é uma otimização do problema de satisfação de preferência contextual, não há restrições mas o que mais concorda com as preferências de entrada.
Trabalhos Relacionados
� O trabalho mais próximo também trabalha com pares de preferências. Uma ordem total dos objetos que concordam o máximo possível com as preferências é extraída.� O presente trabalho foca no impacto de como
as preferências associadas a diferentes contextos tem impacto nos resultados das consultas.
� Finalmente, os autores afirmam que a linguagem de preferências está mais próximas das triplas de dados de treinamento na forma “com respeito ao objeto c, objeto a é mais próximo do que b”.
8.CONCLUSÃO
� O framework apresentado tira vantagem das preferências do usuário para pré-computar ordens representativas e usá-las para fornecer respostas rankeadas às consultas ao banco de dados.
� A abordagem é similar a técnicas de web search: pré-computar a ordenação de cada página e usar esse valor para responder às pesquisas.
CONCLUSÃO
� A linguagem de preferência é natural e intuitiva e não requer que o usuário especifique valores de importância para as tuplas.
� A linguagem é orientada a conjunto e permite que uma única preferência especifique escolhas entre um grande par de tuplas.
� Duas tuplas podem ser ordenadas de forma diferentes, dependendo do contexto.
CONCLUSÃO
� Os experimentos mostram que a proposta alcança alto nível de acurácia mesmo quando um pequeno numero de ordens representativas são mantidas, permitindo uma redução no armazenamento e retornando as respostas rapidamente.
Trabalhos futuros
� Estudar algoritmos incrementais para a manutenção das ordenações e preferências com o desenvolvimento do banco de dados.
� Investigar como fazer a solução resistente a spam na presença de usuários maliciosos.
Referência
� http://rakesh.agrawal-family.com/bio.html� http://scholar.google.com/citations?user=j6KF
CRAAAAAJ&hl=en� http://sites.google.com/site/rantzauworld/� http://dl.acm.org/citation.cfm?id=1142517
OBRIGADA!
Recommended