Eu tenho um banco de dados grande (16 milhões de linhas) contendo hashes perceptivos de imagens.
Gostaria de poder pesquisar linhas impedindo a distância em um prazo razoável.
Atualmente, até onde eu entendi direito o problema, acho que a melhor opção aqui seria uma implementação personalizada do SP-GiST que implemente uma BK-Tree , mas isso parece muito trabalhoso e ainda estou confuso quanto à prática detalhes da implementação adequada de um índice personalizado. Calcular a distância de Hamming é suficiente tratável, e eu fazer sabe C, no entanto.
Basicamente, qual é a abordagem apropriada aqui? Eu preciso ser capaz de consultar correspondências dentro de uma certa distância de edição de um hash. Pelo que entendi, a distância de Levenshtein com cadeias de comprimento igual está prejudicando funcionalmente a distância, portanto há pelo menos algum suporte existente para o que eu quero, embora não haja uma maneira clara de criar um índice a partir dele (lembre-se, o valor que estou consultando Não consigo pré-calcular a distância de um valor fixo, pois isso seria útil apenas para esse valor).
Atualmente, os hashes são armazenados como uma cadeia de 64 caracteres contendo a codificação ASCII binária do hash (por exemplo, "10010101 ..."), mas posso convertê-los em int64 com bastante facilidade. O problema real é que preciso ser capaz de consultar relativamente rápido.
Parece que pode ser possível obter algo na linha do que eu quero com o pg_trgm, mas não sei como funciona o mecanismo do trigrama correspondente (em particular, o que a métrica de similaridade que ele retorna realmente representa? tipo como editar distância).
O desempenho da pastilha não é crítico (é muito computacionalmente caro calcular os hashes para cada linha), então eu me preocupo principalmente com a pesquisa.
fonte
Respostas:
Bem, passei um tempo olhando para escrever uma extensão C personalizada do postgres e acabei escrevendo um wrapper de banco de dados Cython que mantém uma estrutura de árvore BK na memória.
Basicamente, ele mantém uma cópia na memória dos valores de phash do banco de dados, e todas as atualizações no banco de dados são repetidas na árvore BK.
Está tudo no github aqui . Ele também tem muitos testes de unidade.
A consulta em um conjunto de dados de 10 milhões de valores de hash para itens com uma distância de 4 resulta em tocar entre 0,25% e 0,5% dos valores na árvore e leva aproximadamente 100 ms.
fonte
MOAR RESPOSTAS!
Ok, finalmente tirei um tempo para escrever uma extensão de indexação personalizada do PostgreSQL. Eu usei a interface SP-GiST .
Isso foi bastante desafiador, principalmente porque o Posgres é grande .
De qualquer forma, como sempre, está no github aqui .
No que diz respeito ao desempenho, atualmente é ~ 2-3 vezes mais lento que a implementação de memória pura na minha outra resposta a esta pergunta, mas é muito mais conveniente usá-lo. ms / query - 150 ms / query, que ainda é bem pequeno).
fonte