Um sistema de recomendação de produtos baseado em grafos€¦ · Um sistema de recomendação de...

Um sistema de recomendação de produtos baseado em grafos

Renato Pedigoni!Engenheiro Líder @rpedigoni renato@luizalabs.com

André Fatala!Diretor P&D @andrefatala fatala@luizalabs.com

744 lojas físicas 8 centros de distribuição +24 mil colaboradores +22 milhões de clientes 14 milhões de visitantes únicos por mês

–Dan Ariely

"Big data is like teenage sex: everyone talks about it, nobody really knows how to do it,

everyone thinks everyone else is doing it, so everyone claims they are doing it..."

Grafos

Grafos

Vértices (entidades, objetos)

Pessoa Sessão Produto Categoria Depto

Grafos

Vértices (entidades, objetos)

Arestas (relacionamentos, conexões)

Pessoa Sessão Produto Categoria Depto

Grafos

Vértices (entidades, objetos)

Arestas (relacionamentos, conexões)

pertence

Pessoa Sessão Produto Categoria Depto

visitou comprou avaliou

Grafos

Vértices (entidades, objetos)

Arestas (relacionamentos, conexões)

pertence

Pessoa Sessão Produto Categoria Depto

visitou comprou avalioutimestamp timestamp

quantidadetimestamp avaliacao

nome email

timestamp titulo estoque

titulo titulo

Modelo: e-commerce

Modelo: e-commerce

Pessoa

Modelo: e-commerce

Pessoainiciou

Modelo: e-commerce

Pessoa Sessãoiniciou

Modelo: e-commerce

Pessoa Sessãoiniciou

visitou

Modelo: e-commerce

Pessoa Sessão

Produto

iniciou

visitou

Modelo: e-commerce

Pessoa Sessão

Produto

iniciou

visitou

pertence

Modelo: e-commerce

Pessoa Sessão Categoria

Produto

iniciou

visitou

pertence

Modelo: e-commerce

Pessoa Sessão Categoria

Produto

iniciou

visitou

pertence

pertence

Modelo: e-commerce

Pessoa Sessão Categoria

Depto

Produto

iniciou

visitou

pertence

pertence

Modelo: e-commerce

Pessoa Sessão Categoria

Depto

Produto

iniciou

visitou

crosssell

pertence

pertence

Modelo: e-commerce

Pessoa Sessão Categoria

Depto

Produto

Produto

iniciou

visitou

crosssell

pertence

pertence

Modelo: e-commerce

Pessoa Sessão Categoria

Depto

Produto

Produto

iniciou

visitou

crosssell

pertence

pertence

upsell

Modelo: e-commerce

Pessoa Sessão Categoria

Depto

Produto

Produto Produto

iniciou

visitou

crosssell

pertence

pertence

upsell

Modelo: e-commerce

Pessoa Sessão Categoria

Depto

Produto

Produto Produto

iniciou

visitou

similar

crosssell

pertence

pertence

upsell

Modelo: e-commerce

Pessoa Sessão

Produto

Categoria

Depto

Produto

Produto Produto

iniciou

visitou

similar

crosssell

pertence

pertence

upsell

Tinkerpop

Tinkerpop

Tinkerpop

Java Conjunto de ferramentas para trabalhar com grafos Blueprints: análogo ao JDBC, para grafos

Grafos persistentes

Grafos persistentesEntre as possibilidades:

Grafos persistentes

Suporta grandes grafos Código aberto, uso gratuito (incl. comercial) Storage configurável: Cassandra, HBase, entre outros

Nossa escolha:

Entre as possibilidades:

Grafos persistentes• Teorema "CAP"

Consistência - Disponibilidade - Particionamento

Grafos persistentes• Teorema "CAP"

Consistência - Disponibilidade - Particionamento

Nossa escolha

- Sem ponto único de falha - Consistência eventual

Como interagir com o grafo?

Como interagir com o grafo????

Como interagir com o grafo?

Gremlin: Parte do Tinkerpop DSL para grafos Simples Comunidade ativa

Exemplo

Exemplo

> vert1 = g.addVertex();> vert1.tipo = 'visitante';

Visitante

Exemplo

> vert1 = g.addVertex();> vert1.tipo = 'visitante';

> vert2 = g.addVertex();> vert2.tipo = 'produto';

Visitante Produto

Exemplo

> vert1 = g.addVertex();> vert1.tipo = 'visitante';

> vert2 = g.addVertex();> vert2.tipo = 'produto';

> g.addEdge(vert1, vert2, 'visitou');

> g.commit()

Visitantevisitou

Produto

Quem viu, também viuRecomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

Recomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

visitou

visitou

visitou

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

visitou

visitou

visitou

visitou

visitou

visitou

Recomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

Recomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

Recomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

.out('visitou')

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

.out('visitou')

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

.out('visitou')

.groupCount()

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

.out('visitou')

.groupCount()

key value

TV LCD 40"

TV PLASMA 52"

TV LED 42”

TV LCD 32"

1

2

3

1

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

.out('visitou')

.groupCount()

key value

TV LCD 40"

TV PLASMA 52"

TV LED 42”

TV LCD 32"

1

2

3

1

.sort{-it.value}

Sessão!#21162

Quem viu, também viu

TV LED 40"

Sessão!#826482

Sessão!#4337189

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"g.V('product_sku', 'tv_led_40')

.in('visitou')

Recomendação

.out('visitou')

.groupCount()

key value

TV LCD 40"

TV PLASMA 52"

TV LED 42”

TV LCD 32"

1

2

3

1

.sort{-it.value}

Produto

Supernodes• Vértices com número desproporcional de arestas

conectadas

http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/Benchmark

Produto

Supernodes• Vértices com número desproporcional de arestas

conectadas

Produto +1.000.000

http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/Benchmark

Produto

Supernodes• Vértices com número desproporcional de arestas

conectadas

Produto

Solução (Titan): vertex-centric indices

+1.000.000

http://thinkaurelius.com/2012/10/25/a-solution-to-the-supernode-problem/Benchmark

Arestas de atalho

TV LED 40"

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

Sessão"#21162

Sessão"#826482

Sessão"#4337189

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

1

Arestas de atalho

TV LED 40"

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

Sessão"#21162

Sessão"#826482

Sessão"#4337189

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

1

Arestas de atalho

TV LED 40"

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

Sessão"#21162

Sessão"#826482

Sessão"#4337189

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

1

quem_viu_tb_viu

quem_viu_tb_viu

Arestas de atalho

TV LED 40"

TV LCD 40"

TV PLASMA

52"

TV LED 42”

TV LCD 32"

Sessão"#21162

Sessão"#826482

Sessão"#4337189

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

visitou

1

quem_viu_tb_viu

quem_viu_tb_viu

g.V('product_sku', ‘tv_led_40’).out(‘quem_viu_tb_viu’)

Mas e o Hadoop?

Aurelius Graph Stack

Aurelius Graph Stack

Faunus

Roda sobre o Hadoop, armazena os dados no HDFS Ferramenta para operações globais no grafo Diversas utilidades

Graph analytics Schema migration Sub grafos Detecção de comunidades

Faunus: exemploIn degree distribution

g.V.sideEffect('{it.degree=it.inE.count()}').degree.groupCount

Faunus: exemploIn degree distribution

g.V.sideEffect('{it.degree=it.inE.count()}').degree.groupCount

Faunus: exemploIn degree distributiong.V.sideEffect('{it.degree=it.inE.count()}').degree.groupCount

Faunus: exemploIn degree distributiong.V.sideEffect('{it.degree=it.inE.count()}').degree.groupCount

==>1 167050!==>10 2305!==>100 6!==>108 3!==>119 3!==>122 3!==>133 1!==>144 2!==>155 1!==>166 2!==>18 471!==>188 1!==>21 306!==>232 1!==>254 1!==>...

Rexster

• Parte da stack Tinkerpop

• Permite acessar qualquer grafo Blueprints através de uma API REST

• Além de HTTP, possui protocolo binário (RexPro)

Gremlin Demo

User

type userId

Gremlin Demo

User

type userId

Gremlin Demo

initialized

User

type userId

Gremlin Demo

initializedSession

type sessionId timestamp

User

type userId

Gremlin Demo

initializedSession

type sessionId timestamp

viewed

User

type userId

Gremlin Demo

initializedSession

type sessionId timestamp

Product

type category

name

viewed

Gremlin Demoinitialized

User

type userId

Session

type sessionId timestamp

Product

type category

name

viewed

50 users 90 products 102 sessions !690 edges

Analytics

Bob

• Infra: AWS

• +1.2 bilhões de arestas armazenadas

• + 300 milhões de vértices

• 20 milhões de recomendações por dia

Renato Pedigoni"Engenheiro Líder @rpedigoni renato@luizalabs.com

André Fatala"Diretor P&D @andrefatala fatala@luizalabs.com

Há vagas!luizalabs.com