o problema
Achar coisa parecida é fácil quando existe uma consulta. Você pergunta “quem se parece com isto?”, o índice invertido responde, e o custo é proporcional ao tamanho da resposta. O problema muda de natureza quando não há consulta nenhuma: você tem uma coleção inteira e quer todos os pares que se parecem entre si. Todos os documentos quase idênticos de um crawl. Todos os registros de dois cadastros que descrevem a mesma pessoa. Todos os itens de catálogo que são o mesmo item digitado por dois fornecedores. Ninguém pergunta nada — a coleção pergunta de si mesma, e cada elemento é ao mesmo tempo consulta e corpus.
O custo dessa versão é aritmético e implacável: n·(n−1)/2 comparações. Para 1.000.000 de registros são cerca de 500 bilhões de pares; para 10 milhões, 50 trilhões. Dobrar a entrada quadruplica o serviço. E é um custo pago quase todo à toa, porque numa coleção real a esmagadora maioria dos pares não tem nada a ver: a resposta cabe em alguns milhões de linhas enquanto o espaço de busca tem doze zeros. A saída comum da área sempre foi abrir mão da exatidão — famílias de hashing sensível a localidade trocam a resposta completa por uma amostra provável dela, e você aceita perder alguns pares em troca de terminar o job. Em 2007, com coleções web já na casa das centenas de milhões de itens, “exato” tinha virado sinônimo de “inviável”.
a ideia
O título é a tese, e vale ler as duas metades separadas. “All pairs” é a exigência de completude: nada de amostragem, nada de recall de 95%; o resultado é o conjunto exato dos pares acima do limiar. “Scaling up” é a exigência de escala. O trabalho recusa a troca que a área tratava como inevitável e sustenta que dá para manter as duas coisas.
Existe um único caminho lógico para escalar um problema quadrático sem aproximar: não fazer a maior parte das comparações. Não é acelerar cada comparação — nenhuma constante salva você de n². É provar, antes de comparar, que um par não pode passar do limiar, e descartá-lo em bloco. A assimetria que torna isso possível é a mesma que torna o problema irritante: a resposta é minúscula perto da entrada. Quando o trabalho gasto fica proporcional ao tamanho da saída em vez do quadrado da entrada, o problema deixa de ser quadrático na prática mesmo continuando quadrático no pior caso.
o que isso custou
O limiar deixa de ser um detalhe de configuração e vira o parâmetro que decide se o job termina. Qualquer método que ganhe descartando pares antes de olhar para eles ganha menos conforme o limiar cai, e no limite — limiar próximo de zero, quando quase tudo é resposta — não há poda possível e o custo volta a ser o quadrado da entrada. Isso é estrutural, não um defeito de implementação: quem precisa de similaridade fraca está de volta ao ponto de partida.
A formulação também é de lote, não de fluxo. Ela responde sobre uma coleção que parou de se mexer. Coleção que recebe item novo a cada segundo pede outra pergunta, e a resposta de ontem não se atualiza sozinha.
Uma ressalva honesta: as limitações que os próprios autores declaram não estão reproduzidas aqui, porque o texto do paper não veio junto. O que está acima sai da forma do problema, não da seção de limitações deles.
onde isso aparece hoje
A pergunta não envelheceu, só trocou de vocabulário. Deduplicação de web em escala continua sendo o caso de uso canônico, e o mesmo ano de 2007 produziu a abordagem por assinatura de Detecting Near-Duplicates for Web Crawling, que ataca o mesmo alvo pelo lado aproximado. Em bancos de dados, o problema aparece com o nome de blocking na resolução de entidades, como em Scalable blocking for very large databases, e em catálogos de e-commerce vira identificação de produtos equivalentes, como em A flexible large-scale similar product identification system in e-commerce.
O que mudou foi a representação. A similaridade de 2007 é de vetores esparsos de texto; a de hoje passa por embeddings densos e por índices como o de HNSW, que resolvem a variante aproximada e por consulta. A distinção continua valendo na hora de escolher: quando errar um par custa caro — cadastro duplicado, fraude, pagamento repetido — a garantia de completude é o produto, e é ela que a formulação all pairs entrega.