Árvore métrica

Uma árvore métrica é qualquer árvore especializada na índexação de dados em espaços métricos. Árvores métricas exploram as propriedades dos espaços métricos, tais como a desigualdade triangular para acessar os dados de forma mais eficiente. Exemplos incluem árvores M, árvores VP, árvores MVP, e árvores Burkhard-Keller.^[1]

Busca multidimensional

A maioria dos algoritmos e estruturas de dados para pesquisa em um conjunto de dados são baseados no algoritmo clássico de pesquisa binária, e generalizações como a árvore k-d ou a range tree funcionam intercalando o algoritmo de pesquisa binária sobre coordenadas separadas e o tratando cada coordenada espacial com um órgão de pesquisa idependente. Estas estruturas de dados são adequados para problemas de consulta por abrangência consultando cada ponto ${\displaystyle (x,y)}$ que satisfaça ${\displaystyle {\mbox{min}}_{x}\leq x\leq {\mbox{max}}_{x}}$ e ${\displaystyle {\mbox{min}}_{y}\leq y\leq {\mbox{max}}_{y}}$.

Uma limitação das estruturas de busca multidimensional é que elas só são aplicáveis para a pesquisa sobre objetos que podem ser representados como vetores (de forma vetorial). Elas não são aplicáveis para o caso mais geral em que é dada apenas uma coleção de objetos e uma função para medir a distância ou similaridade entre dois objetos. Se, por exemplo, alguém criar uma função que retorna um valor que indica o grau de similaridade entre uma imagem e outra, um problema natural de algoritmos seria: em um conjunto de dados de imagens, encontrar aquelas que são similares de acordo com a função, para uma dada imagem de consulta.

Estruturas de dados métricas

Se não há estrutura para medição de similaridade, então uma busca por força bruta comparando a imagem de consulta com todas imagens do conjunto de dados é o melhor que pode ser feito.^{[carece de fontes?]} Se, no entanto, a função de semelhança satisfaz a desigualdade triangular, então é possível utilizar o resultado de cada comparação para assim reduzir o conjunto de candidatos a ser examinados.

O primeiro artigo sobre árvores métricas, bem como o primeiro uso do termo "metric tree" na literatura, foi feito por Jeffrey Uhlmann, em 1991.^[2] Outros pesquisadores já estavam trabalhando de forma independente em estruturas de dados semelhantes. Em particular, Peter Yianilos que alegou ter descoberto independentemente o mesmo método, na qual ele chamou de árvore vantage-point (Árvore VP).^[3] A pesquisa sobre as árvores métricas floresceu na década de 1990 e incluiu também um estudo feito pelo co-fundador do Google Sergey Brin, a respeito do seu uso em bancos de dados muito grandes.^[4] O primeiro livro sobre estruturas de dados métricas foi publicado em 2006.^[1]

Referências

1. Samet, Hanan. Foundations of multidimensional and metric data structures (em inglês). [S.l.: s.n.] ISBN 978-0-12-369446-1
2. Uhlmann, Jeffrey (1991). «Satisfying General Proximity/Similarity Queries with Metric Trees». Information Processing Letters (em inglês). 40 (4). doi:10.1016/0020-0190(91)90074-r
3. Yianilos, Peter N. (1993). «Data structures and algorithms for nearest neighbor search in general metric spaces». Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms (em inglês). Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 311–321. pny93. Consultado em 22 de agosto de 2008
4. Brin, Sergey (1995). «Near Neighbor Search in Large Metric Spaces». 21st International Conference on Very Large Data Bases (VLDB) (em inglês)