Os algoritmos para busca aos k-vizinhos mais pr´oximos tamb´em procuram reduzir o espa¸co de busca fazendo uso de propriedades do dom´ınio de dados. Contudo, ao contr´ario do que ocorre na Rq, na k-NNq n˜ao existe um raio de consulta definido a princ´ıpio.
O primeiro algoritmo proposto para resolver k-NNq em ´ındices, usualmente chamado Depth-First k-NN, percorre recursivamente a estrutura utilizando um raio dinˆamico, que inicialmente engloba todos os objetos indexados pela estrutura, e ´e ajustado a medida que o conjunto resposta vai sendo preenchido com os k elementos requisitados. Esta estrat´egia permite o descarte de elementos e sub´arvores durante a busca com base na distˆancia entre o elemento de consulta e o k-´esimo elemento encontrado at´e o momento.
A ordem em que a estrutura de indexa¸c˜ao ´e percorrida n˜ao influencia o desempenho das consultas por abrangˆencia, mas pode influenciar muito o desempenho dos algoritmos de consultas aos vizinhos mais pr´oximos. Quanto mais cedo forem encontrados os elemen- tos mais pr´oximos ao elemento de consulta, mais rapidamente o raio limitante dinˆamico ser´a reduzido, aumentando as possibilidades de poda. Com base nessa premissa, Rous- sopoulos et al. (1995) propuseram o algoritmo conhecido como Best-First k-NN, que explora a ordem de visita¸c˜ao dos n´os em uma k-NNq utilizando uma fila de prioridade global, organizada em ordem crescente de distˆancia m´ınima (mindist) entre o elemento de consulta e a regi˜ao coberta por uma sub´arvore. Inicialmente, a raiz da ´arvore ´e inse- rida na fila de prioridade global. A cada passo do algoritmo, o elemento com a menor distˆancia ´e removido da fila de prioridade, pois a sub´arvore enraizada neste elemento tem a maior probabilidade de conter elementos mais pr´oximos ao elemento de consulta dentre as sub´arvores n˜ao visitadas. Outra estrat´egia complementar usada ´e utilizar a menor distˆancia m´axima (minmaxdist) entre o elemento de consulta e a regi˜ao de abrangˆencia de uma sub´arvore. Esse valor pode ser usado para reduzir o raio dinˆamico, pois garante a existˆencia de um elemento situado a no m´aximo essa distˆancia do elemento de consulta.
Uma terceira abordagem se baseia no uso de algoritmos incrementais para busca aos vizinhos mais pr´oximos (Incremental k-NN), que procuram calcular de maneira eficiente o k+1 vizinho mais pr´oximo, dado que os k vizinhos j´a foram calculados (Hjaltason e Samet, 1999; Park e Kim, 2003). Para isso, eles utilizam uma fila de prioridade global, que cont´em os n´os a serem processados e tamb´em a resposta para a consulta (elementos). Al´em disso, os algoritmos definem heur´ısticas que garantem que os k elementos mais pr´oximos est˜ao sempre no in´ıcio da lista, e para obter o k + 1-´esimo elemento n˜ao ´e necess´ario reiniciar a busca, bastando continuar percorrendo a fila de prioridade a partir do passo anterior. O problema dessa t´ecnica ´e o custo de gerenciamento da fila de prioridade, que tende a ser muito elevado, degenerando o desempenho.
Uma outra estrat´egia de aprimoramento consiste em estimar um raio inicial para a k-NNq, de tal forma que a capacidade de poda do algoritmo seja potencializada. Vieira
et al. (2007) propuseram utilizar a dimens˜ao de correla¸c˜ao fractal (D2) do conjunto de
dados para realizar essa estimativa, obtendo desempenho consideravelmente superior com rela¸c˜ao `a inicializa¸c˜ao do raio dinˆamico com ∞. Esta estrat´egia pode ser utilizada para acelerar qualquer um dos algoritmos de k-NNq apresentados, embora os autores tenham implementado essa id´eia sobre o Best-First k-NN. A principal limita¸c˜ao dessa proposta ´e que ´e preciso que exista uma quantidade de elementos j´a armazenada para que a dimens˜ao de correla¸c˜ao fractal do conjunto possa ser calculada. Quando n˜ao ´e poss´ıvel calcular o valor de D2, essa estrat´egia recai na abordagem b´asica, onde o raio dinˆamico ´e iniciado
com ∞.
Finalmente, existem v´arias abordagens que utilizam heur´ısticas para responder a con- sultas aproximadas aos vizinhos mais pr´oximos, tais como o trabalho de Pan e Manocha (2011), baseado na t´ecnica LSH (Locality Sensitive Hashing) com implementa¸c˜ao em uni- dades de processamento gr´afico, e o trabalho de Tao et al. (2010), que prop˜oe uma varia¸c˜ao da t´ecnica LSH sobre ´arvores B, denominada LSB-tree (Locality-Sensitive B-tree).
O restante desta subse¸c˜ao detalha o algoritmo Best-First k-NN implementado sobre a Slim-tree. Na Slim-tree, a distˆancia m´ınima entre um elemento de consulta sq e uma
sub´arvore Tsi, cuja abrangˆencia ´e uma bola centrada em si com raio ri, ´e dada por:
mindist(sq, Tsi) = max{δ(sq, si) − ri, 0} (3.3)
uma vez que nenhum elemento em Tsi pode estar a uma distˆancia de sq menor que
δ(sq, si) − ri. Esse valor ´e usado para organizar a fila de prioridade global (priorQueue)
do algoritmo.
O algoritmo usa tamb´em a estrutura de dados result, para armazenar os vizinhos mais pr´oximos encontrados e a sua distˆancia do elemento de consulta. A distˆancia entre sq e o k-´esimo elemento corrente ´e obtida por meio da fun¸c˜ao getMaxDistance() da
estrutura result, que faz o papel do raio de busca dinˆamico, uma vez que qualquer sub´arvore tal que mindist(sq, Tsi) > result.getMaxDistance() pode ser seguramente
podada.
Para possibilitar a realiza¸c˜ao de podas na busca enquanto o processo ainda est´a visi- tando n´os ´ındice, ´e preciso definir a menor distˆancia m´axima entre o elemento de consulta sq e uma sub´arvore Tsi. Na Slim-tree esse valor ´e dado por:
minmaxdist(sq, Tsi) = δ(sq, si) + ri (3.4)
Esse limite superior pode ser utilizado na estrutura result para descartar elementos e sub´arvores e ajustar o raio dinˆamico de consulta, pois garantidamente existe um elemento sj na sub´arvore Tsi tal que δ(sj, sq) ≤ minmaxdist(sq, Tsi).
O Algoritmo 3.2 apresenta a consulta aos k-vizinhos mais pr´oximos na Slim-tree. O resultado e a fila de prioridade s˜ao inicializados, adicionando o n´o raiz `a fila de prioridade
Algoritmo 3.2: Consulta aos k-vizinhos mais pr´oximos em um MAM (knnQuery) Entrada: rootNode, sq, k Sa´ıda: result in´ıcio 1 result ← ∅; 2 priorQueue ← ∅; 3 priorQueue.add(rootNode, ∞); 4 result.setMaxDistance(∞); 5
enquantopriorQueue 6= ∅ fa¸ca
6
node ← priorQueue.removeMin(); 7
senode ´e um n´o ´ındice ent˜ao
8
para cadasi em node fa¸ca
9
se|δ(sq, srep) − δ(srep, si)| ≤ result.getMaxDistance()+ri ent˜ao
10
minDistance ← mindist(sq, Tsi);
11
seminDistance ≤ result.getMaxDistance() ent˜ao
12
priorQueue.add(P tr(Tsi), minDistance);
13
minMaxDistance ← minmaxdist(sq, Tsi);
14
seminMaxDistance < result.getMaxDistance() ent˜ao
15
result.setMaxDistance(minMaxDistance); 16
remova todas as entradas de priorQueue tais que 17 mindist(sq, Tsi) > minMaxDistance; 18 fim 19 fim 20 fim 21 fim 22
sen˜ao /* node ´e um n´o folha */
23
para cadasi em node fa¸ca
24
se|δ(sq, srep) − δ(srep, si)| ≤ result.getMaxDistance() ent˜ao
25
distance ← δ(sq, si);
26
sedistance ≤ result.getMaxDistance() ent˜ao
27
result.add(si, distance);
28
if result.getNumElements() > k then result.cutElements(k);
29
seresult.getMaxDistance() foi atualizado ent˜ao
30
remova todas as entradas de priorQueue tais que 31 mindist(sq, Tsi) > result.getMaxDistance(); 32 fim 33 fim 34 fim 35 fim 36 fim 37 fim 38 retornaresult; 39 fim 40
(linhas 2-4). O raio dinˆamico do resultado ´e definido como ∞ (linha 5). Enquanto houver elementos na fila de prioridade, o elemento com distˆancia m´ınima estimada ´e retirado (linhas 6-7). Se o n´o corrente ´e um n´o ´ındice, cada elemento do n´o ´e avaliado e o algoritmo tenta podar a sub´arvore respectiva usando a desigualdade triangular (linhas 8-10). Se a sub´arvore n˜ao puder ser podada, o algoritmo calcula a distˆancia m´ınima entre o elemento de consulta e a sub´arvore Tsi, o que implica em calcular δ(sq, si), e verifica novamente se a
sub´arvore pode ser descartada, com base neste valor (linhas 11-12). Caso a poda n˜ao seja poss´ıvel, a sub´arvore ´e inserida na fila de prioridade, com base no valor mindist(sq, Tsi),
para ser processada posteriormente (linha 13). Em seguida, o algoritmo calcula a menor distˆancia m´axima entre sqe Tsi (linha 14). Se esse valor for menor que a distˆancia m´axima
do resultado atual, o algoritmo atualiza a distˆancia m´axima do resultado e remove as entradas da fila de prioridade cujas distˆancias s˜ao maiores que o novo raio de consulta, pois estas sub´arvores podem ser seguramente podadas neste momento (linhas 15-18). Se o n´o corrente ´e um n´o folha, cada elemento si do n´o ´e processado e verifica-se se pode
ser descartado pela desigualdade triangular sem a necessidade de calcular sua distˆancia ao elemento de consulta (linhas 24-25). Caso n˜ao seja poss´ıvel, essa distˆancia ´e calculada e verifica-se se o elemento deve ser inclu´ıdo na resposta (linha 26-27). Caso afirmativo, o elemento ´e inserido no resultado e, se com a inclus˜ao do novo elemento o resultado passar a ter mais do que k elementos, o elemento mais distante ´e eliminado, deixando o resultado com k elementos (linhas 28-29). Se ap´os esta ´ultima opera¸c˜ao a distˆancia m´axima for alterada, reduzindo o raio de consulta, as entradas da fila de prioridade com distˆancia m´ınima estimada maior que o novo raio de consulta s˜ao removidas (linhas 30-32). Ao esgotarem os elementos da fila de prioridade, o algoritmo retorna o resultado da consulta (linha 39).