• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 6
  • Tagged with
  • 6
  • 6
  • 6
  • 6
  • 6
  • 6
  • 4
  • 4
  • 4
  • 4
  • 4
  • 4
  • 2
  • 2
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

DBM-tree: método de acesso métrico sensível à densidade local / DBM-tree: metric access method sensitive to local density data

Vieira, Marcos Rodrigues 28 May 2004 (has links)
Um espaço métrico é definido por um conjunto de objetos e uma função de distância métrica, que é utilizada para avaliar o nível de similaridade entre estes objetos. Isto permite a elaboração de Métodos de Acesso Métricos (MAMs) capazes de responder consultas por similaridade nesses conjuntos em um tempo reduzido. Em geral, esses MAMs são materializados através de uma estrutura hierárquica chamada de árvore métrica. Normalmente essas árvores são mantidas balanceadas, pois isto tende a manter a altura da árvore mínima, reduzindo o número de acessos a disco necessários para responder às consultas. No entanto, é difícil manter as estruturas balanceadas sem a existência de sobreposição entre os nós que cobrem regiões de alta densidade de objetos. O efeito disto é a degradação do tempo das consultas, pois várias subárvores devem ser analisadas para compor as consultas. Em outras palavras, minimizar a sobreposição entre os nós aumenta a eficiência das árvores métricas. Um meio efetivo para isto é flexibilizar o balanceamento das árvores métricas. Este trabalho apresenta um novo MAM dinâmico, chamado de DBM-tree (Density-Based Metric tree), que permite flexibilizar o balanceamento da estrutura, minimizando o grau de sobreposição entre os nós em regiões densas e, conseqüentemente, aumentando o seu desempenho para responder às consultas. Essa flexibilização é ajustada pelo usuário e é rigidamente controlada pela estrutura. A profundidade da árvore é maior em regiões de alta densidade, procurando um equilíbrio entre o número de acessos a disco para avaliar múltiplas subárvores e para a busca em profundidade em cada subárvore. A DBM-tree possui um algoritmo de otimização chamado de DBM-Slim-Down, que melhora o desempenho das árvores através da reorganização de elementos entre os seus nós. Os experimentos feitos com dados reais e sintéticos mostram que a DBM-tree supera em desempenho os MAMs tradicionais. Ela é, em média, 50% mais rápida que os MAMs tradicionais e reduz o número de acessos a disco e cálculos de distância em até 50%. Depois de executado o algoritmo DBM-Slim-Down, o seu desempenho melhorou em até 30% para as consultas por abrangência e aos vizinhos mais próximos. Ainda, a DBM-tree é escalável considerando tempo total de processamento, número de acessos a disco e de cálculos de distância em relação ao tamanho do conjunto de dados indexado. / A metric space is defined as a set of objects and a metric distance function that is used to measure the similarity between these objects. It allows the development of Metric Access Methods (MAMs) that are able to answer similarity queries in these datasets quickly. Usually these MAMs are materialized through a hierarchical structure called metric trees. These trees are kept balanced because it tends to maintain the height of the tree small, aiming to reduce the number of disk access required to answer queries. However, it is difficult to maintain the tree balanced without overlapping nodes covering a large number of objects, leading to the degradation of query performance. In other words, reducing the overlap among nodes increases the performance of metric trees. A possible solution is to relax the need to keep metric trees balanced. This work presents a new dynamic MAM called DBM-tree (Density-Based Metric tree), which changes the rule that imposes a rigid balancing policy, allowing a small amount of unbalancing in some regions of it. This unbalancing minimizes the degree of overlapping among some high-density nodes and, consequently, increases query answering performance. The amount of relaxation is set by the user and is strongly enforced in the tree. The height of the tree is higher in high-density regions, in order to keep a balance between searching in various subtrees and searching deeply in each subtree. The DBM-tree has an optimization algorithm called DBM-Slim-Down that improves the performance in trees through reorganizing the elements among its nodes. The experiments performed over synthetic and real-world datasets showed that the DBM-tree outperforms the traditional MAMs. The DBM-tree is, in average, 50% faster than traditional MAMs and reduces the number of distance calculations and disk accesses up to 50%. After executing the DBM-Slim-Down algorithm, the performance achieves improvements up to 30% for range and k-nearest neighbor queries. Moreover, the DBM-tree is scalable regarding time, number of disk accesses and distance calculations.
2

DBM-tree: método de acesso métrico sensível à densidade local / DBM-tree: metric access method sensitive to local density data

Marcos Rodrigues Vieira 28 May 2004 (has links)
Um espaço métrico é definido por um conjunto de objetos e uma função de distância métrica, que é utilizada para avaliar o nível de similaridade entre estes objetos. Isto permite a elaboração de Métodos de Acesso Métricos (MAMs) capazes de responder consultas por similaridade nesses conjuntos em um tempo reduzido. Em geral, esses MAMs são materializados através de uma estrutura hierárquica chamada de árvore métrica. Normalmente essas árvores são mantidas balanceadas, pois isto tende a manter a altura da árvore mínima, reduzindo o número de acessos a disco necessários para responder às consultas. No entanto, é difícil manter as estruturas balanceadas sem a existência de sobreposição entre os nós que cobrem regiões de alta densidade de objetos. O efeito disto é a degradação do tempo das consultas, pois várias subárvores devem ser analisadas para compor as consultas. Em outras palavras, minimizar a sobreposição entre os nós aumenta a eficiência das árvores métricas. Um meio efetivo para isto é flexibilizar o balanceamento das árvores métricas. Este trabalho apresenta um novo MAM dinâmico, chamado de DBM-tree (Density-Based Metric tree), que permite flexibilizar o balanceamento da estrutura, minimizando o grau de sobreposição entre os nós em regiões densas e, conseqüentemente, aumentando o seu desempenho para responder às consultas. Essa flexibilização é ajustada pelo usuário e é rigidamente controlada pela estrutura. A profundidade da árvore é maior em regiões de alta densidade, procurando um equilíbrio entre o número de acessos a disco para avaliar múltiplas subárvores e para a busca em profundidade em cada subárvore. A DBM-tree possui um algoritmo de otimização chamado de DBM-Slim-Down, que melhora o desempenho das árvores através da reorganização de elementos entre os seus nós. Os experimentos feitos com dados reais e sintéticos mostram que a DBM-tree supera em desempenho os MAMs tradicionais. Ela é, em média, 50% mais rápida que os MAMs tradicionais e reduz o número de acessos a disco e cálculos de distância em até 50%. Depois de executado o algoritmo DBM-Slim-Down, o seu desempenho melhorou em até 30% para as consultas por abrangência e aos vizinhos mais próximos. Ainda, a DBM-tree é escalável considerando tempo total de processamento, número de acessos a disco e de cálculos de distância em relação ao tamanho do conjunto de dados indexado. / A metric space is defined as a set of objects and a metric distance function that is used to measure the similarity between these objects. It allows the development of Metric Access Methods (MAMs) that are able to answer similarity queries in these datasets quickly. Usually these MAMs are materialized through a hierarchical structure called metric trees. These trees are kept balanced because it tends to maintain the height of the tree small, aiming to reduce the number of disk access required to answer queries. However, it is difficult to maintain the tree balanced without overlapping nodes covering a large number of objects, leading to the degradation of query performance. In other words, reducing the overlap among nodes increases the performance of metric trees. A possible solution is to relax the need to keep metric trees balanced. This work presents a new dynamic MAM called DBM-tree (Density-Based Metric tree), which changes the rule that imposes a rigid balancing policy, allowing a small amount of unbalancing in some regions of it. This unbalancing minimizes the degree of overlapping among some high-density nodes and, consequently, increases query answering performance. The amount of relaxation is set by the user and is strongly enforced in the tree. The height of the tree is higher in high-density regions, in order to keep a balance between searching in various subtrees and searching deeply in each subtree. The DBM-tree has an optimization algorithm called DBM-Slim-Down that improves the performance in trees through reorganizing the elements among its nodes. The experiments performed over synthetic and real-world datasets showed that the DBM-tree outperforms the traditional MAMs. The DBM-tree is, in average, 50% faster than traditional MAMs and reduces the number of distance calculations and disk accesses up to 50%. After executing the DBM-Slim-Down algorithm, the performance achieves improvements up to 30% for range and k-nearest neighbor queries. Moreover, the DBM-tree is scalable regarding time, number of disk accesses and distance calculations.
3

Algoritmos de bulk-loading para o método de acesso métrico Onion-tree / Bulk-loading algorithms to the metric access method onion-tree

Carosia, Arthur Emanuel de Oliveira 27 May 2013 (has links)
Atualmente, a Onion-tree [Carélo et al., 2009] é o método de acesso métrico baseado em memória primária mais eficiente para pesquisa por similaridade disponível na literatura. Ela indexa dados complexos por meio da divisão do espaço métrico em regiões (ou seja, subespaços) disjuntas, usando para isso dois pivôs por nó. Para prover uma boa divisão do espaço métrico, a Onion-tree introduz as seguintes características principais: (i) procedimento de expansão, o qual inclui um método de particionamento que controla o número de subespaços disjuntos gerados em cada nó; (ii) técnica de substituição, a qual pode alterar os pivôs de um nó durante operações de inserção baseado em uma política de substituição que garante uma melhor divisão do espaço métrico, independente da ordem de inserção dos elementos; e (iii) algoritmos para a execução de consultas por abrangência e aos k-vizinhos mais próximos, de forma que esses tipos de consulta possam explorar eficientemente o método de particionamento da Onion-tree. Entretanto, a Onion-tree apenas oferece funcionalidades voltadas à inserção dos dados um-a-um em sua estrutura. Ela não oferece, portanto, uma operação de bulk-loading que construa o índice considerando todos os elementos do conjunto de dados de uma única vez. A principal vantagem dessa operação é analisar os dados antecipadamente para garantir melhor particionamento possível do espaço métrico. Com isto, a carga inicial de grandes volumes de dados pode ser melhor realizada usando a operação de bulk-loading. Este projeto de mestrado visa suprir a falta da operação de bulk-loading para a Onion-tree, por meio da proposta de algoritmos que exploram as características intrínsecas desse método de acesso métrico. No total, são propostos três algoritmos de bulk-loading, denominados GreedyBL, SampleBL e HeightBL, os quais utilizam respectivamente as seguintes abordagens: gulosa, amostragem e de estimativa da altura do índice. Testes experimentais realizados sobre conjuntos de dados com volume variando de 2.536 a 102.240 imagens e com dimensionalidade variando de 32 a 117 dimensões mostraram que os algoritmos propostos introduziram vantagens em relação à estrutura criada pelo algoritmo de inserção um-a-um da Onion-tree. Comparado com a inserção um-a-um, o tamanho do índice foi reduzido de 9% até 88%. Em consultas por abrangência, houve redução de 16% até 99% no número de cálculos de distância e de 9% a 99% no tempo gasto em relação à inserção. Em consultas aos k-vizinhos mais próximos, houve redução de 13% a 86% em número de cálculos de distância e de 9% até 63% no tempo gasto / The main-memory Onion-tree [Carélo et al., 2009] is the most efficient metric access method to date. It indexes complex data by dividing the metric space into several disjoint regions (i.e. subspaces) by using two pivots per node. To provide a good division of the metric space, the Onion-tree introduces the following characteristics: (i) expansion procedure, which provides a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) replacement technique, which can replace the pivots of a leaf node during insert operations based on a replacement policy that ensures a better division of the metric space, regardless of the insertion order of the elements; and (iii) algorithms for processing range and k-NN queries, so that these types of query can efficiently use the partitioning method of the Onion-tree. However, the Onion-tree only performs element-by-element insertions into its structure. Another important issue is the mass loading technique, called bulk-loading, which builds the index considering all elements of the dataset at once. This technique is very useful in the case of reconstructing the index or inserting a large number of elements simultaneously. Despite the importance of this technique, to the best of our knowledge, there are not in the literature bulk-loading algorithms for the Onion-tree. In this masters thesis, we fill this gap. We propose three algorithms for bulk-loading Onion-trees: the GreedyBL algorithm, the SampleBL algorithm and the HeightBL algorithm. These algorithms are based on the following approaches, respectively: greedy, sampling and estime height of the index. Performance tests with real-world data with different volumes (ranging from 2,536 to 102,240 images) and different dimensionalities (ranging from 32 to 117 dimensions) showed that the indices produced by the proposed algorithms are very compact. Compared with the element-by-element insertion, the size of the index reduced from 9% up to 88%. The proposed algorithms also provided a great improvement in query processing. They required from 16% up to 99% less distance calculations and were from 9% up to 99% faster than the element-by-element insertion to process range queries. Also, they required from 13% up to 86% less distance calculations and were from 9% up to 63% faster than the element-by-element insertion to process k-NN queries
4

Algoritmos de bulk-loading para o método de acesso métrico Onion-tree / Bulk-loading algorithms to the metric access method onion-tree

Arthur Emanuel de Oliveira Carosia 27 May 2013 (has links)
Atualmente, a Onion-tree [Carélo et al., 2009] é o método de acesso métrico baseado em memória primária mais eficiente para pesquisa por similaridade disponível na literatura. Ela indexa dados complexos por meio da divisão do espaço métrico em regiões (ou seja, subespaços) disjuntas, usando para isso dois pivôs por nó. Para prover uma boa divisão do espaço métrico, a Onion-tree introduz as seguintes características principais: (i) procedimento de expansão, o qual inclui um método de particionamento que controla o número de subespaços disjuntos gerados em cada nó; (ii) técnica de substituição, a qual pode alterar os pivôs de um nó durante operações de inserção baseado em uma política de substituição que garante uma melhor divisão do espaço métrico, independente da ordem de inserção dos elementos; e (iii) algoritmos para a execução de consultas por abrangência e aos k-vizinhos mais próximos, de forma que esses tipos de consulta possam explorar eficientemente o método de particionamento da Onion-tree. Entretanto, a Onion-tree apenas oferece funcionalidades voltadas à inserção dos dados um-a-um em sua estrutura. Ela não oferece, portanto, uma operação de bulk-loading que construa o índice considerando todos os elementos do conjunto de dados de uma única vez. A principal vantagem dessa operação é analisar os dados antecipadamente para garantir melhor particionamento possível do espaço métrico. Com isto, a carga inicial de grandes volumes de dados pode ser melhor realizada usando a operação de bulk-loading. Este projeto de mestrado visa suprir a falta da operação de bulk-loading para a Onion-tree, por meio da proposta de algoritmos que exploram as características intrínsecas desse método de acesso métrico. No total, são propostos três algoritmos de bulk-loading, denominados GreedyBL, SampleBL e HeightBL, os quais utilizam respectivamente as seguintes abordagens: gulosa, amostragem e de estimativa da altura do índice. Testes experimentais realizados sobre conjuntos de dados com volume variando de 2.536 a 102.240 imagens e com dimensionalidade variando de 32 a 117 dimensões mostraram que os algoritmos propostos introduziram vantagens em relação à estrutura criada pelo algoritmo de inserção um-a-um da Onion-tree. Comparado com a inserção um-a-um, o tamanho do índice foi reduzido de 9% até 88%. Em consultas por abrangência, houve redução de 16% até 99% no número de cálculos de distância e de 9% a 99% no tempo gasto em relação à inserção. Em consultas aos k-vizinhos mais próximos, houve redução de 13% a 86% em número de cálculos de distância e de 9% até 63% no tempo gasto / The main-memory Onion-tree [Carélo et al., 2009] is the most efficient metric access method to date. It indexes complex data by dividing the metric space into several disjoint regions (i.e. subspaces) by using two pivots per node. To provide a good division of the metric space, the Onion-tree introduces the following characteristics: (i) expansion procedure, which provides a partitioning method that controls the number of disjoint subspaces generated at each node; (ii) replacement technique, which can replace the pivots of a leaf node during insert operations based on a replacement policy that ensures a better division of the metric space, regardless of the insertion order of the elements; and (iii) algorithms for processing range and k-NN queries, so that these types of query can efficiently use the partitioning method of the Onion-tree. However, the Onion-tree only performs element-by-element insertions into its structure. Another important issue is the mass loading technique, called bulk-loading, which builds the index considering all elements of the dataset at once. This technique is very useful in the case of reconstructing the index or inserting a large number of elements simultaneously. Despite the importance of this technique, to the best of our knowledge, there are not in the literature bulk-loading algorithms for the Onion-tree. In this masters thesis, we fill this gap. We propose three algorithms for bulk-loading Onion-trees: the GreedyBL algorithm, the SampleBL algorithm and the HeightBL algorithm. These algorithms are based on the following approaches, respectively: greedy, sampling and estime height of the index. Performance tests with real-world data with different volumes (ranging from 2,536 to 102,240 images) and different dimensionalities (ranging from 32 to 117 dimensions) showed that the indices produced by the proposed algorithms are very compact. Compared with the element-by-element insertion, the size of the index reduced from 9% up to 88%. The proposed algorithms also provided a great improvement in query processing. They required from 16% up to 99% less distance calculations and were from 9% up to 99% faster than the element-by-element insertion to process range queries. Also, they required from 13% up to 86% less distance calculations and were from 9% up to 63% faster than the element-by-element insertion to process k-NN queries
5

Processamento de consultas analíticas com predicados de similaridade entre imagens em ambientes de data warehousing / Processing of analytical with similarity search predicates over images in data warehousing environments

Teixeira, Jefferson William 29 May 2015 (has links)
Um ambiente de data warehousing oferece suporte ao processo de tomada de decisão. Ele consolida dados de fontes de informação distribuições, autônomas e heterogêneas em um único componente, o data warehouse, e realiza o processamento eficiente de consultas analíticas, denominadas OLAP (on-line analytical processing). Um data warehouse convencional armazena apenas dados alfanuméricos. Por outro lado, um data warehouse de imagens armazena, além desses dados convencionais, características intrínsecas de imagens, permitindo a realização de consultas analíticas estendidas com predicados de similaridade entre imagens. Esses ambientes demandam, portanto, a criação de estratégias que possibilitem o processamento eficiente dessas consultas complexas e custosas. Apesar de haver na literatura trabalhos voltados a índices bitmap para ambientes de data warehousing e métodos de acesso métricos para melhorar o desempenho de consultas por similaridade entre imagens, no melhor do nosso conhecimento, não há uma técnica que investigue essas duas questões em um mesmo contexto. Esta dissertação visa preencher essa lacuna na literatura por meio das seguintes contribuições: (i) proposta do ImageDWindex, um mecanismo para a otimização de consultas analíticas estendidas com predicados de similaridade entre imagens; e (ii) definição de diferentes estratégias de processamento de consultas sobre data warehouses de imagens usando o ImageDW-index. Para validar as soluções propostas, foram desenvolvidas duas outras contribuições secundárias, que são: (iii) o ImageDW-Gen, um gerador de dados com o objetivo de povoar o data warehouse de imagens; e (iv) a proposta de quatro classes de consulta, as quais enfocam em diferentes custos de processamento dos predicados de similaridade entre imagens. Utilizando o ImageDW-Gen, foram realizados testes de desempenho para investigar as vantagens introduzidas pelas estratégias propostas, de acordo com as classes de consultas definidas. Comparado com o trabalho mais correlato existente na literatura, o uso do ImageDWindex proveu uma melhora no desempenho do processamento de consultas IOLAP que variou em média de 55,57% até 82,16%, considerando uma das estratégias propostas. / A data warehousing environment offers support to the decision-making process. It consolidates data from distributed, autonomous and heterogeneous information sources into one of its main components, the data warehouse. Furthermore, it provides effcient processing of analytical queries (i.e. OLAP queries). A conventional data warehouse stores only alphanumeric data. On the other hand, an image data warehouse stores not only alphanumeric data but also intrinsic features of images, thus allowing data warehousing environments to perform analytical similarity queries over images. This requires the development of strategies to provide efficient processing of these complex and costly queries. Although there are a number of approaches in the literature aimed at the development of bitmap index for data warehouses and metric access methods for the efficient processing of similarity queries over images, to the best of our knowledge, there is not an approach that investigate these two issues in the same setting. In this research, we fill this gap in the literature by introducing the following main contributions: (i) the proposal of the ImageDW-index, an optimization mechanism aimed at the efficient processing of analytical queries extended with similarity predicates over images; and (ii) definition of different processing strategies for image data warehouses using the ImageDW-index. In order to validate these main proposals, we also introduce two secondary contributions, as follows: (iii) the ImageDW-Gen, a data generator to populate image data warehouses; and (iv) the proposal of four query classes, each one enforcing different query processing costs associated to the similarity predicates in image data warehousing environments. Using the ImageDW-Gen, performance tests were carried out in order to investigate the advantages introduced by the proposed strategies, according to the query classes. Compared to the most related work available in the literature, the ImageDW-index provided a performance gain that varied from 55.57% to 82.16%, considering one of the proposed strategies.
6

Processamento de consultas analíticas com predicados de similaridade entre imagens em ambientes de data warehousing / Processing of analytical with similarity search predicates over images in data warehousing environments

Jefferson William Teixeira 29 May 2015 (has links)
Um ambiente de data warehousing oferece suporte ao processo de tomada de decisão. Ele consolida dados de fontes de informação distribuições, autônomas e heterogêneas em um único componente, o data warehouse, e realiza o processamento eficiente de consultas analíticas, denominadas OLAP (on-line analytical processing). Um data warehouse convencional armazena apenas dados alfanuméricos. Por outro lado, um data warehouse de imagens armazena, além desses dados convencionais, características intrínsecas de imagens, permitindo a realização de consultas analíticas estendidas com predicados de similaridade entre imagens. Esses ambientes demandam, portanto, a criação de estratégias que possibilitem o processamento eficiente dessas consultas complexas e custosas. Apesar de haver na literatura trabalhos voltados a índices bitmap para ambientes de data warehousing e métodos de acesso métricos para melhorar o desempenho de consultas por similaridade entre imagens, no melhor do nosso conhecimento, não há uma técnica que investigue essas duas questões em um mesmo contexto. Esta dissertação visa preencher essa lacuna na literatura por meio das seguintes contribuições: (i) proposta do ImageDWindex, um mecanismo para a otimização de consultas analíticas estendidas com predicados de similaridade entre imagens; e (ii) definição de diferentes estratégias de processamento de consultas sobre data warehouses de imagens usando o ImageDW-index. Para validar as soluções propostas, foram desenvolvidas duas outras contribuições secundárias, que são: (iii) o ImageDW-Gen, um gerador de dados com o objetivo de povoar o data warehouse de imagens; e (iv) a proposta de quatro classes de consulta, as quais enfocam em diferentes custos de processamento dos predicados de similaridade entre imagens. Utilizando o ImageDW-Gen, foram realizados testes de desempenho para investigar as vantagens introduzidas pelas estratégias propostas, de acordo com as classes de consultas definidas. Comparado com o trabalho mais correlato existente na literatura, o uso do ImageDWindex proveu uma melhora no desempenho do processamento de consultas IOLAP que variou em média de 55,57% até 82,16%, considerando uma das estratégias propostas. / A data warehousing environment offers support to the decision-making process. It consolidates data from distributed, autonomous and heterogeneous information sources into one of its main components, the data warehouse. Furthermore, it provides effcient processing of analytical queries (i.e. OLAP queries). A conventional data warehouse stores only alphanumeric data. On the other hand, an image data warehouse stores not only alphanumeric data but also intrinsic features of images, thus allowing data warehousing environments to perform analytical similarity queries over images. This requires the development of strategies to provide efficient processing of these complex and costly queries. Although there are a number of approaches in the literature aimed at the development of bitmap index for data warehouses and metric access methods for the efficient processing of similarity queries over images, to the best of our knowledge, there is not an approach that investigate these two issues in the same setting. In this research, we fill this gap in the literature by introducing the following main contributions: (i) the proposal of the ImageDW-index, an optimization mechanism aimed at the efficient processing of analytical queries extended with similarity predicates over images; and (ii) definition of different processing strategies for image data warehouses using the ImageDW-index. In order to validate these main proposals, we also introduce two secondary contributions, as follows: (iii) the ImageDW-Gen, a data generator to populate image data warehouses; and (iv) the proposal of four query classes, each one enforcing different query processing costs associated to the similarity predicates in image data warehousing environments. Using the ImageDW-Gen, performance tests were carried out in order to investigate the advantages introduced by the proposed strategies, according to the query classes. Compared to the most related work available in the literature, the ImageDW-index provided a performance gain that varied from 55.57% to 82.16%, considering one of the proposed strategies.

Page generated in 0.0872 seconds