DiskANN: Uma solução ANNS baseada em disco com alta revocação e alto QPS em conjunto de dados em escala de bilhões
“DiskANN: Busca Rápida e Precisa de Vizinhos Mais Próximos em Bilhões de Pontos em um Único Nó” é um artigo publicado na NeurIPS em 2019. O artigo apresenta um método de ponta para realizar a construção de índices e a busca em conjuntos de dados na escala de bilhões usando uma única máquina com apenas 64 GB de RAM e um SSD grande o suficiente. Além disso, ele satisfaz os três requisitos de ANNS (Busca Aproximada do Vizinho Mais Próximo) em conjuntos de dados de larga escala: alta revocação, baixa latência e alta densidade (número de nós em uma única máquina). Esse método constrói um índice baseado em grafos em um conjunto de dados na escala de bilhões SIFT-1B usando uma única máquina com 64 GB de RAM e uma CPU de 16 núcleos, atingindo 5000 QPS (consultas por segundo) com mais de 95 % de recall@1, e latência média inferior a 3 ms.
Autores
Suhas Jayaram Subramanya: Ex-funcionário do Microsoft India Research Institute, doutorando da CMU. Os principais interesses de pesquisa são computação de alto desempenho e algoritmos de aprendizado de máquina para dados de larga escala.
Devvrit: Assistente de Pesquisa de Pós-Graduação na The University of Texas at Austin. Seus interesses de pesquisa são ciência da computação teórica, aprendizado de máquina e aprendizado profundo.
Rohan Kadekodi: Doutorando na University of Texas. Sua área de pesquisa é sistemas e armazenamento, incluindo principalmente armazenamento persistente, sistema de arquivos e armazenamento kV.
Ravishankar Krishaswamy: Pesquisador principal do Microsoft Indian Research Institute. Doutor pela CMU. A área de pesquisa é o algoritmo de aproximação baseado em grafos e agrupamento.
Harsha Vardhan Simhadri: Pesquisador principal do Microsoft Indian Research Institute. Doutor pela CMU. No passado, estudou algoritmos paralelos e sistemas de tempo de execução. Agora, seu principal trabalho é desenvolver novos algoritmos e escrever modelos de programação.
Motivações
A maioria dos algoritmos ANNS convencionais faz algumas compensações entre desempenho de construção de índices, desempenho de busca e revocação. Algoritmos baseados em grafos, como HNSW e NSG, são atualmente métodos de ponta em termos de desempenho de busca e revocação. Como o método de indexação baseado em grafos residente em memória ocupa muita memória, é relativamente difícil indexar e buscar em um conjunto de dados de larga escala usando uma única máquina com recursos de memória limitados.
Muitas aplicações exigem respostas rápidas de ANNS baseada em distância euclidiana em conjuntos de dados na escala de bilhões. Abaixo estão duas soluções principais:
Índice invertido + quantização: agrupar o conjunto de dados em M partições e comprimir o conjunto de dados usando esquemas de quantização como PQ (Quantização por Produto). Essa solução produz baixa revocação devido a uma perda de precisão causada pela compressão de dados. Aumentar o topk ajuda a melhorar a revocação, enquanto o QPS cairia correspondentemente.
Dividir e indexar: dividir o conjunto de dados em vários fragmentos disjuntos e construir um índice em memória para cada fragmento. Quando as solicitações de consulta chegam, a busca será realizada nos índices de cada fragmento e os resultados serão retornados após a fusão. Essa solução causa a superexpansão da escala do conjunto de dados e, portanto, são necessárias mais máquinas devido à restrição de recursos de memória em uma única máquina, levando a baixo QPS.
Ambas as soluções mencionadas acima são limitadas pela restrição de memória de uma única máquina. Este artigo propõe o projeto de um mecanismo de indexação residente em SSD para resolver esse problema. O desafio da indexação residente em SSD é reduzir o número de acessos aleatórios ao disco e o número de solicitações de acesso ao disco.
Contribuições
Este artigo apresenta um esquema ANNS residente em SSD chamado DiskANN, que pode oferecer suporte efetivo à busca em conjuntos de dados de larga escala. Esse esquema é baseado em um algoritmo baseado em grafos apresentado neste artigo: Vamana. As contribuições deste artigo incluem:
DiskANN pode indexar e buscar em um conjunto de dados na escala de bilhões com mais de 100 dimensões em uma única máquina com 64 GB de RAM, fornecendo mais de 95% de recall@1 com latências inferiores a 5 milissegundos.
Um novo algoritmo baseado em grafos chamado Vamana, com um raio de busca menor do que os de NSG e HNSW, foi proposto para minimizar o número de acessos ao disco.
Vamana pode funcionar em memória e seu desempenho não é mais lento do que NSG e HNSW.
Índices Vamana menores, construídos em partições sobrepostas do grande conjunto de dados, podem ser mesclados em um único grafo sem perder conectividade.
Vamana pode ser combinado com esquemas de quantização, como PQ. A estrutura do grafo e os dados originais são armazenados no disco, enquanto os dados comprimidos são mantidos em memória.
Vamana
Este algoritmo é semelhante à ideia do NSG[2][4] (para aqueles que não entendem NSG, consultem a Referência [2], e se não quiserem ler artigos, podem consultar a Referência [4]). A principal diferença entre eles está na estratégia de poda. Para ser preciso, um comutador alpha foi adicionado à estratégia de poda do NSG. A ideia principal da estratégia de poda do NSG é que a escolha dos vizinhos do ponto-alvo seja o mais diversa possível. Se o novo vizinho estiver mais próximo de um vizinho do ponto-alvo do que do ponto-alvo, não precisamos adicionar esse ponto ao conjunto de pontos vizinhos. Em outras palavras, para cada vizinho do ponto-alvo, não pode haver outros pontos vizinhos dentro do raio circundante dist (ponto-alvo, ponto vizinho). Essa estratégia de poda controla efetivamente o grau de saída do grafo e é relativamente radical. Ela reduz a ocupação de memória do índice, melhora a velocidade de busca, mas também reduz a precisão da busca. A estratégia de poda do Vamana é controlar livremente a escala da poda por meio do parâmetro alpha. O princípio de funcionamento é multiplicar a dist (um ponto vizinho, ponto candidato) na condição de poda por um parâmetro alpha (não menor que 1). Somente quando a dist (ponto-alvo, um determinado ponto candidato) é maior que a distância de referência ampliada é que a estratégia de poda é adotada, aumentando a tolerância da exclusão mútua entre os vizinhos do ponto-alvo.
O processo de indexação do Vamana é relativamente simples:
Inicializar um grafo aleatório;
Calcular o ponto de partida, que é semelhante ao ponto de navegação do NSG. Primeiro, encontre o centróide global e, em seguida, encontre o ponto mais próximo do centróide global como o ponto de navegação. A diferença entre Vamana e NSG é que a entrada do NSG já é um grafo de vizinhos mais próximos, portanto os usuários podem simplesmente fazer uma busca aproximada do vizinho mais próximo no ponto centróide diretamente no grafo de vizinhos inicial. No entanto, Vamana inicializa um grafo aleatório de vizinhos mais próximos, portanto os usuários não podem realizar busca aproximada diretamente no grafo aleatório. Eles precisam fazer uma comparação global para obter um ponto de navegação como ponto de partida das iterações subsequentes. O objetivo desse ponto é minimizar o raio médio de busca;
Realizar a Busca Aproximada do Vizinho Mais Próximo em cada ponto com base no grafo aleatório de vizinhos inicializado e no ponto de partida da busca determinado na etapa 2, tornar todos os pontos no caminho de busca os conjuntos de vizinhos candidatos e executar a estratégia de poda de arestas usando alpha = 1. Semelhante à do NSG, selecionar o conjunto de pontos no caminho de busca a partir do ponto de navegação como o conjunto de vizinhos candidatos aumentará algumas arestas longas e reduzirá efetivamente o raio de busca.
Ajustar alpha > 1 (o artigo recomenda 1.2) e repetir a etapa 3. Enquanto a etapa 3 é baseada em um grafo aleatório de vizinhos mais próximos, o grafo fica de baixa qualidade após a primeira iteração. Portanto, outra iteração é necessária para melhorar a qualidade do grafo, o que é muito importante para a taxa de recall.
Este artigo compara os três índices de grafos, ou seja, Vamana, NSG e HNSW. Em termos de desempenho de indexação e consulta, Vamana e NSG são relativamente próximos, e ambos superam ligeiramente o HNSW. Consulte a seção Experimento abaixo para os dados.
Figura 1.
Para visualizar o processo de construção do índice Vamana, o artigo fornece um grafo, no qual 200 pontos bidimensionais são usados para simular duas rodadas de iteração. A primeira linha usa alpha = 1 para podar as arestas. Pode-se ver que a estratégia de poda é relativamente radical, e um grande número de arestas é podado. Após aumentar o valor de alpha e afrouxar as condições de poda, muitas arestas são obviamente adicionadas de volta. No grafo final, são adicionadas várias arestas longas. Isso pode reduzir efetivamente o raio de busca.
DiskANN
Um computador pessoal com apenas 64GB de memória nem sequer comportaria um bilhão de itens de dados brutos, muito menos o índice construído sobre eles. Há dois desafios pela frente: 1. Como indexar um conjunto de dados em tão grande escala com recursos de memória limitados? 2. Como calcular a distância durante a busca se os dados originais não podem ser carregados na memória?
O artigo propôs as seguintes soluções:
Para o primeiro desafio: primeiro, dividir os dados em k clusters usando k-means e, em seguida, alocar cada ponto nos i clusters mais próximos. Geralmente, 2 é suficiente para o número i. Construir um índice Vamana baseado em memória para cada cluster e, por fim, mesclar k índices Vamana em um só.
Para o segundo desafio: construir o índice nos vetores originais e consultar vetores comprimidos. Construir índices no vetor original garante a qualidade do grafo, enquanto o vetor comprimido pode ser carregado na memória para busca de granularidade grosseira. Embora a busca com os vetores comprimidos possa causar perda de precisão, a direção geral estará correta desde que a qualidade do grafo seja alta o suficiente. O resultado final da distância será calculado usando o vetor original.
O layout do índice do DiskANN é semelhante ao dos índices de grafo em geral. O conjunto de vizinhos de cada ponto e os dados vetoriais originais são armazenados juntos. Isso faz melhor uso da localidade dos dados.
Como mencionado anteriormente, se os dados do índice forem armazenados no SSD, o número de acessos ao disco e as solicitações de leitura e gravação em disco devem ser reduzidos ao máximo para garantir baixa latência de busca. Portanto, o DiskANN propõe duas estratégias de otimização:
Cache de hotspots: armazenar em cache na memória todos os pontos dentro de C saltos a partir do ponto inicial. É melhor definir o valor de C entre 3 e 4.
Beam search: Simplificando, consiste em pré-carregar as informações dos vizinhos. Ao buscar o ponto p, o ponto vizinho de p precisa ser carregado do disco se não estiver na memória. Como uma pequena quantidade de operações de acesso aleatório ao SSD leva aproximadamente o mesmo tempo que uma operação de acesso a um único setor do SSD, as informações de vizinhos de W pontos não acessados podem ser carregadas de uma vez. W não pode ser definido nem muito grande nem muito pequeno. Um W grande desperdiçará recursos computacionais e largura de banda do SSD, enquanto um pequeno aumentará a latência de busca.
Experimento
O experimento consiste em três grupos:
Comparação entre índices baseados em memória: Vamana VS. NSG VS. HNSW
Conjuntos de dados: SIFT1M (128 dimensões), GIST1M (960 dimensões), DEEP1M (96 dimensões) e um conjunto de dados de 1M amostrado aleatoriamente de DEEP1B.
Parâmetros do índice (todos os conjuntos de dados usam o mesmo conjunto de parâmetros):
HNSW：M = 128, efc = 512.
Vamana: R = 70, L = 75, alpha = 1.2.
NSG: R = 60, L = 70, C= 500.
Os parâmetros de busca não são fornecidos no artigo, o que pode ser consistente com os parâmetros de indexação. Para a seleção de parâmetros, os parâmetros do NSG mencionados no artigo são baseados nos parâmetros listados no repositório GitHub do NSG para selecionar o grupo com melhor desempenho. Vamana e NSG são relativamente próximos, portanto os parâmetros também são definidos próximos. No entanto, a razão para a seleção dos parâmetros do HNSW não é fornecida. Acreditamos que o parâmetro M do HNSW é definido relativamente grande. Isso pode levar a uma comparação menos convincente entre índices baseados em grafos se seus graus de saída não forem definidos no mesmo nível.
Sob os parâmetros de indexação acima, o tempo de indexação de Vamana, HNSW e NSG é de 129s, 219s e 480s, respectivamente. O tempo de indexação do NSG inclui o tempo para construir o grafo inicial de vizinhos com EFANN [3].
Curva Recall-QPS:
Figure 2.
Pode-se ver na Figura 3 que Vamana tem um excelente desempenho nos três conjuntos de dados, semelhante ao NSG e ligeiramente melhor que o HNSW.
Comparação do raio de busca:
A partir da Figura 2.c, podemos ver que Vamana tem o caminho médio de busca mais curto sob a mesma taxa de recall em comparação com os do NSG e HNSW.
Comparação entre um índice construído de uma só vez e um índice grande mesclado
Conjunto de dados: SIFT1B
Os parâmetros do índice construído de uma só vez: L = 50, R = 128, alpha = 1.2. Após rodar por 2 dias em uma máquina DDR3 de 1800G, o pico de memória é de cerca de 1100 G, e o grau de saída médio é 113.9.
Procedimento de indexação baseado na mesclagem:
Treinar 40 clusters no conjunto de dados usando kmeans;
Cada ponto é distribuído nos 2 clusters mais próximos;
Construir um índice Vamana com L = 50, R = 64 e alpha = 1.2 para cada cluster;
Mesclar os índices de cada cluster.
Este índice gerou um índice de 384GB com um grau de saída médio de 92.1. Este índice rodou por 5 dias em uma máquina DDR4 de 64GB.
Os resultados da comparação são os seguintes (Figura 2a):
Figure 3.
Em conclusão:
O índice construído de uma só vez é significativamente melhor que o índice baseado em mesclagem;
O índice baseado em mesclagem também é excelente;
O esquema de indexação baseado em mesclagem também é aplicável ao conjunto de dados DEEP1B (Figura 2b).
Índice baseado em disco: DiskANN VS. FAISS VS. IVF-OADC+G+P
IVFOADC+G+P é um algoritmo proposto na Referência [5].
Este artigo compara apenas o DiskANN com IVFOADC+G+P, uma vez que a referência [5] provou que IVFOADC+G+P é melhor que FAISS. Além disso, FAISS requer recursos de GPU, que não são suportados por todas as plataformas.
IVF-OADC+G+P parece ser uma combinação de HNSW e IVF-PQ. Ele determina clusters usando HNSW e realiza a busca adicionando algumas estratégias de poda ao cluster-alvo.
O resultado está na Figura 2a. O 16 e 32 na figura são o tamanho do codebook. O conjunto de dados é SIFT1B, quantizado por OPQ.
Detalhes de implementação do código
O código-fonte do DiskANN é open-sourced em https://github.com/microsoft/DiskANN
Em janeiro de 2021, o código-fonte da solução de disco foi open-sourced.
A seguir, introduz principalmente o processo de indexação e o processo de busca.
Construção do índice
Há 8 parâmetros para construir o índice:
data_type: as opções incluem float/int8/uint8.
data_file.bin: O arquivo binário de dados original. Os dois primeiros inteiros no arquivo representam, respectivamente, o número total n de vetores do conjunto de dados e a dimensão vetorial dim. Os últimos n * dim * sizeof(data_type) bytes são dados vetoriais contínuos.
index_prefix_path: O prefixo do caminho do arquivo de saída. Depois que o índice é construído, vários arquivos relacionados ao índice serão gerados. Este parâmetro é o prefixo comum do diretório onde eles são armazenados.
R: O grau máximo de saída do índice global.
L: O parâmetro L do índice Vamana, o limite superior do tamanho do conjunto candidato.
B: O limite de memória ao consultar. Ele controla o tamanho do codebook PQ, em GB.
M: O limite de memória ao construir um índice. Ele determina o tamanho do fragmento, em GB.
T: O número de threads.
Processo de indexação (função de entrada: aux_utils.cpp::build_disk_index):
Gerar vários nomes de arquivos de saída de acordo com index_prefix_path.
Verificação de parâmetros.
Ler os metadados de data_file.bin para obter n e dim. Determinar o número de subespaços m do codebook de PQ de acordo com B e n.
generate_pq_pivots: Amostrar o ponto central do conjunto de treinamento de PQ usando a taxa de amostragem de p = 1500000/n uniformemente para treinar PQ globalmente.
generate_pq_data_from_pivots: Gerar o codebook global de PQ e salvar o ponto central e o codebook separadamente.
build_merged_vamana_index: fatie o conjunto de dados original, crie índices Vamana em segmentos e, por fim, mescle os índices em um só.
partition_with_ram_budget: Determine o número de fragmentos k de acordo com o parâmetro M. Faça uma amostragem do conjunto de dados usando kmeans, distribuindo cada ponto para os dois clusters mais próximos. Fragmente o conjunto de dados, e cada fragmento produz dois arquivos: um arquivo de dados e um arquivo de ID. O arquivo de ID e o arquivo de dados correspondem entre si, e cada ID no arquivo de ID corresponde a um vetor no arquivo de dados. Os IDs são obtidos numerando cada vetor dos dados originais de 0 a n-1. O ID é relativamente importante e está relacionado à mesclagem.
Faça uma amostragem global uniforme do conjunto de treinamento com uma taxa de amostragem de 1500000 / n;
Inicialize num_parts = 3. Itere a partir de 3:
- Faça num_parts-means++ no conjunto de treinamento na etapa i;
- Use uma taxa de amostragem de 0.01 para amostrar um conjunto de teste uniformemente de forma global e divida o conjunto de teste nos 2 clusters mais próximos;
- Conte o número de pontos em cada cluster e divida-o pela taxa de amostragem para estimar o número de pontos em cada cluster;
- Estime a memória exigida pelo maior cluster na etapa 3 de acordo com o tamanho do índice Vamana; se não exceder o parâmetro M, prossiga para a etapa iii; caso contrário, num_parts ++ e volte para a etapa 2;
Divida o conjunto de dados original em num_parts arquivos de grupo, cada grupo de arquivos inclui arquivos de dados fragmentados e arquivos de ID correspondentes aos dados fragmentados.
Crie índices Vamana separadamente para todas as fatias na etapa a e salve-os em disco;
merge_shards: mescle num_parts shard Vamana em um índice global:
Leia o arquivo de ID dos fragmentos num_parts em idmap. Este idmap é equivalente a estabelecer um mapeamento direto de fragmento->id;
Estabeleça um mapeamento reverso de id-> fragmentos de acordo com idmap e saiba em quais dois fragmentos cada vetor está;
Use um reader com cache de 1GB para abrir os índices Vamana de fatia num_parts e use um writer com cache de 1GB para abrir o arquivo de saída, pronto para mesclar;
Coloque num_parts pontos de navegação do índice Vamana no arquivo de ponto central, que será usado durante a busca;
Comece a mesclar de acordo com o ID do menor para o maior, leia o conjunto de pontos vizinhos de cada vetor original em cada fragmento por vez de acordo com o mapeamento reverso, remova duplicatas, embaralhe, trunque e grave no arquivo de saída. Como o fatiamento foi originalmente ordenado globalmente, e agora a mesclagem também está em ordem, o ID no índice final gravado e o ID dos dados originais têm uma correspondência um-para-um.
Exclua arquivos temporários, incluindo arquivos de fragmento, índices de fragmento e arquivos de ID de fragmento.
7.create_disk_layout: O índice global gerado na etapa 6 possui apenas uma tabela de adjacência compacta. Esta etapa é para alinhar o índice. A tabela de adjacência e os dados originais são armazenados juntos. Ao buscar, carregue a tabela de adjacência e leia o vetor original junto para o cálculo preciso da distância. Também existe o conceito de SECTOR, com o tamanho padrão de 4096. Cada SECTOR contém apenas 4096 / node_size partes de informações de vetor. node_size = tamanho de vetor único + tamanho de tabela de adjacência de nó único.
8.Por fim, faça uma amostragem global uniforme de 150000 / n, salve-a e use-a para warmup durante a busca.
Busca
Há 10 parâmetros de busca:
index_type: As opções incluem Float/int8/uint8, semelhante ao primeiro parâmetro data_type ao criar um índice.
index_prefix_path: Consulte o parâmetro de índice index_prefix_path.
num_nodes_to_cache: Número de hotspots de cache.
num_threads: Número de threads de busca.
beamwidth: Limite superior do número de pontos de preload. O sistema determina se estiver definido como 0.
query_file.bin: Arquivo do conjunto de consultas.
truthset.bin: Arquivo do conjunto de resultados, "null" significa que o conjunto de resultados não é fornecido, o programa o calcula por si só;
K: topk;
result_output_prefix: Caminho para salvar os resultados de busca;
L*: Lista de parâmetros de busca. Múltiplos valores podem ser adicionados. Para cada L, informações estatísticas serão fornecidas durante a busca com diferentes L.
Processo de busca:
Carregar dados relacionados: carregar conjunto de consultas, dados dos pontos centrais PQ, dados do codebook, ponto inicial de busca e outros dados, e ler os metadados do índice.
Usar o conjunto de dados amostrado durante a indexação para executar cached_beam_search, contar os tempos de acesso de cada ponto e carregar no cache os num_nodes_to_cache pontos com a maior frequência de acesso.
Há uma operação WARMUP por padrão. Assim como na etapa 2, este conjunto de dados de amostra também é usado para executar um cached_beam_search.
De acordo com o número de parâmetros L fornecidos, cada L será executado com cached_beam_search novamente com o conjunto de consultas, e estatísticas como taxa de recall e QPS serão geradas. O processo de warmup e os dados de hotspot de estatísticas não são contados no tempo de consulta.
Sobre cached_beam_search:
Encontrar o candidato mais próximo do ponto de consulta a partir do ponto inicial candidato. A distância PQ é usada aqui, e o ponto inicial é adicionado à fila de busca.
Iniciar a busca:
A partir da fila de busca, não há mais que beam_width + 2 pontos não visitados. Se esses pontos estiverem no cache, adicione-os à fila de acertos do cache. Se não forem atingidos, adicione-os à fila de misses. Certifique-se de que o tamanho da fila de misses não exceda beam_width.
Enviar solicitações assíncronas de acesso ao disco para pontos na fila de misses.
Para os pontos atingidos pelo cache, usar os dados originais e os dados da consulta para calcular a distância exata, adicionar à fila de resultados e, em seguida, usar PQ para calcular a distância até os pontos vizinhos que ainda não foram visitados antes de adicionar à fila de busca. O comprimento da fila de busca é limitado pelos parâmetros.
Processar os pontos de miss do cache na etapa a, semelhante à etapa c.
Quando a fila de busca está vazia, a busca termina, e o topk da fila de resultados é retornado.
Resumo
Embora este seja um trabalho relativamente extenso, no geral é excelente. As ideias do artigo e do código são claras: dividir uma série de buckets sobrepostos por meio de k-means, depois dividir os buckets para construir um índice de mapa e, por fim, mesclar os índices, o que é uma ideia relativamente nova. Quanto ao índice de grafo em memória Vamana, ele é essencialmente uma versão inicializada aleatoriamente do NSG que pode controlar a granularidade da poda. Ao consultar, ele faz pleno uso de cache + pipeline, encobre parte do tempo de io e melhora o QPS. No entanto, de acordo com o artigo, mesmo que a condição da máquina não seja extraordinária, o tempo de treinamento leva até 5 dias, e a usabilidade é relativamente baixa. Otimizações no treinamento são definitivamente necessárias no futuro. Do ponto de vista do código, a qualidade é relativamente alta e pode ser usada diretamente no ambiente de produção.
Referências
[Cong Fu, Chao Xiang, Changxu Wang, and Deng Cai. Fast approximate nearest neighbor search with the navigating spreading-out graphs. PVLDB, 12(5):461 – 474, 2019. doi: 10.14778/3303753.3303754.] (http://www.vldb.org/pvldb/vol12/p461-fu.pdf)
Cong Fu and Deng Cai. GitHub - ZJULearning/efanna: biblioteca rápida para busca ANN e construção de grafo KNN.
Continue lendo
Zilliz Cloud Now Available in AWS Asia Pacific (Seoul)
Zilliz Cloud is now available in AWS Seoul — low-latency vector search, in-country data residency, and one-step migration for Korean AI teams. 31 regions across 5 clouds.
Creating Collections in Zilliz Cloud Just Got Way Easier
We've enhanced the entire collection creation experience to bring advanced capabilities directly into the interface, making it faster and easier to build production-ready schemas without switching tools.
Demystifying the Milvus Sizing Tool
Explore how to use the Sizing Tool to select the optimal configuration for your Milvus deployment.