Loading AI tools
Da Wikipédia, a enciclopédia livre
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]
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.
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]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.