Made available in DSpace on 2014-06-12T18:27:30Z (GMT). No. of bitstreams: 2 arquivo1642_1.pdf: 3240172 bytes, checksum: 20b51b421dc923f18b5115c1606bb545 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho aqui apresentado consiste de um modelo para automação de horários escolares, cujo problema está baseado no estudo de casos brasileiros, e também consiste de uma análise da relação entre as restrições do problema e sua complexidade. O problema automação de horários escolares é um problema NP-completo, mesmo nos casos mais simples, onde as restrições mantidas são o mínimo absolutamente necessário. Aqui são construídas ou apresentadas provas desta relação entre as restrições e o problema. O modelo usa programação inteira para encontrar uma solução viável inicial. Uma vez encontrada, é aplicada uma heurística desenvolvida para trabalhar com trocas locais via um grafo chamado grafo híbrido. A solução viável inicial também pode ser encontrada por uma heurística que usa trocas via o grafo híbrido. Estas heurísticas são essencialmente meta-heurísticas busca tabu. O grafo híbrido, que é facilmente construído dos dados do problema, permitiu a definição de movimentos (mudanças) que aplicados a uma solução preservam o atendimento a um grande número de restrições. A descoberta do grafo híbrido fez uma grande diferença em nosso trabalho: nenhuma outra estrutura de dados na literatura (tanto quanto sabemos) tem a flexibilidade de acompanhar uma troca de horários atribuídos a um par de encontros às suas últimas conseqüências. As trocas são rápidas e milhares de soluções viáveis podem ser facilmente geradas e comparadas. A idéia do grafo híbrido tem aplicações a uma grande variedade de problemas de horários e de restrições de conflitos

Made available in DSpace on 2014-06-12T18:29:06Z (GMT). No. of bitstreams: 2 arquivo4270_1.pdf: 3240198 bytes, checksum: 40ce23c71a96036f67deaa9c0522df1a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2008 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O trabalho aqui apresentado consiste de um modelo para automação de horários escolares, cujo problema está baseado no estudo de casos brasileiros, e também consiste de uma análise da relação entre as restrições do problema e sua complexidade. O problema automação de horários escolares é um problema NP-completo, mesmo nos casos mais simples, onde as restrições mantidas são o mínimo absolutamente necessário. Aqui são construídas ou apresentadas provas desta relação entre as restrições e o problema. O modelo usa programação inteira para encontrar uma solução viável inicial. Uma vez encontrada, é aplicada uma heurística desenvolvida para trabalhar com trocas locais via um grafo chamado grafo híbrido. A solução viável inicial também pode ser encontrada por uma heurística que usa trocas via o grafo híbrido. Estas heurísticas são essencialmente meta-heurísticas busca tabu. O grafo híbrido, que é facilmente construído dos dados do problema, permitiu a definição de movimentos (mudanças) que aplicados a uma solução preservam o atendimento a um grande número de restrições. A descoberta do grafo híbrido fez uma grande diferença em nosso trabalho: nenhuma outra estrutura de dados na literatura (tanto quanto sabemos) tem a flexibilidade de acompanhar uma troca de horários atribuídos a um par de encontros às suas últimas conseqüências. As trocas são rápidas e milhares de soluções viáveis podem ser facilmente geradas e comparadas. A idéia do grafo híbrido tem aplicações a uma grande variedade de problemas de horários e de restrições de conflitos

[pt] Neste trabalho, apresentamos algoritmos aproximativos para dois problemas de otimização em árvores. Na primeira parte, consideramos o Problema de Atribuição de k-Hotlinks. Seja G= (V,E) um grafo direcionado acíclico representando um web site, onde nós correspondem a páginas e arcos correspondem a hyperlinks. Nesse contexto, hotlink são definidos como atalhos (novos arcos) adicionados às páginas de G de modo a reduzir o tempo gasto pelos usuários para alcançarem as informações desejadas. Neste trabalho consideramos o problema onde G é uma árvore enraizada e o objetivo é minimizar o tempo médio gasto pelos usuários atribuindo no máximo k hotlinks a cada nó. Para a versão mais estudada desse problema onde no máximo um hotlink pode ser atribuído a cada nó, provamos a existência de um FPTAS. Isso representa uma significante melhora em relação ao algoritmo com aproximação constante obtido recentemente em [Jacobs, WADS 2007]. Além disso, desenvolvemos o primeiro algoritmo com aproximação constante para a versão mais geral onde k hotlinks podem ser atribuídos a cada nó. Na segunda parte deste trabalho, consideramos o problema de computar estratégias eficientes para realizar buscas em árvores. Como uma generalização da tradicional busca binária em listas ordenadas, suponha que se deseja encontrar um nó específico (porém desconhecido) de uma árvore realizando consultas em seus arcos, onde cada consulta indica a extremidade do arco mais próxima ao nó desejado. Dada a probabilidade de cada nó ser aquele procurado, o objetivo é computar uma estratégia de busca que minimize o número esperado de consultas. Aplicações práticas desse problema incluem sincronização de file systems e testes de software. Apresentamos um algoritmo linear que obtém a primeira aproximação constante para esse problema. Isso representa uma melhora significativa em relação à O(log n)-aproximação anterior. / [en] Here we present a study on two optimization problems in trees: the k- Hotlink Assignment Problem and the problem of Binary Searching in Trees. As a result, we obtain improved approximation algorithms for both problem. The k-Hotlink Assignment Problem can be defined as follows. Let G = (V,E) be a directed acyclic graph representing a web site, where nodes correspond to pages and arcs to hyperlinks. In this context, hotlinks are defined as shortcuts (new arcs) added to web pages of G in order to reduce the time spent by users to reach their desired information. Here we consider the problem where G is a rooted directed tree and the goal is minimizing the expected time spent by users by assigning at most k hotlinks to each node. For the most studied version of this problem where at most one hotlink can be assigned from each node, we prove the existence of an FPTAS, improving upon the constant factor algorithm recently obtained in [Jacobs, WADS 2007]. In addition, we develop the first constant factor approximation algorithm for the most general version where k hotlinks can be assigned from each node. In the second part of this work, we consider the problem of computing efficient strategies for searching in trees. As a generalization of the classical binary search for ordered lists, suppose one wishes to find a (unknown) specific node of a tree by asking queries to its arcs, where each query indicates the endpoint closer to the desired node. Given the likelihood of each node being the one searched, the objective is to compute a search strategy that minimizes the expected number of queries. Practical applications of this problem include file system synchronization and software testing. Here we present a linear time algorithm which is the first constant factor approximation for this problem. This represents a significant improvement over previous O(log n)-approximation.

[pt] Links patrocinados são aqueles que aparecem em destaque nos resultados de pesquisas em máquinas de busca na Internet e são grande fonte de receita para seus provedores. Para os anunciantes, que fazem ofertas por palavras-chave para aparecerem em destaque nas consultas dos usuários, são uma oportunidade de divulgação da marca, conquista e manutenção de clientes. Um dos desafios das máquinas de busca neste modelo de negócio é selecionar os anunciantes que serão exibidos a cada consulta de modo a maximizar sua receita em determinado período. Este é um problema tipicamente online, onde a cada consulta é tomada uma decisão sem o conhecimento prévio das próximas consultas. Após uma decisão ser tomada, esta não pode mais ser alterada. Nesta dissertação avaliamos experimentalmente algoritmos propostos na literatura para solução deste problema, comparando-os à solução ótima offline, em simulações com dados sintéticos. Supondo que o conjunto das consultas diárias obedeça a uma determinada distribuição, propomos dois algoritmos baseados em informações estocásticas que são avaliados nos mesmos cenários que os outros algoritmos. / [en] Sponsored links are those that appear highlighted at Internet search engine results. They are responsible for a large amount of their providers’ revenue. To advertisers, that place bids for keywords in large auctions at Internet, these links are the opportunity of brand exposing and achieving more clients. To search engine companies, one of the main challenges in this business model is selecting which advertisers should be allocated to each new query to maximize their total revenue in the end of the day. This is a typical online problem, where for each query is taken a decision without previous knowledge of future queries. Once the decision is taken, it can not be modified anymore. In this work, using synthetically generated data, we do experimental evaluation of three algorithms proposed in the literature for this problem and compare their results with the optimal offline solution. Considering that daily query set obeys some well known distribution, we propose two algorithms based on stochastic information, those are evaluated in the same scenarios of the others.

Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2016-04-20T18:19:49Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação Leitura recepcional do texto literário em WebQuest.pdf: 7931809 bytes, checksum: ab605724f18c109bd2d16319ece98ef8 (MD5) / Made available in DSpace on 2016-04-20T18:19:49Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Dissertação Leitura recepcional do texto literário em WebQuest.pdf: 7931809 bytes, checksum: ab605724f18c109bd2d16319ece98ef8 (MD5) Previous issue date: 2015-07-28 / CAPES / Esta dissertação tem por objetivo analisar o horizonte de expectativas de alunos do 9º ano do ensino fundamental, diante da leitura de texto literário mediada por uma WebQuest, que conceba o leitor na recepção e explore possibilidades de construção de sentidos do texto literário. Para isso, fundamentamos a pesquisa em duas linhas na proposição de um trabalho com leitura literária: a leitura recepcional difundida pela Estética da Recepção (JAUSS, 1983, 2011; ISER, 1996, 1999); e uma proposta metodológica, a WebQuest,uma ferramenta educacional tecnológica que contempla uma formação em coerência com a nova relação do saber diante das transformações exigidas em tempo de cibercultura (LÉVY, 1999). Essa pesquisa-ação parte da limitação de leitura dos alunos, que, muitas vezes, não ultrapassam o plano denotado no linguístico do texto literário, para propor à leitura de A Nova Califórnia de Lima Barreto por meio da ferramenta mencionada, que é o instrumento para coleta do corpus que foi analisado. Os dados analisados mostraram que os alunos concretizaram significados do conto e mobilizaram informações dispostas por links de pesquisa na WQ para construir sentidos no texto lido, demonstrando uma mudança no horizonte de expectativas inicial da leitura. / Esta disertación tiene como objetivo analizar el horizonte de expectativas de los alumnos del 9° año de la enseñanza fundamental delante de la lectura de texto literario mediada por una WebQuest que conciba el lector en la recepción y explore posibilidades de construcción de sentidos del texto literario. Para eso, fundamentamos la pesquisa en dos líneas en la proposición de un trabajo con lectura literaria: la lectura recepcional difundida por la Estética de la Recepción (JAUSS, 1983, 2011; ISER, 1996, 1999); y una propuesta metodológica, la WebQuest, una herramienta educacional tecnológica que contempla una formación en coherencia con la nueva relación del saber delante de las transformaciones exigidas en tiempo de cibercultura (LÉVY, 1999). Esta pesquisa-acción parte de la limitación de lectura de los alumnos, que, muchas veces, no ultrapasan el plan denotado en el lingüístico del texto literario, para proponer a la lectura de A Nova Califórnia, de Lima Barreto, por medio de la herramienta mencionada, que es el instrumento para coleta del corpus que fue analizado. Los datos analizados mostraron que los alumnos concretizaron significados del cuento y mobilizaron informaciones dispuestas por links de la pesquisa en la WebQuest para construir sentidos en el texto leído, lo que demonstra que hubo un cambio en el horizonte de las expectativas inicial de la lectura.

A diversidade biológica é essencial para a sustentabilidade da vida na Terra e motiva numerosos esforços para coleta de dados sobre espécies, dando origem a uma grande quantidade de informação. Esses dados são geralmente armazenados em bancos de dados relacionais. Pesquisadores usam esses bancos de dados para extrair conhecimento e compartilhar novas descobertas. No entanto, atualmente a busca tradicional (baseada em palavras-chave) já não é adequada para ser usada em grandes quantidades de dados heterogêneos, como os de biodiversidade. Ela tem baixa precisão e revocação para esse tipo de dado. Este trabalho apresenta uma nova arquitetura para abordar esse problema aplicando técnicas de buscas semânticas em dados sobre biodiversidade e usando formatos e ferramentas da Web Semântica para representar esses dados. A busca semântica tem como objetivo melhorar a acurácia dos resultados de buscas com o uso de ontologias para entender os objetivos dos usuários e o significado contextual dos termos utilizados. Este trabalho também apresenta os resultados de testes usando um conjunto de dados representativos sobre biodiversidade do Instituto Nacional de Pesquisas da Amazônia (INPA) e do Museu Paraense Emílio Goeldi (MPEG). Ontologias permitem que conhecimento seja organizado em espaços conceituais de acordo com seu significado. Para a busca semântica funcionar, um ponto chave é a criação de mapeamentos entre os dados (neste caso, dados sobre biodiversidade do INPA e MPEG) e termos das ontologias que os descrevem, neste caso: a classificação taxonômica de espécies e a OntoBio, a ontologia de biodiversidade do INPA. Esses mapeamentos foram criados depois que extraímos a classificação taxonômica do site Catalog of Life (CoL) e criamos uma nova versão da OntoBio. Um protótipo da arquitetura foi construído e testado usando casos de uso e dados do INPA e MPEG. Os resultados dos testes mostraram que a abordagem da busca semântica tinha uma melhor precisão (28% melhor) e revocação (25% melhor) quando comparada com a busca por palavras-chave. Eles também mostraram que é possível conectar facilmente os dados mapeados a outras fontes de dados abertas, como a fonte Amazon Forest Linked Data do Instituto Nacional de Pesquisas Espaciais. (INPE) / Biological diversity is of essential value to life sustainability on Earth and motivates many efforts to collect data about species. That gives rise to a large amount of information. Biodiversity data, in most cases, is stored in relational databases. Researchers use this data to extract knowledge and share their new discoveries about living things. However, nowadays the traditional search approach (based basically on keywords matching) is not appropriate to be used in large amounts of heterogeneous biodiversity data. Search by keyword has low precision and recall in this kind of data. This work presents a new architecture to tackle this problem using a semantic search system for biodiversity data and semantic web formats and tools to represent this data. Semantic search aims to improve search accuracy by using ontologies to understand user objectives and the contextual meaning of terms used in the search to generate more relevant results. This work also presents test results using a set of representative biodiversity data from the National Research Institute for the Amazon (INPA) and the Emilio Gueldi Museum in Pará (MPEG). Ontologies allow knowledge to be organized into conceptual spaces in accordance to its meaning. For semantic search to work, a key point is to create mappings between the data (in this case, INPAs and MPEGs biodiversity data) and the ontologies describing it, in this case: the species taxonomy (a taxonomy is an ontology where each class can have just one parent) and OntoBio, INPAs biodiversity ontology. These mappings were created after we extracted the taxonomic classification from the Catalogue of Life (CoL) website and created a new version of OntoBio. A prototype of the architecture was built and tested using INPAs and MPEGs use cases and data. The results showed that the semantic search approach had a better precision (28% improvement) and recall (25% improvement) when compared to keyword based search. They also showed that it was possible to easily connect the mapped data to other Linked Open Data sources, such as the Amazon Forest Linked Data from the National Institute for Space Research (INPE)

O problema de seleção de características, no contexto de Reconhecimento de Padrões, consiste na escolha de um subconjunto X de um conjunto S de características, de tal forma que X seja \"ótimo\" dentro de algum critério. Supondo a escolha de uma função custo c apropriada, o problema de seleção de características é reduzido a um problema de busca que utiliza c para avaliar os subconjuntos de S e assim detectar um subconjunto de características ótimo. Todavia, o problema de seleção de características é NP-difícil. Na literatura existem diversos algoritmos e heurísticas propostos para abordar este problema; porém, quase nenhuma dessas técnicas explora o fato que existem funções custo cujos valores são estimados a partir de uma amostra e que descrevem uma \"curva em U\" nas cadeias do reticulado Booleano (P(S),<=), um fenômeno bem conhecido em Reconhecimento de Padrões: conforme aumenta-se o número de características consideradas, há uma queda no custo do subconjunto avaliado, até o ponto em que a limitação no número de amostras faz com que seguir adicionando características passe a aumentar o custo, devido ao aumento no erro de estimação. Em 2010, Ris e colegas propuseram um novo algoritmo para resolver esse caso particular do problema de seleção de características, que aproveita o fato de que o espaço de busca pode ser organizado como um reticulado Booleano, assim como a estrutura de curvas em U das cadeias do reticulado, para encontrar um subconjunto ótimo. Neste trabalho estudamos a estrutura do problema de minimização de funções custo cujas cadeias são decomponíveis em curvas em U (problema U-curve), provando que o mesmo é NP-difícil. Mostramos que o algoritmo de Ris e colegas possui um erro que o torna de fato sub-ótimo, e propusemos uma versão corrigida e melhorada do mesmo, o algoritmo U-Curve-Search (UCS). Apresentamos também duas variações do algoritmo UCS que controlam o espaço de busca de forma mais sistemática. Introduzimos dois novos algoritmos branch-and-bound para abordar o problema, chamados U-Curve-Branch-and-Bound (UBB) e Poset-Forest-Search (PFS). Para todos os algoritmos apresentados nesta tese, fornecemos análise de complexidade de tempo e, para alguns deles, também prova de corretude. Implementamos todos os algoritmos apresentados utilizando o arcabouço featsel, também desenvolvido neste trabalho; realizamos experimentos ótimos e sub-ótimos com instâncias de dados reais e simulados e analisamos os resultados obtidos. Por fim, propusemos um relaxamento do problema U-curve que modela alguns tipos de projeto de classificadores; também provamos que os algoritmos UCS, UBB e PFS resolvem esta versão generalizada do problema. / The feature selection problem, in the context of Pattern Recognition, consists in the choice of a subset X of a set S of features, such that X is \"optimal\" under some criterion. If we assume the choice of a proper cost function c, then the feature selection problem is reduced to a search problem, which uses c to evaluate the subsets of S, therefore finding an optimal feature subset. However, the feature selection problem is NP-hard. Although there are a myriad of algorithms and heuristics to tackle this problem in the literature, almost none of those techniques explores the fact that there are cost functions whose values are estimated from a sample and describe a \"U-shaped curve\" in the chains of the Boolean lattice o (P(S),<=), a well-known phenomenon in Pattern Recognition: for a fixed number of samples, the increase in the number of considered features may have two consequences: if the available sample is enough to a good estimation, then it should occur a reduction of the estimation error, otherwise, the lack of data induces an increase of the estimation error. In 2010, Ris et al. proposed a new algorithm to solve this particular case of the feature selection problem: their algorithm takes into account the fact that the search space may be organized as a Boolean lattice, as well as that the chains of this lattice describe a U-shaped curve, to find an optimal feature subset. In this work, we studied the structure of the minimization problem of cost functions whose chains are decomposable in U-shaped curves (the U-curve problem), and proved that this problem is actually NP-hard. We showed that the algorithm introduced by Ris et al. has an error that leads to suboptimal solutions, and proposed a corrected and improved version, the U-Curve-Search (UCS) algorithm. Moreover, to manage the search space in a more systematic way, we also presented two modifications of the UCS algorithm. We introduced two new branch-and-bound algorithms to tackle the U-curve problem, namely U-Curve-Branch-and-Bound (UBB) and Poset-Forest-Search (PFS). For each algorithm presented in this thesis, we provided time complexity analysis and, for some of them, also proof of correctness. We implemented each algorithm through the featsel framework, which was also developed in this work; we performed optimal and suboptimal experiments with instances from real and simulated data, and analyzed the results. Finally, we proposed a generalization of the U-curve problem that models some kinds of classifier design; we proved the correctness of the UCS, UBB, and PFS algorithms for this generalized version of the U-curve problem.

[pt] Em cenários de tomada de decisão, quando um agente, humano ou máquina, necessita de mais conhecimento para decidir devido a uma lacuna de conhecimento, surge uma necessidade de informação. Os usuários podem conscientemente tomar a iniciativa de adquirir conhecimento para preencher essa lacuna através de tarefas de buscas por informação. As consultas do usuário podem ser incompletas, imprecisas e ambíguas. Isso ocorre porque parte da informação necessária está implícita ou porque o usuário não compreende totalmente o domínio ou a tarefa que motiva a busca. Esta condição está prevista nas abordagens de busca exploratória. Embora os Grafos de Conhecimento (KG) sejam reconhecidos como fontes de informação com grande potencial para integração de dados e busca exploratória, eles são incompletos por natureza. Além disso, KGs Crowdsourced, ou KGs construídos pela integração de diversas fontes de informação de qualidade variável, precisam de uma Camada de Confiança para serem eficazes no suporte a processos de tomada de decisão. A avaliação da veracidade do conhecimento depende dos contextos das alegações e das tarefas a serem realizadas ou pretendidas (propósito). Esta pesquisa tem como objetivo preparar e consultar KGs para apoiar a exploração ciente de contexto em cenários de tomada de decisão. As contribuições incluem uma arquitetura para sistemas de apoio à decisão, composta por uma Camada de Decisão, uma Camada de Confiança e uma Camada de Conhecimento que opera sob a hipótese de Mundo Aberto Dual. A Camada de Conhecimento é composta por um Grafo de Conhecimento enriquecido de Contexto (CoaKG) e uma Máquina de Consulta baseada em CoaKG. CoaKG estende um KG padrão com mapeamentos de contexto para identificar o contexto explicitamente representado e regras para inferir o contexto implícito. A máquina de Consulta baseada em CoaKG foi projetada como uma abordagem de resposta a consultas que recupera todas as respostas contextualizadas (possíveis). A Wikidata é objeto de uma Prova de Conceito para avaliar a eficácia da Camada de Conhecimento. / [en] In decision-making scenarios, an information need arises when an agent, human, or machine needs more knowledge to decide due to a knowledge gap. Users can consciously take the initiative to acquire knowledge to fill this gap through information search tasks. User queries can be incomplete, inaccurate, and ambiguous. It occurs because part of the information needed is implicit or because the user does not fully understand the domain or the task that motivates the search. This condition is foreseen within the exploratory search approaches. Although Knowledge Graphs (KG) are recognized as information sources with great potential for data integration and exploratory search, they are incomplete by nature. Besides, Crowdsourced KGs, or KGs constructed by integrating several different information sources of varying quality, need a Trust Layer to be effective. The evaluation of knowledge truthfulness depends upon the contexts of claims and tasks being carried out or intended (purpose). This research aims to prepare and query KGs to support context-aware exploration in decision-making scenarios. The contributions include a framework for Context Augmented Knowledge Graphs-based Decision Support Systems composed of a Decision Layer, a Trust Layer, and a Knowledge Layer that operates under a Dual Open World Assumption. The Knowledge Layer comprises a Context Augmented KG (CoaKG) and a CoaKG Query Engine. CoaKG contains contextual mappings to identify explicit context and rules to infer implicit context. CoaKG Query Engine is designed as a query-answering approach that retrieves all contextualized (possible answers) from the CoaKG. Wikidata is the object of a Proof of Concept to evaluate the effectiveness of the Knowledge Layer.

A crescente disponibilidade de dados em diferentes domínios tem motivado o desenvolvimento de técnicas para descoberta de conhecimento em grandes volumes de dados complexos. Trabalhos recentes mostram que a busca em dados complexos é um campo de pesquisa importante, já que muitas tarefas de mineração de dados, como classificação, detecção de agrupamentos e descoberta de motifs, dependem de algoritmos de busca ao vizinho mais próximo. Para resolver o problema da busca dos vizinhos mais próximos em domínios complexos muitas abordagens determinísticas têm sido propostas com o objetivo de reduzir os efeitos da maldição da alta dimensionalidade. Por outro lado, algoritmos probabilísticos têm sido pouco explorados. Técnicas recentes relaxam a precisão dos resultados a fim de reduzir o custo computacional da busca. Além disso, em problemas de grande escala, uma solução aproximada com uma análise teórica sólida mostra-se mais adequada que uma solução exata com um modelo teórico fraco. Por outro lado, apesar de muitas soluções exatas e aproximadas de busca e mineração terem sido propostas, o modelo de programação em CPU impõe restrições de desempenho para esses tipos de solução. Uma abordagem para melhorar o tempo de execução de técnicas de recuperação e mineração de dados em várias ordens de magnitude é empregar arquiteturas emergentes de programação paralela, como a arquitetura CUDA. Neste contexto, este trabalho apresenta uma proposta para buscas kNN de alto desempenho baseada numa técnica de hashing e implementações paralelas em CUDA. A técnica proposta é baseada no esquema LSH, ou seja, usa-se projeções em subespac¸os. O LSH é uma solução aproximada e tem a vantagem de permitir consultas de custo sublinear para dados em altas dimensões. Usando implementações massivamente paralelas melhora-se tarefas de mineração de dados. Especificamente, foram desenvolvidos soluções de alto desempenho para algoritmos de descoberta de motifs baseados em implementações paralelas de consultas kNN. As implementações massivamente paralelas em CUDA permitem executar estudos experimentais sobre grandes conjuntos de dados reais e sintéticos. A avaliação de desempenho realizada neste trabalho usando GeForce GTX470 GPU resultou em um aumento de desempenho de até 7 vezes, em média sobre o estado da arte em buscas por similaridade e descoberta de motifs / The increasing availability of data in diverse domains has created a necessity to develop techniques and methods to discover knowledge from huge volumes of complex data, motivating many research works in databases, data mining and information retrieval communities. Recent studies have suggested that searching in complex data is an interesting research field because many data mining tasks such as classification, clustering and motif discovery depend on nearest neighbor search algorithms. Thus, many deterministic approaches have been proposed to solve the nearest neighbor search problem in complex domains, aiming to reduce the effects of the well-known curse of dimensionality. On the other hand, probabilistic algorithms have been slightly explored. Recently, new techniques aim to reduce the computational cost relaxing the quality of the query results. Moreover, in large-scale problems, an approximate solution with a solid theoretical analysis seems to be more appropriate than an exact solution with a weak theoretical model. On the other hand, even though several exact and approximate solutions have been proposed, single CPU architectures impose limits on performance to deliver these kinds of solution. An approach to improve the runtime of data mining and information retrieval techniques by an order-of-magnitude is to employ emerging many-core architectures such as CUDA-enabled GPUs. In this work we present a massively parallel kNN query algorithm based on hashing and CUDA implementation. Our method, based on the LSH scheme, is an approximate method which queries high-dimensional datasets with sub-linear computational time. By using the massively parallel implementation we improve data mining tasks, specifically we create solutions for (soft) realtime time series motif discovery. Experimental studies on large real and synthetic datasets were carried out thanks to the highly CUDA parallel implementation. Our performance evaluation on GeForce GTX 470 GPU resulted in average runtime speedups of up to 7x on the state-of-art of similarity search and motif discovery solutions

Made available in DSpace on 2014-12-17T15:48:07Z (GMT). No. of bitstreams: 1 CamilaNOT_DISSERT.pdf: 4321465 bytes, checksum: d103bd2da647997e8dfd0a8784c2060d (MD5) Previous issue date: 2013-02-01 / Nonogram is a logical puzzle whose associated decision problem is NP-complete. It has applications in pattern recognition problems and data compression, among others. The puzzle consists in determining an assignment of colors to pixels distributed in a N &#61620; M matrix that satisfies line and column constraints. A Nonogram is encoded by a vector whose elements specify the number of pixels in each row and column of a figure without specifying their coordinates. This work presents exact and heuristic approaches to solve Nonograms. The depth first search was one of the chosen exact approaches because it is a typical example of brute search algorithm that is easy to implement. Another implemented exact approach was based on the Las Vegas algorithm, so that we intend to investigate whether the randomness introduce by the Las Vegas-based algorithm would be an advantage over the depth first search. The Nonogram is also transformed into a Constraint Satisfaction Problem. Three heuristics approaches are proposed: a Tabu Search and two memetic algorithms. A new function to calculate the objective function is proposed. The approaches are applied on 234 instances, the size of the instances ranging from 5 x 5 to 100 x 100 size, and including logical and random Nonograms / O Nonograma ? um jogo l?gico cujo problema de decis?o associado ? NP-completo. Ele possui aplica??o em problemas de identifica??o de padr?es e de compacta??o de dados, dentre outros. O jogo consiste em determinar uma aloca??o de cores em pixels distribu?dos em uma matriz N &#61620; M atendendo restri??es em linhas e colunas. Um Nonograma ? codificado atrav?s de vetores cujos elementos especificam o n?mero de pixels existentes em cada coluna e linha de uma figura, sem especificar suas coordenadas. Este trabalho apresenta abordagens exatas e heur?sticas para solucionar o Nonograma. A Busca em Profundidade foi uma das abordagens exatas escolhida, por ser um exemplo t?pico de algoritmo de for?a bruta de f?cil implementa??o. Outra abordagem exata implementada foi baseada no algoritmo Las Vegas, atrav?s do qual se pretende investigar se a aleatoriedade introduzida pelo algoritmo Las Vegas traria algum benef?cio em rela??o ? Busca em Profundidade. O Nonograma tamb?m ? transformado em um Problema de Satisfa??o de Restri??es. Tr?s abordagens heur?sticas s?o propostas: uma Busca Tabu e dois algoritmos Mem?tico. Uma nova abordagem para o c?lculo da fun??o objetivo ? proposta neste trabalho. As abordagens s?o testadas em 234 casos de teste de tamanho entre 5 x 5 e 100 x 100, incluindo Nonogramas l?gicos e aleat?rios