IVF_RABITQCompatible with Milvus 2.6.x

O índice IVF_RABITQ é um algoritmo de indexação baseado na quantização binária que quantiza vectores FP32 em representações binárias. Este índice oferece uma eficiência de armazenamento excecional com um rácio de compressão de 1 para 32, mantendo taxas de recuperação relativamente boas. Suporta um refinamento opcional para obter uma maior recuperação à custa de armazenamento adicional, tornando-o um substituto versátil para IVF_SQ8 e IVF_FLAT em cenários com limitações de memória.

Síntese

O IVF_RABITQ significa Inverted File with RaBitQ quantization (Ficheiro invertido com quantização RaBitQ), combinando duas técnicas poderosas para uma pesquisa e armazenamento vectoriais eficientes.

IVF

O Inverted File (IVF) organiza o espaço vetorial em regiões gerenciáveis usando o agrupamento k-means. Cada cluster é representado por um centróide, que serve de ponto de referência para os vectores desse cluster. Esta abordagem de clustering reduz o espaço de pesquisa, permitindo que o algoritmo se concentre apenas nos clusters mais relevantes durante o processamento da consulta.

Para saber mais sobre os detalhes técnicos do IVF, consulte IVF_FLAT.

RaBitQ

O RaBitQ é um método de quantização binária de última geração com garantias teóricas, introduzido no artigo de investigação "RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search" (RaBitQ: Quantificação de vectores de alta dimensão com um limite de erro teórico para a pesquisa do vizinho mais próximo) de Jianyang Gao e Cheng Long.

O RaBitQ introduz vários conceitos inovadores:

Codificação de informação angular: Ao contrário da codificação espacial tradicional, o RaBitQ codifica a informação angular através da normalização do vetor. No IVF_RABITQ, os vectores de dados são normalizados em relação ao seu centróide IVF mais próximo, aumentando a precisão do processo de quantização.

Fundamentação teórica: A fórmula de aproximação da distância central é:

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

Onde:

• $or\mathbf{o_r}$ or é um vetor de dados do conjunto de dados
• $qr\mathbf{q_r}$ qr é um vetor de consulta
• $co\mathbf{c_o}$ co é o vetor de centróide FIV mais próximo para $or\mathbf{o_r}$ o r
• $C(\mathbf{o_r}, \mathbf{c_o})$ C$(\mathbf{o}$r, co ) e $C_1(\mathbf{o_r}, \mathbf{c_o})$ C ${}_{}(o$ r, c o ) são constantes pré-computadas
• $o~\tilde{\mathbf{o}}$ ~ é o vetor binário quantizado armazenado no índice
• $\tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle$ o ~$,$ q${}_{}-$ c${}_{}⟩$ representa a operação ponto-produto

Eficiência computacional: A natureza binária de $o~\tilde{\mathbf{o}}$ ~ torna os cálculos de distância extremamente rápidos, beneficiando particularmente das arquiteturas de CPU modernas com instruções dedicadas AVX-512 VPOPCNTDQ nos processadores Intel Ice Lake+ ou AMD Zen 4+.

Melhorias algorítmicas: O RaBitQ integra-se eficazmente com técnicas estabelecidas, como a abordagemFastScan e rotações aleatórias, para melhorar o desempenho.

IVF + RaBitQ

O índice IVF_RABITQ combina o agrupamento eficiente do IVF com a quantização binária avançada do RaBitQ:

1. Coarse Filtering: O IVF divide o espaço vetorial em clusters, reduzindo significativamente o âmbito da pesquisa ao concentrar-se nas regiões de cluster mais relevantes.

2. Quantização binária: Dentro de cada cluster, o RaBitQ comprime os vectores em representações binárias, preservando as relações de distância essenciais através de garantias teóricas.

3. Refinamento opcional: Quando ativado, o índice armazena dados refinados adicionais utilizando formatos de maior precisão (SQ6, SQ8, FP16, BF16 ou FP32) para melhorar as taxas de recuperação à custa de um maior armazenamento.

Milvus implementa IVF_RABITQ utilizando as seguintes cadeias de caracteres de fábrica FAISS:

• Com refinamento: "RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• Sem refinamento: "RR({dim}),IVF{nlist},RaBitQ"

Construir índice

Para construir um índice IVF_RABITQ 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_RABITQ", # 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={
        "nlist": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

Nesta configuração:

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

• 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. Para obter detalhes, consulte Parâmetros de construção de í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 mais informações, 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": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement magnification factor
    }
}

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. Para obter detalhes, 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 construir 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. Cada cluster, representado por um centroide, armazena uma lista de vectores. O aumento deste parâmetro reduz o número de vectores em cada cluster, criando partições mais pequenas e mais focadas.	Tipo: Integer Intervalo: [1, 65536] Valor padrão: 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].
RaBitQ	refine	Ativa o processo de refinamento e armazena os dados refinados.	Tipo: Booleano Range: [true, false] Valor predefinido: false	Defina para true se for necessária uma taxa de recuperação de 0,9+. A ativação do refinamento melhora a precisão mas aumenta os requisitos de armazenamento e o tempo de construção do índice.
	refine_type	Define a representação de dados utilizada para refinamento quando refine está ativado.	Tipo: String Range: [SQ6, SQ8, FP16, BF16, FP32] Valor predefinido: Nenhum	Os valores listados são apresentados em ordem crescente de taxa de recuperação, decrescente de QPS e crescente de tamanho de armazenamento. SQ8 é recomendado como ponto de partida, oferecendo um bom equilíbrio entre precisão e uso de recursos.

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. Os valores mais elevados permitem pesquisar mais clusters, melhorando a recuperação através da expansão do âmbito da pesquisa, mas à custa de uma maior latência da consulta.	Tipo: Inteiro Intervalo: [1, nlist] Valor padrão: 8	Aumentar este valor melhora a recuperação, mas pode tornar a pesquisa mais lenta. Defina nprobe proporcionalmente a nlist para equilibrar a velocidade e a precisão. Na maioria dos casos, recomendamos que defina um valor dentro deste intervalo: [1, nlist].
RaBitQ	rbq_query_bits	Define se é aplicada a quantização escalar adicional de um vetor de consulta. Se definido para 0, a consulta é utilizada sem quantização. Se definido para um valor entre [1, 8], a consulta é pré-processada utilizando a quantização escalar de n bits.	Tipo: Inteiro Intervalo: [0, 8] Valor predefinido: 0	O valor padrão 0 fornece a taxa de recuperação máxima, mas o desempenho mais lento. Recomendamos testar os valores 0, 8 e 6, pois eles fornecem taxas de recuperação semelhantes, sendo 6 o mais rápido. Use valores menores para requisitos de recuperação mais altos.
	refine_k	O processo de refinamento usa quantização de maior qualidade para escolher o número necessário de vizinhos mais próximos de um conjunto refine_k vezes maior de candidatos escolhidos usando IVF_RABITQ.	Tipo: Float Range: [1, float_max) Valor predefinido: 1	Valores mais altos em refine_k diminuem o QPS, mas aumentam a taxa de recuperação. Comece com 1 e teste os valores 2, 3, 4, e 5 para encontrar a melhor relação entre QPS e recuperação para o seu conjunto de dados.