Eu tenho um grande banco de dados (16 milhões de linhas) contendo hashes perceptivos de imagens.
Eu gostaria de poder procurar linhas por hamming distância em um período de tempo razoável.
Atualmente, tanto quanto eu entendo corretamente o problema, acho que a melhor opção aqui seria uma implementação SP-GiST personalizada que implementa um BK-Tree , mas isso parece muito trabalhoso e ainda estou confuso na prática detalhes da implementação adequada de um índice personalizado. Calcular a distância hamming é tratável o suficiente, e eu conheço 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 Levenshtein com strings de comprimento igual é uma distância hamming funcional, então 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 mudanças. Não posso pré-calcular a distância a partir de um valor fixo, pois isso só seria útil para aquele valor).
Os hashes são atualmente armazenados como uma string de 64 caracteres contendo a codificação ASCII binária do hash (por exemplo, "10010101..."), mas posso convertê-los para int64 com bastante facilidade. O problema real é que preciso ser capaz de consultar relativamente rápido.
Parece que seria possível conseguir algo na linha do que eu quero com o pg_trgm, mas estou um pouco confuso sobre como funciona o mecanismo de correspondência de trigramas (em particular, o que a métrica de similaridade que ele retorna realmente representa? Parece tipo distância de edição).
O desempenho de inserção não é crítico (é muito caro computacionalmente calcular os hashes para cada linha), então eu me preocupo principalmente com a pesquisa.
MOAR RESPONDE!
Ok, finalmente reservei 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 Posgres é grande .
De qualquer forma, como sempre, está no github aqui .
Em termos de desempenho, é atualmente ~ 2-3 vezes mais lento do que a implementação pura na memória em minha outra resposta a esta pergunta, mas é muito mais conveniente de usar. ms/consulta - 150 ms/consulta, o que ainda é muito pequeno).
Bem, passei um tempo procurando escrever uma extensão C postgres personalizada 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 reproduzidas 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 aproximadamente 0,25% a 0,5% dos valores na árvore e leva aproximadamente 100 ms.