PCA-tree: uma proposta para indexação multidimensional / PCA-Tree: a multidimensional access method proposal

AUTOR(ES)

Philipe Dalla Bernardina

DATA DE PUBLICAÇÃO

2007

RESUMO

Com o vislumbramento de aplicações que exigiam representações em espaços multidimensionais, surgiu a necessidade de desenvolvimento de métodos de acessos eficientes a estes dados representados em R^d. Dentre as aplicações precursoras dos métodos de acessos multidimensionais, podemos citar os sistemas de geoprocessamento, aplicativos 3D e simuladores. Posteriormente, os métodos de acessos multidimensionais também apresentaram-se como uma importante ferramenta no projeto de classificadores, principalmente classificadores pelos vizinhos mais próximos. Com isso, expandiu-se o espaço de representação, que antes se limitava no máximo a quatro dimensões, para dimensionalidades superiores a mil. Dentre os vários métodos de acesso multidimensional existentes, destaca-se uma classe de métodos baseados em árvores balanceadas com representação em R^d. Estes métodos constituem evoluções da árvore de acesso unidimenisonal B-tree e herdam várias características deste último. Neste trabalho, apresentamos alguns métodos de acessos dessa classe de forma a ilustrar a idéia central destes algoritmos e propomos e implementamos um novo método de acesso, a PCA-tree. A PCA-tree utiliza uma heurística de quebra de nós baseada na extração da componente principal das amostras a serem divididas. Um hiperplano que possui essa componente principal como seu vetor normal é definido como o elemento que divide o espaço associado ao nó. A partir dessa idéia básica geramos uma estrutura de dados e algoritmos que utilizam gerenciamento de memória secundária como a B-tree. Finalmente, comparamos o desempenho da PCA-tree com o desempenho de alguns outros métodos de acesso da classe citada, e apresentamos os prós e contras deste novo método de acesso através de análise de resultados práticos.

ASSUNTO(S)

indexing nearest neighbors classifier métodos de acessos espaciais spatial access methods indexação mutidimensional access methods métodos de acessos multidimensionais

Documentos Relacionados

• A árvore das estórias: uma proposta de tradução para Tree and Leaf, de J. R. R. Tolkien
• Uma proposta para gerência de correio eletrônico
• "DBM-tree: método de acesso métrico sensível à densidade local"
• Uma proposta de roteiro para diagnóstico de clusters
• Proposta de um método para diagnóstico da gestão de produção