Orientador: João Meidanis / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-23T12:35:59Z (GMT). No. of bitstreams: 1 Telles_GuilhermePimentel_M.pdf: 2865242 bytes, checksum: 54f791de77bb496c8eebad6c170fdc93 (MD5) Previous issue date: 1997 / Resumo: Neste trabalho formalizamos as Árvores PQR de Meidanis e Munuera e seu relacionamento com a propriedade dos uns consecutivos e com as Árvores PQ de Booth e Lueker. Mostramos que uma árvore PQR construída para uma coleção C de subconjuntos de um universo U é capaz de armazenar todas as permutações de U que verificam a propriedade dos uns consecutivos. Apresentamos dois algoritmos para construir as árvores PQR, um recursivo e outro não recursivo, e alguns problemas relativos à propriedade e às coleções de conjuntos que podem ser resolvidos através destas árvores. Analisamos, ainda, um conjunto de aplicações das Árvores PQ e consideramos a possibilidade de empregar as árvores PQR / Abstract: In the present work we formalize Meidanis and Munuera's PQR trees and their relationship with the Consecutive Ones Property and with Booth and Lueker's PQ trees. We show that a PQR tree built for a colIection C of subsets of a ground set U is able to store alI permutations of U that verify the consecutive ones property. We introduce two algorithms that build the PQR trees, a recursive and a non recursive one, and some problems related to the consecutive ones property and to colIections of sets that can be solved using them. We analyze some applications of the PQ trees and inspect the useness of the PQR trees / Mestrado / Mestre em Ciência da Computação

Orientador : Prof. Dr. Eduardo Cunha de Almeida / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 24/02/2017 / Inclui referências : f. 41-43 / Área de concentração: Ciência da computação / Resumo: Em Database Cracking, uma coluna de banco de dados se organiza fisicamente, de maneira autônoma, em partições, um índice é então criado para otimizar o acesso a essas partições. A árvore AVL é a estrutura de dados utilizada para implementar esse índice. Contudo, em termos de cache, ela é particularmente ineficiente para consultas de intervalos, já que seus nós acessados apenas algumas vezes e os nós frequentemente acessados estão espalhados por toda a árvore. Esse trabalho apresenta a Self-Pruning Splay Tree (SPST) que é uma estrutura de dados capaz de reorganizar os dados mais e menos acessados, melhorando o tempo de acesso para as partições mais acessadas. Para cada consulta de intervalo, a SPST rotaciona para a raiz os nós que apontam para os valores do predicado da consulta e o valor médio do intervalo. Eventualmente, os nós mais acessados da árvore irão permanecer próximos a raíz, melhorando a utilização da CPU e a atividade de cache. Os nós menos acessados permanecerão próximos às folhas e serão removidos para limparmos dados que não são utilizados, diminuindo o tamanho do índice e obtendo custos de leitura e atualização menores. Palavras-chave: Database Cracking, Índice para Cracking , Árvore Splay. / Abstract: In database cracking, a database is physically self-organized into cracked partitions with cracker indices boosting the access to these partitions. The AVL Tree is the current data structure of choice to implement cracker indices. However, it is particularly cache-inefficient for range queries, because the nodes accessed only for a few times (i.e, "Cold Data") and the most accessed ones (i.e, "Hot Data") are spread all over the index. This work presents the Self-Pruning Splay Tree (SPST) data structure to index database cracking and reorganize "Hot Data" and "Cold Data" to boost the access to the cracked partitions. To every range query, the SPST rotates to the root the nodes pointing to the edges and to the middle value of the predicate interval. Eventually, the most accessed tree nodes remain close to the root improving CPU and cache activity. On the other hand, the least accessed tree nodes remain close to the leaves and are pruned to clean up unused data in order to diminish the storage footprint with significant improvements: smaller lookup/update costs. Keywords: Database Cracking, Cracker Index, Splay Tree.

Orientador: Claudio Leonardo Lucchesi, Leo Pini Magalhães / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-21T16:43:54Z (GMT). No. of bitstreams: 1 Moroni_Artemis_M.pdf: 1496576 bytes, checksum: e28bc3179b1001fa26b884bb49bcc6df (MD5) Previous issue date: 1996 / Resumo: A visualização e a simulação de processos fisicos e o modelamento de fenômenos naturais vêm ocupando um espaço cada vez maior na ciência de computação. Abordagens recentes, que provêem soluções para essas aplicações são geralmente agrupadas sob o termo modelamento baseado em sistemas fisicos. Neste trabalho, é descrita uma aplicação de sistemas de partículas para o modelamento de superficies isopotenciais 3D geradas por cargas elétricas, através do Método Multipólos Rápido (MMR). O método sugere uma abordagem para acelerar a velocidade do cálculo das interaçôes entre as partículas para uma classe específica de problemas, onde as interações são definidas usando funções Para representar o espaço que contém as partículas elétricas é usada a estrutura de dados octree. As relações de vizinhança na octree ocupam um importante papel no MMR. O sistema resultante IsSuP - Isopotential Surfaces using Particles, um sistema flexível para a avaliação e o modelamento das superfícies isopotenciais 3D, é descrito. Para visualizar as superfícies é utilizada a biblioteca V3DTOOLS para visualização e processamento de volumes do sistema khoros. Resultados numéricos e imagens são apresentadas / Abstract: The visualization and simulation of physical processes and the modelling of natural phenomena is playing an increasing role in computer science. Recent approaches, which provide solutions for these applications, are generally referenced under the term physically based modelling. Ao application of particle systems for modelling 3D isopotential surfaces generated by electrical charges using the Fast Multipole Method (FMM) is described. This method suggests an approach to accelerate the evaluation speed of the interactions among the particles for a specific cIass of problems, where the interactions are defined using potential functions. The octree is used to represent the space which contains the electrical charges. The neighborhood relation in the octree plays an important role in the FMM algoritlun. The resulting system, Is,SuP - Isopotential Surfaces using Particles, a t1exible system for the evaluation and modeUing 3D isopotential surfaces generated by means of electrical charges, is presented. The V3DTOOLS Toolbox for Volume Visualization and Processing for the Khoros System is used to visualize the surfaces. Numerical results and images are shown / Mestrado / Mestre em Ciência da Computação

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-09T17:25:07Z (GMT). No. of bitstreams: 1 Neves_PatriciaTakaki_M.pdf: 4451114 bytes, checksum: c4fcf2f5d76f36075020307255c1470c (MD5) Previous issue date: 2007 / Resumo: O problema de encontrar caminhos mínimos em um grafo com pesos nas arestas é considerado fundamental em otimização combinatória. Diversos problemas do mundo real podem ser modelados dessa forma: percurso mais curto/rápido entre duas cidades, transmissão de dados em uma rede de computadores, reconhecimento de voz, segmentação de imagens entre outros. O algoritmo proposto por Dijkstra em 1959 resolve o problema de caminhos mínimos em grafos sem arestas de peso negativo, o que não chega a ser restritivo na maior parte das aplicações. Desde então, o algoritmo tem sido refinado com o uso de estruturas de dados cada vez mais sofisticadas, reduzindo seu tempo de execução de pior caso (ao menos, do ponto de vista teórico). Recentemente, problemas de caminhos mínimos têm aparecido no contexto de Sistemas de Informação Geográfica (SIG). Neste modelo, o usuário faz consultas ao sistema para encontrar o trajeto mais curto (ou rápido) entre dois pontos especificados (problema ponto-a-ponto ou problema P2P). Além disso, pode haver várias consultas. Instâncias neste tipo de modelo são relativamente grandes: o mapa rodoviário dos Estados Unidos tem mais de 20 milhões de vértices (cada vértice representa intersecções de vias). Mesmo as implementações mais sofisticadas do algoritmo de Dijkstra não apresentam um desempenho prático capaz de atender às demandas que esse tipo de modelo requer. A pesquisa recente tem tentado reduzir este gap entre a teoria e a prática. Várias técnicas de aceleração de algoritmos têm sido propostas e implementadas: busca bidirecional, algoritmo A*, alcance (reach), landmarks e muitos outros. Algumas dessas técnicas têm restrições de domínio e outras podem ser usadas em qualquer contexto. Neste trabalho, estudamos algumas variações da versão original do algoritmo de Dijkstra, caracterizadas pelas diferentes estruturas de dados. Implementamos quatro dessas variações e realizamos testes experimentais utilizando os mapas do mundo real. Nosso objetivo foi analisar o desempenho prático dessas. Dedicamos também uma atenção especial ao problema P2P, apresentando algumas das principais técnicas de aceleração / Abstract: The problem of finding shortest paths in a weighted graph is a fundamental one in combinatorial optimization. Several real world problems can be modeled in this way: shortest or fastest tour between two cities, data transmission on a computer network, voice recognition, image segmentation among others. The algorithm proposed by Dijkstra in 1959 solves this problem when the graph has no edge with negative weight, which is not a serious restriction in most applications. Since then, the algorithm has been improved with the use of sophisticated data structures, reducing the worst case running time (at least, from a theoretical viewpoint). Recently shortest path problems has appeared in the context of Geographic Information System (GIS). In this model, the user asks the system to find out the shortest path between two given points (point-to-point problem or P2P problem). Moreover, there can be several queries. Instances in this model are relatively large: the road network map of the United States has more than 20 million vertices (each vertex represents an intersection of two roads). Even the fastest implementations of Dijkstra's algorithm do not have a performance in practice which is satisfactory to meet the requirements of this model. Recent research has tried to reduce this gap between theory and practice. Several speed-up techniques for these algorithms have been proposed and implemented: bidirectional search, algorithm A*, reach, landmarks and many others. Some of them are domain-restricted and others are applicable in any context. In this work, we studied some variants of Dijkstra's algorithm characterized by its different data structures. We have implemented four of those variants and performed experimental tests using real-world maps. Our goal was to analyze their practical performance. We also paid special attention to the P2P problem, and presented some of the main speed-up techniques / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador : Wu Shin-Ting / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-02T20:07:52Z (GMT). No. of bitstreams: 1 Batagelo_HarlenCosta_M.pdf: 608382 bytes, checksum: e61ed7585f24dc2d6939e44ac8117202 (MD5) Previous issue date: 2002 / Mestrado

TEIXEIRA, D. N. Uma técnica de decomposição a priori para geração paralela de malhas bidimensionais. 2014. 95 f. Dissertação (Mestrado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2014. / Submitted by Daniel Eduardo Alencar da Silva (dealencar.silva@gmail.com) on 2015-01-23T18:25:13Z No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Approved for entry into archive by Rocilda Sales(rocilda@ufc.br) on 2015-09-23T16:26:52Z (GMT) No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) / Made available in DSpace on 2015-09-23T16:26:52Z (GMT). No. of bitstreams: 1 2014_dis_dnteixeira.pdf: 17919971 bytes, checksum: 092ad12b33cf64a31552e6a839a5a5bc (MD5) Previous issue date: 2014 / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits. / Este trabalho descreve uma técnica de decomposição de domínios bidimensionais para geração em paralelo de malhas. Esta técnica funciona tanto para memória distribuída quanto compartilhada, além de permitir que se utilize qualquer estrutura de dados que gere regiões quadrangulares paralelas aos eixos para decompor o domínio dado como entrada. Pode se utilizar por exemplo, uma árvore quaternária (quadtree) ou uma partição binária do espaço (bsp). Além disso, qualquer processo de geração de malha que respeite os pré-requisitos estabelecidos pode ser empregado nos subdomínios criados, como as técnicas de Delaunay ou Avanço de Fronteira, dentre outras. A técnica proposta é dita a priori porque a malha de interface entre os subdomínios é gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomínio é feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nível de refinamento orienta a criação das arestas que são definidas a partir da discretização das fronteiras das células internas. Essa maneira de estimar carga produz resultados que representam, com boa precisão, o número de elementos a serem gerados em cada subdomínio. Isso contribui para um bom particionamento do domínio, fazendo com que a geração de malha em paralelo seja significativamente mais rápida do que a geração serial. Além disso, a qualidade da malha gerada em paralelo é qualitativamente equivalente àquela gerada serialmente, dentro de limites aceitáveis.

Orientador: Mario Antonio do Nascimento / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-12T01:56:25Z (GMT). No. of bitstreams: 1 Colossi_NathanGevaerd_M.pdf: 2522265 bytes, checksum: 99dd6e401847b5a2592ea4b0d70619cf (MD5) Previous issue date: 2000 / Resumo: Em bancos de dados multimídia é comum a representação de objetos utilizando vetores de características, que são, por sua vez, mapeados em um espaço multidimensional. Nesta dissertação, os objetos utilizados são imagens, e os vetores de características são obtidos através dos seus histogramas de cores. O mapeamento dos vetores de características em um espaço multidimensional permite a utilização de estruturas de indexação espaciais, proporcionando a realização de consultas de similaridade de forma eficiente. Este trabalho são avaliadas algumas estruturas de indexação para dados multidimen­sionais, que vão de estruturas espaciais tradicionais, como a R-tree e a R* -tree, a estrutu­ras espaciais adaptadas para espaços hiperdimensionais, como a SS-tree e a SR-tree. De fato, este trabalho se concentra no aspecto da alta dimensionalidade dos vetores de ca­racterísticas. Paralelo a estas estruturas, a M-tree, que realiza a indexação dos vetores de características de forma adimensional, i.e., no espaço métrico, é também avaliada. Para completar a avaliação, é feita a comparação dessa estruturas em relação a busca linear, a fim de confirmar a eficiência das estruturas avaliadas. Para assegurar um ambiente de avaliação homogêneo, foi utilizado o ambiente de programação GiST para a implementação das estruturas, e, nas avaliações das estruturas, foi utilizado um conjunto de dados reais de 40.000 elementos. Um conjunto bastante amplo de parâmetros de construção e consulta dos índices permitiu a avaliação das estruturas. Nos resultados obtidos, a SR-tree se mostrou a melhor estrutura com os conjuntos de dados reais. A M-tree mostrou poder alcançar bons resultados, dependendo da técnica de split utilizada. Nesta dissertação são propostas novas técnicas de split sendo uma delas mais robusta em relação ao aumento do número de dimensões. Além desses resultados, é mostrado que o uso de número de páginas acessadas como único indicador de desempenho pode levar a conclusões incorretas / Abstract: In multimedia databases its common to represent objects using feature vectors, which are mapped onto a multidimensional space. In this thesis, the objects are image, and their feature vectors are obtained from their color histogram. The feature vectors mapping into a multidimensional space allows the utilization of spatial access structures, in order to efficiently perform similarity queries In this research multidimensional indexing structures are evaluated, from traditional spatial structures, R-tree and R*-tree, up to structures specially designed for high-dimen­sional spaces, like the SS-tree and SR-tree. Indeed, this work focus on the issue of the high-dimensionality of the feature space. Along with these structures, the M-tree, that indexes feature vectors in a non-dimensional manner, i.e., using the metric space, is also evaluated. To complete the evaluation, all the above structures are evaluated against the linear scan, in order to confirm the efficiency of the structures. To assure a homogeneous evaluation environment, the GiST framework was used to implement the structures, and the evaluation was performed using a data set of 40,000 feature vectors. A wide set of parameters was used evaluate construction and query processmg. The results obtained, indicate the SR-tree as the best structure for the real dataset. The M-tree was shown able to obtain good results, depending primarily upon the split technique used. This thesis also proposes new split techniques, and one of them was more resilient with respect to the increase in the number of dimensions. In addition, it is also shown that using the number of accessed pages as the only performance indicator may lead to wrong conclusions / Mestrado / Mestre em Ciência da Computação

Orientador : Geovane Cayres Magalhães / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-02T15:03:52Z (GMT). No. of bitstreams: 1 Gatti_SandroDanilo_M.pdf: 6967879 bytes, checksum: 106ac6f889f78c15c4e4025f2e113486 (MD5) Previous issue date: 2000 / Resumo: Métodos de junção espacial baseadas em percurso sincronizado em árvores foram anali­zadas. Os fatores considerados incluíram tamanho do bufferpàol, tamanho da página, critérios de ordenação de índices intermediários de junção, políticas de substituição de páginas do bufferpool, dentre outros fatores. Esta análise foi efetuada tomando-se por base um conjunto de dados reais extraídos de uma aplicação de SIG em telecomunicações, indexados em R*-trees. Os resultados deste trabalho avaliam a forma como estes fatores afetam o desempenho das junções espaciais e podem ser utilizados para ajustar estas técnicas / Abstract: Synchronized tree traversal join methods for spatial access methods were analysed. The factors considered included bufferpool size, page size, intermediate join indexes ordering criteria, bufferpool page replacement policies, among others. This analysis was based on real data taken from a crs application for telecommunications, indexed on a R*-tree. Results of this work assess the way those factors affect spatial join performance and can be used for tuning such methods / Mestrado / Mestre em Ciência da Computação

Orientador : João Meidanis / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-03T14:23:48Z (GMT). No. of bitstreams: 1 Telles_GuilhermePimentel_D.pdf: 2708887 bytes, checksum: b728e7b5eaa59e830b3ce288b3c90dd6 (MD5) Previous issue date: 2003 / Resumo: Nesta tese apresentamos um algoritmo quase-linear para construir árvores PQR e o esquema para clustering de seqüências expressas que foi usado no projeto SUCEST (Sugarcane EST project).Uma árvore PQR é uma estrutura de dados capaz de resolver o problema dos uns consecutivos e outros problemas, como mapeamento físico de DNA, reconhecimento de grafos intervalo, otimização de circuitos lógicos e recuperação de dados. As árvores PQR são uma generalização das árvores PQ de Booth e Lueker e estão fundamentadas em propriedades algébricas sólidas. O algoritmo que apresentamos nesta tese se baseia nessas propriedades e é formado por um conjunto pequeno de padrões que modificam a árvore. Nosso algoritmo é mais eficiente que o algoritmo quadrático proposto originalmente por Meidanis e Munuera ao definir as árvores PQR e, embora não seja linear como o algoritmo para construir árvores PQ, acreditamos que ele contribui em direção a uma solução definitiva para o problema dos uns consecutivos. Clustering é o problema de categorização de um conjunto de objetos quando nem o número nem a composição das categorias é conhecido antecipadamente. Seqüências expressas ou ESTs (expressed sequence tags) são amostras de genes ativos extraídas das células de um organismo. Em um projeto genoma EST são obtidas milhares dessas seqüências que serão usadas como fonte para investigações por cientistas interessados nos processos celulares do organismo. O clustering de seqüências expressas é necessário para avaliar e reduzir a redundância do conjunto de ESTs. Nesta tese apresentamos o esquema de clustering usado no projeto da cana-de-açúcar, que produziu aproximadamente 300.000 ESTs. O esquema que apresentamos substituiu um esquema pré-existente e se caracteriza por uma limpeza prévia intensiva dos ESTs e pelo uso de um montador de genomas para agrupá-los. Acreditamos que este esquema possa ser utilizado em outros projetos do gênero / Abstract: In this thesis we introduce an almost-linear algorithm for building PQR trees and the method for expressed sequence tags clustering used in the SUCEST project (Sugarcane EST Project). A PQR tree is a structure that can be used to solve many problems, as the consecutive ones problem, DNA physical mapping, interval graphs recognition and data retrieval. PQR trees are a generalization of Booth and Lueker's PQ trees, and are founded on solid algebraic properties. The algorithm we present in this work is based on such properties and is composed by a small set of well-organized patterns. Our algorithm is more efficient than the quadratic one proposed by Meidanis and Munuera, who defined the PQR trees, and, although not linear as the algorithm for PQ trees construction, we believe that it contributes for a definite solution for the consecutive ones problem. Clustering is the problem of categorizing a set of objects when neither the number of categories nor the composition of the categories is known. Expressed sequence tags (ESTs) are samples from active genes extracted from cells of an organism. In an EST project, thousands of ESTs are produced and used as a source for research. Clustering ESTs is necessary to reduce the redundancy in the set of sequences. In this thesis we introduce the method used in the Sugarcane EST Project, that produced almost 300,000 sequences. The method we introduce in this work replaced another one that had problems. Our scheme include an intensive trimming of the ESTs and the use of a genome assembler for the whole set of sequences. We believe that our scheme may be used in other EST projects / Doutorado / Doutor em Ciência da Computação

Orientadores: Paulo Licio de Geus, Fernando Antonio Vanini / Dissertação (mestrado profissional) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-03T18:44:46Z (GMT). No. of bitstreams: 1 Kerr_EduardoSantos_M.pdf: 2585011 bytes, checksum: 2fd67d43272fa13f5e50ede1ec493050 (MD5) Previous issue date: 2003 / Resumo: O termo "texto complexo" é utilizado para classificar um texto que possua relações transtextuais dentro do texto de origem e com textos complementares, que sirvam para agregar os diferentes tipos de análise e crítica, ou simplesmente para permitir uma melhor compreensão. Nesse trabalho, é proposto um processo para representação de informação em textos complexos utilizando a meta linguagem XML e algumas tecnologias relacionadas. Como parte do processo de representação, foi definido um modelo denominado Ketib, que é aplicado, a título de estudo de caso, à obra Biblia Hebraica Stuttgartensia. Este texto foi escolhido por apresentar um alto grau de complexidade, tomando possível demonstrar o potencial do modelo no tratamento da representação e da codificação de informações com natureza multidimensional que contenham diferentes sistemas de referência. Os resultados não estão restritos ao estudo de caso e demonstram a viabilidade desse processo em textos de outros domínios / Abstract: The phrase "complex text" applies to texts that possess transtextual relations within the source text and that relate to other supplementary texts, either for aggregating the different kinds of critiques and analyses, or just for better understanding. This work proposes a process for the representation of information in complex texts using the XML language and some related technologies. As part of the representation process, the model defined was one called Ketib, and it is applied, as a case study, to the Biblia Hebraica Sttutgartensia. The reason for selecting this text was its high degree of complexity, making it possible to validate the potential of the model when treating the representation and the codification of information of a multidimensional nature, containing different reference systems. The results are not restricted to the case study and demonstrate the possibilities of this process in texts in other domains / Mestrado / Ciência da Computação / Mestre em Ciência da Computação