Á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 que satisfaça e .
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
- ↑ a b Samet, Hanan. Foundations of multidimensional and metric data structures (em inglês). [S.l.: s.n.] ISBN 978-0-12-369446-1
- ↑ 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
- ↑ 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
- ↑ Brin, Sergey (1995). «Near Neighbor Search in Large Metric Spaces». 21st International Conference on Very Large Data Bases (VLDB) (em inglês)