Como os motores de busca conduzem a operação 'AND'?

StackOverflow https://stackoverflow.com/questions/2340665

Pergunta

Considere os seguintes resultados de pesquisa:

OK.As páginas são indexadas, basta consultar a contagem e os primeiros itens da tabela de índice, portanto a velocidade é compreensível.

Agora considere a seguinte pesquisa com operação AND:

Isso me deixa irritado;) Como diabos os mecanismos de pesquisa podem obter o resultado de operações AND em conjuntos de dados gigantescos tão rapidamente?Vejo as duas maneiras a seguir de conduzir a tarefa e ambas são terríveis:

  1. Você conduz a busca por 'David'.Pegue a gigantesca mesa temporária e faça uma busca por 'John' nela.NO ENTANTO, a tabela temporária não é indexada por 'John', portanto, é necessária uma pesquisa de força bruta.Isso simplesmente não será computado em 0,25 segundos, não importa qual HW você tenha.
  2. Indexação por todas as possíveis combinações de palavras como 'David John'.Em seguida, enfrentamos uma explosão combinatória no número de chaves e nem mesmo o Google tem a capacidade de armazenamento para lidar com isso.

E você pode E juntos quantas frases de pesquisa você quiser e você ainda obtém respostas em menos de 0,5 segundo!Como?

Foi útil?

Solução

O que Markus escreveu sobre o Google processando a consulta em muitas máquinas em paralelo está correto.

Além disso, existem recuperação de informação Algoritmos que facilitam esse trabalho. A maneira clássica de fazer isso é construir um Índice invertido que consiste em listas de postagens - Uma lista para cada termo de todos os documentos que contêm esse termo, em ordem.

Quando uma consulta com dois termos é pesquisada, conceitualmente, você pegava as listas de postagens para cada um dos dois termos ('David' e 'John') e caminhava por elas, procurando documentos que estão nas duas listas. Se as duas listas forem ordenadas da mesma maneira, isso poderá ser feito em O (n). É verdade que N ainda é enorme, e é por isso que isso será feito em centenas de máquinas em paralelo.

Além disso, pode haver truques adicionais. Por exemplo, se os documentos mais bem classificados fossem colocados mais altos nas listas, talvez o algoritmo pudesse decidir que encontrou os 10 melhores resultados sem caminhar por todas as listas. Então então acho no número restante de resultados (com base no tamanho das duas listas).

Outras dicas

Acho que você está abordando o problema do ângulo errado.

O Google não possui tabelas/índices em uma única máquina.Em vez disso, eles particionam fortemente seu conjunto de dados em seus servidores.Os relatórios indicam que até 1.000 máquinas físicas estão envolvidas em cada consulta!

Com essa quantidade de poder de computação, é "simplesmente" (usado com muita ironia) uma questão de garantir que cada máquina conclua seu trabalho em frações de segundo.

Ler sobre a tecnologia e infraestrutura do Google é muito inspirador e altamente educativo.Eu recomendo ler em Mesa grande, MapaReduzir e a Sistema de arquivos do Google.

O Google tem um arquivo de suas publicações disponível com muitas informações interessantes sobre suas tecnologias. Este tópico no metafiltro também fornece algumas dicas sobre a enorme quantidade de hardware necessária para executar um mecanismo de pesquisa.

Eu não sei como o Google faz isso, mas posso te dizer como EU Fiz isso quando um cliente precisava de algo semelhante:

Começa com um índice invertido, conforme descrito por Avi. Essa é apenas uma listagem de tabela, para cada palavra em todos os documentos, o ID do documento, a palavra e uma pontuação para a relevância da palavra nesse documento. (Outra abordagem é indexar cada aparência da palavra individualmente junto com sua posição, mas isso não foi necessário neste caso.)

A partir daí, é ainda mais simples que a descrição da Avi - não há necessidade de fazer uma pesquisa separada para cada termo. Operações de resumo do banco de dados padrão podem fazer isso facilmente em um único passe:

SELECT document_id, sum(score) total_score, count(score) matches FROM rev_index
WHERE word IN ('david', 'john') GROUP BY document_id HAVING matches = 2
ORDER BY total_score DESC

Isso retornará os IDs de todos os documentos que têm pontuações para 'David' e 'John' (ou seja, ambas as palavras aparecem), ordenadas por alguma aproximação de relevância e levará ao mesmo tempo para executar, independentemente de quantos ou quantos poucos termos que você está procurando, já IN O desempenho não é afetado muito pelo tamanho do conjunto de destino e está usando um simples count Para determinar se todos os termos foram correspondidos ou não.

Observe que esse método simplista apenas adiciona a pontuação 'David' e a pontuação 'John' para determinar a relevância geral; Não leva o pedido/proximidade/etc. dos nomes em consideração. Mais uma vez, tenho certeza de que o Google considera isso em suas pontuações, mas meu cliente não precisou.

Eu fiz algo semelhante a isso anos atrás em uma máquina de 16 bits.O conjunto de dados tinha um limite superior de cerca de 110.000 registros (era um cemitério, portanto, limite finito para sepultamentos), então configurei uma série de bitmaps, cada um contendo 128 mil bits.

A busca por "david" resultou na definição do bit relevante em um dos bitmaps para indicar que o registro continha a palavra "david".Fiz o mesmo com 'john' em um segundo bitmap.

Então tudo o que você precisa fazer é um 'e' binário dos dois bitmaps, e o bitmap resultante informa quais números de registro continham 'david' e 'john'.A verificação rápida do bitmap resultante retorna a lista de registros que correspondem a ambos os termos.

Essa técnica não funcionaria para o Google, então considere isso como meu valor de $ 0,02.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top