IVF_PQ

O índice IVF_PQ é um algoritmo de indexação baseado em quantização para pesquisa aproximada do vizinho mais próximo em espaços de alta dimensão. Embora não seja tão rápido quanto alguns métodos baseados em grafos, o IVF_PQ geralmente requer muito menos memória, tornando-o uma opção prática para grandes conjuntos de dados.

Descrição geral

O IVF_PQ significa Inverted File with Product Quantization (Ficheiro invertido com quantificação de produtos), uma abordagem híbrida que combina indexação e compressão para uma pesquisa e recuperação vectoriais eficientes. Aproveita dois componentes principais: Inverted File (IVF) e Product Quantization (PQ).

IVF

O IVF é como criar um índice num livro. Em vez de analisar todas as páginas (ou, no nosso caso, todos os vectores), procura palavras-chave específicas (clusters) no índice para encontrar rapidamente as páginas (vectores) relevantes. No nosso cenário, os vectores são agrupados em clusters e o algoritmo irá procurar dentro de alguns clusters que estejam próximos do vetor de consulta.

Veja como isso funciona:

1. Agrupamento: O seu conjunto de dados vectoriais é dividido num número especificado de clusters, utilizando um algoritmo de agrupamento como o k-means. Cada cluster tem um centroide (um vetor representativo do cluster).

2. Atribuição: Cada vetor é atribuído ao cluster cujo centróide está mais próximo dele.

3. Índice invertido: É criado um índice que mapeia cada centróide de cluster para a lista de vectores atribuídos a esse cluster.

4. Pesquisa: Quando procura os vizinhos mais próximos, o algoritmo de pesquisa compara o vetor de consulta com os centróides de cluster e seleciona o(s) cluster(s) mais promissor(es). A pesquisa é então reduzida aos vectores dentro desses clusters selecionados.

Para saber mais sobre os seus pormenores técnicos, consulte IVF_FLAT.

PQ

A Quantização de Produtos (PQ) é um método de compressão para vectores de elevada dimensão que reduz significativamente os requisitos de armazenamento, permitindo operações de pesquisa de semelhanças rápidas.

O processo de PQ envolve as seguintes etapas principais:

Ivf Pq 1

1. Decomposição da dimensão: O algoritmo começa por decompor cada vetor de alta dimensão em m sub-vectores de igual dimensão. Esta decomposição transforma o espaço D-dimensional original em m subespaços disjuntos, em que cada subespaço contém D/m dimensões. O parâmetro m controla a granularidade da decomposição e influencia diretamente a taxa de compressão.

2. Geração do livro de códigos do subespaço: Dentro de cada subespaço, o algoritmo aplica o agrupamento k-means para aprender um conjunto de vectores representativos (centróides). Estes centróides formam coletivamente um livro de códigos para esse subespaço. O número de centróides em cada livro de códigos é determinado pelo parâmetro nbits, em que cada livro de códigos contém centróides de ^2nbits. Por exemplo, se nbits = 8, cada livro de códigos conterá 256 centróides. A cada centróide é atribuído um índice único com nbits bits.

3. Quantizaçãodo vetor: Para cada sub-vetor do vetor original, a PQ identifica o seu centróide mais próximo no subespaço correspondente utilizando um tipo de métrica específico. Este processo mapeia efetivamente cada sub-vetor para o seu vetor representativo mais próximo no livro de códigos. Em vez de armazenar as coordenadas completas do sub-vetor, apenas o índice do centróide correspondente é retido.

4. Representação comprimida: A representação comprimida final consiste em m índices, um de cada subespaço, coletivamente designados por códigos PQ. Esta codificação reduz o requisito de armazenamento de D × 32 bits (assumindo números de vírgula flutuante de 32 bits) para m × nbits bits, conseguindo uma compressão substancial ao mesmo tempo que preserva a capacidade de aproximar as distâncias vectoriais.

Para mais detalhes sobre a afinação e otimização de parâmetros, consulte Parâmetros de índice.

Cálculo da distância com PQ

Ao efetuar uma pesquisa de similaridade com um vetor de consulta, a PQ permite o cálculo eficiente da distância através dos seguintes passos:

1. Pré-processamento da consulta

   • O vetor de consulta é decomposto em m sub-vectores, correspondendo à estrutura de decomposição PQ original.

   • Para cada sub-vetor de consulta e o seu livro de códigos correspondente (contendo centróides de ^2nbits ), calcular e armazenar as distâncias a todos os centróides.

   • Isto gera m tabelas de pesquisa, em que cada tabela contém distâncias de ^2nbits.

2. Aproximação das distâncias

   Para qualquer vetor da base de dados representado por códigos PQ, a sua distância aproximada ao vetor de consulta é calculada da seguinte forma:

   • Para cada um dos sub-vectores m, obter a distância pré-computada da tabela de pesquisa correspondente utilizando o índice do centróide armazenado.

   • Somar estas m distâncias para obter a distância aproximada com base num tipo de métrica específico (por exemplo, distância euclidiana).

Ivf Pq 2

IVF + PQ

O índice IVF_PQ combina os pontos fortes do IVF e do PQ para acelerar as pesquisas. O processo funciona em duas etapas:

1. Filtragem grosseira com IVF: IVF particiona o espaço vetorial em clusters, reduzindo o escopo da pesquisa. Em vez de avaliar todo o conjunto de dados, o algoritmo concentra-se apenas nos clusters mais próximos do vetor de consulta.

2. Comparação fina com PQ: Dentro dos clusters selecionados, PQ utiliza representações vectoriais comprimidas e quantizadas para calcular rapidamente distâncias aproximadas.

O desempenho do índice IVF_PQ é significativamente afetado pelos parâmetros que controlam os algoritmos IVF e PQ. O ajuste desses parâmetros é crucial para obter os melhores resultados para um determinado conjunto de dados e aplicação. Informações mais detalhadas sobre esses parâmetros e como ajustá-los podem ser encontradas em Parâmetros de índice.

Criar índice

Para construir um índice IVF_PQ num campo vetorial em Milvus, utilize o método add_index(), especificando os parâmetros index_type, metric_type, e parâmetros adicionais para o índice.

from pymilvus import MilvusClient

# Prepare index building params
index_params = MilvusClient.prepare_index_params()

index_params.add_index(
    field_name="your_vector_field_name", # Name of the vector field to be indexed
    index_type="IVF_PQ", # Type of the index to create
    index_name="vector_index", # Name of the index to create
    metric_type="L2", # Metric type used to measure similarity
    params={
        "m": 4, # Number of sub-vectors to split eahc vector into
    } # Index building params
)

Nesta configuração:

• index_type: O tipo de índice a construir. Neste exemplo, defina o valor para IVF_PQ.

• metric_type: O método utilizado para calcular a distância entre vectores. Os valores suportados incluem COSINE, L2, e IP. Para obter detalhes, consulte Tipos de métricas.

• params: Opções de configuração adicionais para criar o índice.

  • m: Número de sub-vectores em que dividir o vetor.

  Para saber mais sobre os parâmetros de construção disponíveis para o índice IVF_PQ, consulte Parâmetros de construção do índice.

Assim que os parâmetros do índice estiverem configurados, pode criar o índice utilizando diretamente o método create_index() ou passando os parâmetros do índice no método create_collection. Para obter detalhes, consulte Criar coleção.

Pesquisar no índice

Depois de o índice ser criado e as entidades serem inseridas, pode efetuar pesquisas de semelhança no índice.

search_params = {
    "params": {
        "nprobe": 10, # Number of clusters to search
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field", # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=3,  # TopK results to return
    search_params=search_params
)

Nesta configuração:

• params: Opções de configuração adicionais para pesquisar no índice.

  • nprobe: Número de clusters a serem pesquisados.

  Para saber mais sobre os parâmetros de pesquisa disponíveis para o índice IVF_PQ, consulte Parâmetros de pesquisa específicos do índice.

Parâmetros de índice

Esta secção fornece uma visão geral dos parâmetros utilizados para criar um índice e efetuar pesquisas no índice.

Parâmetros de construção do índice

A tabela seguinte lista os parâmetros que podem ser configurados em params ao construir um índice.

	Parâmetro	Descrição	Intervalo de valores	Sugestão de afinação
IVF	nlist	O número de clusters a criar utilizando o algoritmo k-means durante a construção do índice.	Tipo: Integer Intervalo: [1, 65536] Valor predefinido: 128	Valores maiores de nlist melhoram a recuperação ao criar clusters mais refinados, mas aumentam o tempo de construção do índice. Optimize com base no tamanho do conjunto de dados e nos recursos disponíveis. Na maioria dos casos, recomendamos que você defina um valor dentro deste intervalo: [32, 4096].
PQ	m	O número de sub-vectores (utilizados para quantização) para dividir cada vetor de alta dimensão durante o processo de quantização.	Tipo: Inteiro Intervalo: [1, 65536] Valor predefinido: Nenhum	Um valor m mais elevado pode melhorar a precisão, mas também aumenta a complexidade computacional e a utilização de memória. m tem de ser um divisor da dimensão do vetor(D) para garantir uma decomposição adequada. Um valor geralmente recomendado é m = D/2. Na maioria dos casos, recomendamos que defina um valor dentro deste intervalo: [D/8, D].
	nbits	O número de bits utilizados para representar o índice do centróide de cada sub-vetor na forma comprimida. Determina diretamente o tamanho de cada livro de códigos. Cada livro de códigos conterá centroides de 2nbits. Por exemplo, se nbits estiver definido para 8, cada sub-vetor será representado por um índice de centróide de 8 bits. Isto permite28 (256) centróides possíveis no livro de códigos para esse sub-vetor.	Tipo: Integer Intervalo: [1, 24] Valor por defeito: 8	Um valor nbits mais alto permite livros de códigos maiores, potencialmente levando a representações mais precisas dos vectores originais. No entanto, isso também significa usar mais bits para armazenar cada índice, resultando em menos compactação. Na maioria dos casos, recomendamos que defina um valor dentro deste intervalo: [1, 16].

Parâmetros de pesquisa específicos do índice

A tabela a seguir lista os parâmetros que podem ser configurados em search_params.params ao pesquisar no índice.

	Parâmetro	Descrição	Intervalo de valores	Sugestão de ajuste
FIV	nprobe	O número de clusters para procurar candidatos.	Tipo: Integer Intervalo: [1, nlist] Valor predefinido: 8	Valores mais altos permitem que mais clusters sejam pesquisados, melhorando a recuperação ao expandir o escopo da pesquisa, mas ao custo de maior latência de consulta. Defina nprobe proporcionalmente a nlist para equilibrar velocidade e precisão. Na maioria dos casos, recomendamos que você defina um valor dentro deste intervalo: [1, nlist].