Um data warehouse geográco (DWG) é um banco de dados multidimensional, orientado a assunto, integrado, histórico, não-volátil e geralmente organizado em níveis de agregação. Além disso, também armazena dados espaciais em uma ou mais dimensões ou em pelo menos uma medida numérica. Visando oferecer suporte à tomada de decisão, é possível realizar em DWGs consultas SOLAP (spatial online analytical processing ), isto é, consultas analíticas multidimensionais (e.g., drill-down, roll-up, drill-across ) com predicados espaciais (e.g., intersecta, contém, está contido) denidos para range queries e junções espaciais. Um desafio no processamento dessas consultas é recuperar, de forma eficiente, dados espaciais e convencionais em DWGs muito volumosos. Na literatura, existem poucos índices voltados à indexação de DWGs, e ainda assim nenhum desses índices dedica-se a indexar consultas SOLAP drill-across e com junção espacial. Esta dissertação visa suprir essa limitação, por meio da proposta de estratégias para o processamento dessas consultas complexas. Para o processamento de consultas SOLAP drill-across foram propostas duas estratégias, Divide e Única, além da especicação de um conjunto de diretrizes que deve ser seguido para o projeto de um esquema de DWG que possibilite a execução dessas consultas e da especicação de classes de consultas. Para o processamento de consultas SOLAP com junção espacial foi proposta a estratégia SJB, além da identicação de quais características o esquema de DWG deve possuir para possibilitar a execução dessas consultas e da especicação do formato dessas consultas. A validação das estratégias propostas foi realizada por meio de testes de desempenho considerando diferentes congurações, sendo que os resultados obtidos foram contrastados com a execução de consultas do tipo junção estrela e o uso de visões materializadas. Os resultados mostraram que as estratégias propostas são muito eficientes. No processamento de consultas SOLAP drill-across, as estratégias Divide e Única mostraram uma redução no tempo de 82,7% a 98,6% com relação à junção estrela e ao uso de visões materializadas. No processamento de consultas SOLAP com junção espacial, a estratégia SJB garantiu uma melhora de desempenho na grande maioria das consultas executadas. Para essas consultas, o ganho de desempenho variou de 0,3% até 99,2% / A geographic data warehouse (GDW) is a special kind of multidimensional database. It is subject-oriented, integrated, historical, non-volatile and usually organized in levels of aggregation. Furthermore, a GDW also stores spatial data in one or more dimensions or at least in one numerical measure. Aiming at decision support, GDWs allow SOLAP (spatial online analytical processing) queries, i.e., multidimensional analytical queries (e.g., drill-down, roll-up, drill-across) extended with spatial predicates (e.g., intersects, contains, is contained) dened for range and spatial join queries. A challenging issue related to the processing of these complex queries is how to recover spatial and conventional data stored in huge GDWs eciently. In the literature, there are few access methods dedicated to index GDWs, and none of these methods focus on drill-across and spatial join SOLAP queries. In this master\'s thesis, we propose novel strategies for processing these complex queries. We introduce two strategies for processing SOLAP drill-across queries (namely, Divide and Unique), dene a set of guidelines for the design of a GDW schema that enables the execution of these queries, and determine a set of classes of these queries to be issued over a GDW schema that follows the proposed guidelines. As for the processing of spatial join SOLAP queries, we propose the SJB strategy, and also identify the characteristics of a DWG schema that enables the execution of these queries as well as dene the format of these queries. We validated the proposed strategies through performance tests that compared them with the star join computation and the use of materialized views. The obtained results showed that our strategies are very ecient. Regarding the SOLAP drill-across queries, the Divide and Unique strategies showed a time reduction that ranged from 82,7% to 98,6% with respect to star join computation and the use of materialized views. Regarding the SOLAP spatial join queries, the SJB strategy guaranteed best results for most of the analyzed queries. For these queries, the performance gain of the SJB strategy ranged from 0,3% to 99,2% over the star join computation and the use of materialized view

Os Sistemas de Gerenciamento de Bases de Dados devem atualmente ser capazes de gerenciar dados complexos, como dados multimídia, sequências genéticas, séries temporais, além dos dados tradicionais. Em consultas em grandes coleções de dados complexos, a similaridade entre os dados é o fator mais importante, e pode ser adequadamente expressada quando esses dados são representados em espaços métricos. Independentemente do domínio de um tipo de dados, existem aplicações que devem acompanhar a evolução temporal dos elementos de dados. Porém, os Métodos de Acesso Métrico existentes consideram que os dados são imutáveis com o decorrer do tempo. Visando o tratamento do tempo e dinamicidade em dados representados em espaços métricos, o trabalho apresentado nesta tese foi desenvolvido em duas frentes principais de atividades. A primeira frente tratou da inclusão das operações de remoção e atualização em métodos de acesso métrico, e visa atender às necessidades de domínios de aplicação em que dados em espaços métricos sofram atualização frequente, independentemente de necessitarem de tratamento temporal. Desta frente de atividades também resultou um novo método de otimização de àrvores métricas, baseado no algoritmo de remoção desenvolvido. A segunda frente de atividades aborda a inclusão do conceito de evolução temporal em dados representados em espaços métricos. Para isso foi proposto o Espaço Métrico-temporal, um modelo de representação de dados que permite a comparação de elementos métricos associado a informações temporais. O modelo conta com um método para identificar as contribuições relativas das componentes métrica e temporal no cálculo da similaridade. Também foram apresentadas estratégias para análise de trajetórias de dados métricos com o decorrer do tempo, através da imersão de espaços métrico-temporais em espaços dimensionais. Por fim, foi apresentado um novo método de balanceamento de múltiplos descritores para representação de imagens, fruto de modificações no método proposto para identificar as contribuições das componentes que podem formar um espaço métrico-temporal / Nowadays, the Database Management Systems (DBMS) must be able to manage complex data, such as multimedia data, genetic sequences, temporal series, besides the traditional data. For queries on large collections of complex data, the similarity among elements is the most relevant concept, and it can be adequately expressed when data are represented in metric spaces. Regardless of the data domain, there are applications that must tracking the evolution of data over time However, the existing Metric Access Methods assume that the data elements are immutable. Aiming at both treating time and allowing changes in metric data, the work presented in this thesis consisted of two main parts. The first part addresses the inclusion of the operations for element remotion and updating in metric access methods. These operations are meant to application domains that work with metric data that changes over time, regardless of the needed to manage temporal information. A new method for metric trees optimization was also developed in this part of the work. It was based on the proposed remotion algorithm. The second part of the thesis addresses including the temporal evolution concept in data represented in metric spaces. The Metric-Temporal Space was proposed, a representation model to allow comparing elements consisting of metric data with temporal information associated. The model includes a method to identify the relative contributions of the temporal and the metric components in the final similarity calculation. Strategies for trajectory analysis of metric data over time was also presented, through the immersion of metric-temporal spaced in dimensional spaces. Finally, a new method for weighting multiple image descriptors was presented. It was derived from changes in the proposed method to identify the contributions of the components of the metric-temporal space

Um Sistema de Informação Geográfica armazena e mantém dados geográficos, combinando-os, para obter novas representações do espaço geográfico. A junção espacial combina duas relações de geometrias geo-referenciadas de acordo com algum predicado espacial, como intersecção e distância entre objetos. Trata-se de uma operação essencial, pois é constantemente utilizada e possui um alto custo de realização devido a realização de grande número de operações de Entrada/Saída e a complexidade do algoritmo. Este trabalho estuda o desempenho de algoritmos de junção espacial. Inicialmente, apresenta a análise dos algoritmos já publicados na literatura, obtendo expressões de custo para número de operações de disco e processamento. Após, descreve-se a implementação de alguns algoritmos em um ambiente de testes. Este ambiente permite ao usuário variar diversos parâmetros de entrada: cardinalidade dos conjuntos, memória disponível e predicado de junção, envolvendo dados reais e sintéticos. O ambiente de testes inclui os algoritmos de Laços Aninhados, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) para árvores R* e Iterative Spatial Stripped Join (ISSJ). Os testes demonstraram que o STT é adequado para conjuntos pequenos de dados; o ISSJ se houver memória suficiente para ordenar os conjuntos internamente; e o PBSM se houver pouca memória disponível para buffer de dados. A partir da análise um novo algoritmo, chamado Histogram-based Hash Stripped Join (HHSJ) é apresentado. O HSSJ utiliza histogramas da distribuição dos objetos no espaço para definir o particionamento, armazena os objetos em arquivos organizados em hash e subdivide o espaço em faixas (strips) para reduzir o processamento. Os testes indicam que o HHSJ é mais rápido na maioria dos cenários, sendo ainda mais vantajoso quanto maior o número de objetos envolvidos na junção. Um módulo de otimização de consultas baseado em custos, capaz de escolher o melhor algoritmo para realizar a etapa de filtragem é descrito. O módulo utiliza informações estatísticas mantidas no dicionário de dados para estimar o tempo de resposta de cada algoritmo, e indicar o mais rápido para realizar uma operação específica. Este otimizador de consultas acertou a indicação em 88,9% dos casos, errando apenas na junção de conjuntos pequenos, quando o impacto é menor. / A Geographic Information System (GIS) stores geographic data, combining them to obtain new representations of the geographic space. The spatial join operation combines two sets of spatial features, A and B, based on a spatial predicate. It is a fundamental as well as one of the most expensive operations in GIS. Combining pairs of spatial, georreferenced data objects of two different, and probably large data sets implies the execution of a significant number of Input/Output (I/O) operations as well as a large number of CPU operations. This work presents a study about the performance of spatial join algorithms. Firstly, an analysis of the algorithms is realized. As a result, mathematical expressions are identified to predict the number of I/O operations and the algorithm complexity. After this, some of the algorithms (e.g.; Nested Loops, Partition Based Spatial Join Method (PBSM), Synchronized Tree Transversal (STT) to R-Trees and Iterative Spatial Stripped Join (ISSJ)) are implemented, allowing the execution of a series of tests in different spatial join scenarios. The tests were performed using both synthetic and real data sets. Based on the results, a new algorithm, called Histogram-based Hash Stripped Join (HHSJ), is proposed. The partitioning of the space is carried out according to the spatial distribution of the objects, maintained in histograms. In addition, a hash file is created for each input data set and used to enhance both the storage of and the access to the minimum bounding rectangles (MBR) of the respective set elements. Furthermore, the space is divided in strips, to reduce the processing time. The results showed that the new algorithm is faster in almost all scenarios, specially when bigger data sets are processed. Finally, a query optimizer based on costs, capable to choose the best algorithm to perform the filter step of a spatial join operation, is presented. The query optimizer uses statistical information stored in the data dictionary to estimate the response time for each algorithm and chooses the faster to realize the operation. This query optimizer choose the right one on 88.9% of cases, mistaken just in spatial join envolving small data sets, when the impact is small.

Submitted by Daniella Sodre (daniella.sodre@ufpe.br) on 2015-03-10T13:03:19Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação Bruno Souza.pdf: 3055649 bytes, checksum: 5cedaf83e4e87135a1f22f1bb7c1dd09 (MD5) / Made available in DSpace on 2015-03-10T13:03:19Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação Bruno Souza.pdf: 3055649 bytes, checksum: 5cedaf83e4e87135a1f22f1bb7c1dd09 (MD5) Previous issue date: 2013-09-09 / FACEPE / Ambientes dinâmicos e distribuídos são sistemas descentralizados que fornecem aos usuários recursos de consultas sobre um conjunto de fontes de dados heterogêneas, distribuídas e autônomas (peers). Sistemas de Integração de Dados, Peer Data Management System (PDMS) e Dataspaces são exemplos de tais sistemas. Eles são constituídos por peers que pertencem a um domínio específico e estão ligados entre si por meio de correspondências semânticas. No entanto, um desafio inerente em ambientes dinâmicos e distribuídos é o processo de reformulação de consulta entre um par de peers. Quando um usuário coloca uma consulta em um peer, a fim de adquirir mais informações, a consulta deve ser reformulada de acordo com o esquema dos peers vizinhos. Neste processo podem surgir alguns problemas como a perda semântica e a degradação da consulta. A perda semântica e degradação da consulta são problemas relacionados à perda de conceitos semânticos durante a reformulação. Por outro lado, em um ambiente semanticamente rico, ao invés de uma perda semântica, a consulta pode ter um enriquecimento semântico por meio da agregação de conceitos semanticamente relacionados durante a reformulação. Neste sentido, a consulta do usuário pode ser enriquecida e resultados semânticos mais ricos podem ser recuperados. Critérios de qualidade da informação têm sido usados em alguns trabalhos para avaliar o nível de qualidade dos elementos de um ambiente dinâmico e distribuído como, por exemplo, peers, dados e a resposta da consulta. Estes critérios são medidas dinâmicas proporcionadas pelo sistema e servem como uma pontuação que pode ser constantemente avaliada para obter o nível real de qualidade. Neste trabalho, apresentamos quatro critérios de qualidade da informação que medem a perda e o ganho de conceitos semânticos durante a reformulação da consulta entre os pares de peers. Nós apresentamos um exemplo da nossa abordagem e os algoritmos de avaliação de critérios. Também damos as nossas definições para os problemas de perda semântica e degradação da consulta. Por fim, apresentamos a experimentação que fizemos com o PDMS SPEED e os resultados obtidos. / Dynamic distributed environments are decentralized systems that provide users with querying capabilities over a set of heterogeneous, distributed and autonomous data sources (peers). Data Integration Systems, Peer Data Management Systems (PDMS) and Dataspaces are examples of such systems. They are composed by peers that belong to a specific domain and are linked to each other by correspondences (semantic connections). Nonetheless, a challenge inherent to dynamic distributed environments is the query reformulation process between a pair of peers. When a user poses a query at a peer, in order to acquire more information, the query should be reformulated in accordance with the neighbor peers schema. In this process some problems as semantic loss and query degradation can arise. The semantic loss and query degradation are problems related to the loss of semantic concepts during query reformulation. In the other hand, in such a semantic environment instead of a semantic loss the query can have a semantic enrichment by aggregating semantic related concepts during reformulation. In this sense, the user’s query can be enriched and semantically richer results can be delivered. Information Quality criteria has been used in some works to evaluate the level of quality of the distributed dynamic environment’s elements such as, peers, data and query answer. These criteria are dynamic measures provided by the system and serve as scores that can be constantly evaluated to get the actual level of quality. In this work we present four Information Quality criteria that measure the loss and enrichment of semantic concepts during query reformulation among peers. We present an example of our analysis and the algorithms that implement the evaluation of the presented criteria. We also give our definitions to the semantic loss and query degradation problems. Finally, we present the experimentation we have done with the SPEED PDMS and the obtained results.

Estruturas de indexação para domínios métricos são úteis para agilizar consultas por similaridade sobre dados complexos, tais como imagens, onde o custo computacional da comparação de dois itens de dados geralmente é alto. O estado da arte para executar consultas por similaridade está centrado na utilização dos chamados \"Métodos de Acesso Métrico\" (MAM). Tais métodos consideram os dados como elementos de um espaço métrico, onde apenas valem as propriedades fundamentais para que um espaço seja considerado métrico, onde a única informação que os MAMs utilizam é a medida de similaridade entre pares de elementos do domínio. No campo teórico, espaços métricos são extensamente estudados e servem de base para diversas áreas da Matemática. No entanto, a maioria dos trabalhos que têm sido desenvolvidos em Computação se restringem a utilizar as definições básicas desses espaços, e não foram encontrados estudos que explorem em mais profundidade os muitos conceitos teóricos existentes. Assim, este trabalho aplica conceitos teóricos importantes da Teoria de Espaços Métricos para desenvolver técnicas que auxiliem o tratamento e a manipulação dos diversos dados complexos, visando principalmente o desenvolvimento de métodos de indexação mais eficientes. É desenvolvida uma técnica para realizar um mapeamento de espaços métricos que leva à atenuação do efeito da maldição da dimensionalidade, a partir de uma aplicação lipschitziana real baseada em uma função de deformação do espaço das distâncias entre os elementos do conjunto. Foi mostrado que uma função do tipo exponecial deforma as distâncias de modo a diminuir os efeitos da maldição da dimensionalidade, melhorando assim o desempenho nas consultas. Uma segunda contribuição é o desenvolvimento de uma técnica para a imersão de espaços métricos, realizada de maneira a preservar a ordem das distâncias, possibilitando a utilização de propriedades no espaço de imersão. A imersão de espaços métricos no \' R POT. n\' possibilita a utilização da lei dos cossenos e assim viabiliza o cálculo de distâncias entre elementos e um hiperplano métrico, permitindo aumentar a agilidade à consultas por similaridade. O uso do hiperplano métrico foi exemplificado construindo uma árvore binária métrica, e também foi aplicado em um método de acesso métrico, a família MMH de métodos de acesso métrico, melhorando o particionamento do espaço dos dados / The access methods designed for metric domains are useful to answer similarity queries on any type of data, being specially useful to index complex data, such as images, where the computacional cost of comparison are high. The main mecanism used up to now to perform similarity queries is centered on \"Metric Acess Methods\" (MAM). Such methods consider data as elements that belong to a metric space, where only hold the properties that define the metric space. Therefore, the only information that a MAM can use is the similarity measure between pairs of elements in the domain. Metric spaces are extremelly well studied and is the basis for many mathematics areas. However, most researches from computer science are restrained to use the basic properties of metric spaces, not exploring the various existing theorical concepts. This work apply theoretical concepts of metric spaces to develop techniques aiding the treatment and manipulation of diverse complex data, aiming at developing more efficient indexing methods. A technique of mapping spaces was developed in order to ease the dimensionality curse effects, basing on a real lipschitz application that uses a stretching function that changes the distance space of elements. It was shown that an exponential function changes the distances space reducing the dimensionality curse effects, improving query operations. A second contribution is the developing of a technique based on metric space immersion, preserving the distances order between pairs of elements, allowing the usage of immersion space properties. The immersion of metric spaces into \'R POT. n\' allow the usage of the cossine law leading to the determination of distances between elements and a hiperplane, forming metric hiperplanes. The use of the metric hiperplanes lead to an improvement of query operations performance. The metric hiperplane itself formed the binary metric tree, and when applied to a metric access method, lead the formation of a family of metric access methods that improves the metric space particioning achieving faster similarity queries

[pt] O processamento de consulta paralelo tradicional utilize- se de nós computacionais para reduzir o tempo de processamento de consultas. Com o surgimento das grades computacionais, milhares de nós podem ser utilizados, desafiando as atuais técnicas de processamento de consulta a oferecerem um suporte massivo ao paralelismo em um ambiente onde as condições variam todo a instante. Em adição, as aplicações científicas executadas neste ambiente oferecem novas características de processamento de dados que devem ser integradas em um sistema desenvolvido para este ambiente. Neste trabalho apresentamos o sistema de processamento de consulta paralelo do CoDIMS-G, e seu novo operador Orbit que foi desenvolvido para suportar a avaliação de consultas iterativas. Neste modelo de execução as tuplas são constantemente avaliadas por um fragmento paralelo do plano de execução. O trabalho inclui o desenvolvimento do sistema de processamento de consulta e um novo algoritmo de escalonamento que, considera as variações de rede e o throughput de cada nó, permitindo ao sistema se adaptar constantemente as variações no ambiente. / [en] Traditional parallel query processing uses multiple computing nodes to reduce query response time. Within a Grid computing context, the availability of thousands of nodes challenge current parallel query processing techniques to support massive parallelism in a constantly varying environment conditions. In addition, scientific applications running on Grids offer new data processing characteristics that shall be integrated in such a framework. In this work we present the CoDIMS-G parallel query processing system with a full-fledged new query execution operator named Orbit. Orbit is designed for evaluating massive iterative based data processing. Tuples in Orbit iterate over a parallelized fragment of the query execution plan. This work includes the development of the query processing system and a new scheduling algorithm that considers variation on network and the throughput of each node. Such algorithm permits the system to adapt constantly to the changes in the environment.

O aumento da geração e do intercâmbio de imagens médicas digitais tem incentivado profissionais da computação a criarem ferramentas para manipulação, armazenamento e busca por similaridade dessas imagens. As ferramentas de recuperação de imagens por conteúdo, foco desse trabalho, têm a função de auxiliar na tomada de decisão e na prática da medicina baseada em estudo de casos semelhantes. Porém, seus principais obstáculos são conseguir uma rápida recuperação de imagens armazenadas em grandes bases e reduzir o gap semântico, caracterizado pela divergência entre o resultado obtido pelo computador e aquele esperado pelo médico. No presente trabalho, uma análise das funções de distância e dos descritores computacionais de características está sendo realizada com o objetivo de encontrar uma aproximação eficiente entre os métodos de extração de características de baixo nível e os parâmetros de percepção do médico (de alto nível) envolvidos na análise de imagens. O trabalho de integração desses três elementos (Extratores de Características, Função de Distância e Parâmetro Perceptual) resultou na criação de operadores de similaridade, que podem ser utilizados para aproximar o sistema computacional ao usuário final, visto que serão recuperadas imagens de acordo com a percepção de similaridade do médico, usuário final do sistema / The continuous growth of the medical images generation and their use in the day-to-day procedures in hospitals and medical centers has motivated the computer science researchers to develop algorithms, methods and tools to store, search and retrieve images by their content. Therefore, the content-based image retrieval (CBIR) field is also growing at a very fast pace. Algorithms and tools for CBIR, which are at the core of this work, can help on the decision making process when the specialist is composing the images analysis. This is based on the fact that the specialist can retrieve similar cases to the one under evaluation. However, the main reservation about the use of CBIR is to achieve a fast and effective retrieval, in the sense that the specialist gets what is expected for. That is, the problem is to bridge the semantic gap given by the divergence among the result automatically delivered by the system and what the user is expecting. In this work it is proposed the perceptual parameter, which adds to the relationship between the feature extraction algorithms and distance functions aimed at finding the best combination to deliver to the user what he/she expected from the query. Therefore, this research integrated the three main elements of similarity queries: the image features, the distance function and the perceptual parameter, what resulted in searching operators. The experiments performed show that these operators can narrow the distance between the system and the specialist, contributing to bridge the semantic gap

Sistemas de recuperação de imagens por conteúdo (Content-based image retrieval { CBIR) e de classificação dependem fortemente de vetores de características que são extraídos das imagens considerando critérios visuais específicos. É comum que o tamanho dos vetores de características seja da ordem de centenas de elementos. Conforme se aumenta o tamanho (dimensionalidade) do vetor de características, também se aumentam os graus de irrelevâncias e redundâncias, levando ao problema da \"maldição da dimensionalidade\". Desse modo, a seleção das características relevantes é um passo primordial para o bom funcionamento de sistemas CBIR e de classificação. Nesta tese são apresentados novos métodos de seleção de características baseados em algoritmos genéticos (do inglês genetic algorithms - GA), visando o aprimoramento de consultas por similaridade e modelos de classificação. A família Fc (\"Fitness coach\") de funções de avaliação proposta vale-se de funções de avaliação de ranking, para desenvolver uma nova abordagem de seleção de características baseada em GA que visa aprimorar a acurácia de sistemas CBIR. A habilidade de busca de GA considerando os critérios de avaliação propostos (família Fc) trouxe uma melhora de precisão de consultas por similaridade de até 22% quando comparado com métodos wrapper tradicionais para seleção de características baseados em decision-trees (C4.5), naive bayes, support vector machine, 1-nearest neighbor e mineração de regras de associação. Outras contribuições desta tese são dois métodos de seleção de características baseados em filtragem, com aplicações em classificação de imagens, que utilizam o cálculo supervisionado da estatística de silhueta simplificada como função de avaliação: o silhouette-based greedy search (SiGS) e o silhouette-based genetic algorithm search (SiGAS). Os métodos propostos superaram os métodos concorrentes na literatura (CFS, FCBF, ReliefF, entre outros). É importante também ressaltar que o ganho em acurácia obtido pela família Fc, e pelos métodos SiGS e SiGAS propostos proporcionam também um decréscimo significativo no tamanho do vetor de características, de até 90% / Content-based image retrieval (CBIR) and classification systems rely on feature vectors extracted from images considering specific visual criteria. It is common that the size of a feature vector is of the order of hundreds of elements. When the size (dimensionality) of the feature vector is increased, a higher degree of redundancy and irrelevancy can be observed, leading to the \"curse of dimensionality\" problem. Thus, the selection of relevant features is a key aspect in a CBIR or classification system. This thesis presents new methods based on genetic algorithms (GA) to perform feature selection. The Fc (\"Fitness coach\") family of fitness functions proposed takes advantage of single valued ranking evaluation functions, in order to develop a new method of genetic feature selection tailored to improve the accuracy of CBIR systems. The ability of the genetic algorithms to boost feature selection by employing evaluation criteria (fitness functions) improves up to 22% the precision of the query answers in the analyzed databases when compared to traditional wrapper feature selection methods based on decision-tree (C4.5), naive bayes, support vector machine, 1-nearest neighbor and association rule mining. Other contributions of this thesis are two filter-based feature selection algorithms for classification purposes, which calculate the simplified silhouette statistic as evaluation function: the silhouette-based greedy search (SiGS) and the silhouette-based genetic algorithm search (SiGAS). The proposed algorithms overcome the state-of-the-art ones (CFS, FCBF and ReliefF, among others). It is important to stress that the gain in accuracy of the proposed methods family Fc, SiGS and SIGAS is allied to a significant decrease in the feature vector size, what can reach up to 90%

Neste trabalho estudamos problemas relacionados com a busca de pontos e segmentos em janelas retangulares com os lados paralelos aos eixos. É dado um conjunto de segmentos (ou pontos) no plano. Em uma primeira fase estes segmentos são organizados em estruturas de dados de tal forma a tornar buscas por aqueles que estão contidos em janelas retangulares mais eficiente. Na segunda fase são dadas as janelas de maneira online. Várias destas estruturas de dados são baseadas em árvores balanceadas, tais como, árvore limite, árvore de busca com prioridade, árvore de intervalos e árvore de segmentos. Na dissertação mostramos detalhadamente estas estruturas de dados e os algoritmos para resolver este problema para conjuntos de pontos (versão unidimensional do problema) e para segmentos no plano, tanto horizontais e verticais como com qualquer orientação (sem cruzamentos). Os algoritmos são analisados de forma rigorosa quanto ao seu uso de espaço e de tempo. Implementamos também os vários algoritmos estudados, construindo uma biblioteca destas estruturas de dados. Apresentamos, finalmente os resultados de experimentos computacionais com instâncias do problema. / In this work we study problems about point and segment query in rectangular windows whose edges are parallel to the axis. Given a set of segments (or points) in the plane. In a first phase these segments are organized in data structures such that queries for segments in windows are done more efficiently. In the second phase windows are given online. The data structures are balanced trees as range tree, priority search tree, interval tree and segment tree. In this master\'s thesis we show in details data structures and algorithms for solving windowing queries to sets of points (unidimensional version of the problem) and of segments in the plane, as horizontal and vertical as any orientation (without crossings). The algorithms are analysed rigorously regarding their space and time used. We implement the algorithms studied, building a library of these data structures. Finally, we present, the results of computational experiments with instances of the problem.

Background. A demanda por cuidados médicos especializados vem aumentando em todo o mundo. Analisamos uma iniciativa de telemedicina para reduzir o tempo entre encaminhamento e consulta especializada e o número de pacientes na fila de espera. Métodos. Um estudo retrospectivo com controles contemporâneos foi realizado entre junho de 2014 a julho de 2016. As especialidades selecionadas foram incluídas em uma intervenção de telemedicina e comparadas com as especialidades controle reguladas de forma padrão. Os pacientes de intervenção foram combinados com um conjunto aleatório de controles (proporção 1: 1) por semestre e ano de inclusão na lista de espera e pelo índice de demanda e oferta de consultas especializadas (número de pacientes na fila de espera em junho de 2014 dividido pela média de consultas médicas especializadas disponibilizadas durante os 25 meses que compõem o período de análise). A intervenção de telemedicina incluiu o desenvolvimento de protocolos de referência e classificação de risco de pacientes na fila de espera. O tempo de espera para a consulta presencial e a magnitude da diminuição do número de pacientes na fila no final da observação foram os desfechos primários. Resultados. Nefrologia, pneumologia, urologia, neurologia, neurocirurgia e reumatologia foram selecionados para a intervenção, para um total de 50.185 pacientes (idade média: 51,5 anos) versus 50,124 pacientes controles (idade média: 52,2 anos). O tempo médio para o agendamento de consultas foi de 583,5 dias no grupo de intervenção versus 599,8 dias nos controles (p <0,001). O volume da lista de espera diminuiu 61,4% no grupo de intervenção e 53,2% no grupo controle 13 (<0,001). Para pacientes de alto risco (grupo de intervenção apenas), o tempo médio entre encaminhamento e consultas foi de 235,43 dias. Conclusões. A intervenção de telemedicina foi eficaz para diminuir o tempo de espera, especialmente para indivíduos de alto risco, e número de pacientes em espera para consultas médicas especializadas, o que sinaliza um efeito positivo sobre a eficiência do sistema de saúde, com redução de tempo e custos de deslocamentos, além de potencializar a prevenção quaternária ao prevenir consultas desnecessárias com médicos especilaistas, por meio do melhor manejo dos médicos de atenção primária. / Background. The demand for specialist care is increasing worldwide. We tested a telemedicine initiative to reduce the time between referral and specialist appointment and the number of waitlisted patients. Methods. A retrospective trial with contemporaneous controls was conducted between June 2014-July 2016. Selected specialties were included in a telemedicine intervention and compared to control specialties covered by the usual gatekeeping program. Intervention patients were matched to a random set of controls (1:1 ratio) by semester and year of inclusion in the waiting list and by the specialty demand to supply ratio (number of waitlisted patients in June 2014 divided by the mean number of appointment slots during the 25 months comprising the period of analysis). The telemedicine intervention encompassed development of referral protocols and risk classification of waitlisted patients. Waiting time to face-to-face consultation and magnitude of decrease in the number of waitlisted patients at the end of the observation were defined as primary outcomes. Results. Nephrology, pulmonology, urology, neurology, neurosurgery, and rheumatology were selected for the intervention, for a total 50,185 patients (mean age: 51.5 years) vs. 50,124 patients controls (mean age: 52.2 years). Mean referralto- appointment time was 583.5 days in the intervention group vs. 599.8 days in controls (p<0.001). Waitlist volume decreased 61.4% in the intervention group and 53.2% in the control group (<0.001). For high-risk patients (intervention group only), mean time between referral and appointments was 235.43 days. 15 Conclusions. The telemedicine intervention was effective to decrease wait time, especially for high-risk individuals, and number of waitlisted patients, which signal a positive effect of e-consultations on the knowledge of primary care physicians, reducing time and travel costs and enhancing a quaternary prevention and avoiding unnecessary consultations. / Telemedicina