o problema
Deduplicar um banco é decidir, para cada par de registros, se os dois falam da mesma coisa: o mesmo produto cadastrado por dois vendedores, o mesmo cliente com dois endereços, a mesma empresa escrita de três jeitos. O comparador que responde isso bem é caro — normaliza texto, mede distância entre campos, roda um modelo. E o número de pares cresce com o quadrado do número de registros. Num catálogo de 530 milhões de linhas são cerca de 140 quatrilhões de pares. Não existe cluster que pague essa conta, nem que o comparador custasse um microssegundo.
Por isso todo sistema de deduplicação tem um estágio anterior, o blocking: agrupar registros por alguma chave barata e só comparar quem cai no mesmo grupo. O problema é que a chave é uma escolha feita antes de olhar o dado, e ela erra dos dois lados. Chave frouxa — cidade, categoria, primeira letra do nome — produz blocos monstruosos e o custo quadrático volta pela porta dos fundos, concentrado no bloco de “São Paulo” ou no bloco do campo que veio vazio. Chave apertada separa registros que eram par e o recall despenca, sem que ninguém fique sabendo: o par perdido no blocking nunca chega ao comparador para ser rejeitado com conhecimento de causa.
a ideia
Dynamic Blocking, que este trabalho estende, parte de uma observação sobre onde mora o sinal. Compartilhar um valor comum não diz quase nada. Compartilhar um valor raro diz muito. E compartilhar uma interseção de valores — mesmo que cada valor isolado seja comum — também é raro, e também diz muito. Raridade, e não o atributo em si, é o que prevê a relação de match.
Isso sugere não fixar a chave antes. Começa-se com blocos formados por valores individuais e, onde o bloco ficou grande demais para ser útil, ele é refinado pela interseção com outros atributos, até virar um conjunto pequeno o bastante para ser interessante. O dado decide a granularidade, bloco a bloco, em vez de o engenheiro decidir uma granularidade só para o banco inteiro.
Hashed Dynamic Blocking acrescenta duas coisas a isso. A primeira é usar Locality Sensitive Hashing para construir os próprios valores de chave de bloco: em vez de agrupar por igualdade exata de um campo, agrupa-se por hash que colide quando os campos são parecidos, com uma configuração que expõe o trade-off entre precisão e recall como parâmetro em vez de deixá-lo implícito no esquema. A segunda é tratar o processo como um problema de sistema, não de algoritmo: minimizar movimentação de dados, representar bloco de forma compacta e podar gulosamente os blocos candidatos que não valem a pena usando um Count-min Sketch — contagem aproximada, barata, em vez de materializar os blocos para depois medi-los.
o que isso custou
O trade-off está declarado, não escondido: a configuração de LSH controla precisão contra recall, e não existe ponto que entregue as duas. Escolher onde parar nessa curva continua sendo decisão de quem opera, com o custo de que o par perdido é invisível a jusante.
A poda é gulosa e a contagem é aproximada. Count-min Sketch erra para cima, nunca para baixo, então a decisão de descartar um bloco é tomada sobre uma estimativa inflada de tamanho — o método é uma heurística de engenharia com garantia probabilística, não uma seleção exata dos melhores blocos.
A linearidade é empírica. O trabalho a demonstra em datasets reais acima de um milhão de linhas; é uma observação nessa faixa, com esses dados, não um limite assintótico provado.
E o número que mais impressiona é também o que delimita o escopo. Detectar 68 bilhões de pares candidatos em menos de três horas por US$ 307 é o custo do blocking. Esses 68 bilhões de pares ainda precisam passar pelo comparador caro. O trabalho resolve o estágio de geração de candidatos e move o gargalo para o próximo, que não é o que ele mede.
onde isso aparece hoje
Geração de candidatos por hashing é a mesma família de problema que aparece em detecção de quase-duplicatas na web, onde a solução clássica é Detecting Near-Duplicates for Web Crawling, e em busca de similaridade sem comparar tudo com tudo, que é o ataque de Scaling Up All Pairs Similarity Search pelo outro lado. A ideia de trocar contagem exata por estrutura probabilística compacta é a mesma linhagem de HyperLogLog e do filtro de Bloom: aceitar erro limitado em troca de caber na memória.
Dentro do próprio catálogo de e-commerce, o problema reaparece em identificação de produtos similares em escala e em detecção de perguntas quase duplicadas — sempre com a mesma estrutura de dois estágios, um barato que recupera candidatos e um caro que decide.