[pt] Redes veiculares (VANETs — Vehicle Ad Hoc NETworks) constituem um caso especial de redes ad hoc em que os nós são veículos equipados com uma interface de comunicação sem fio. Esses veículos podem se mover a velocidades elevadas, e a transmissão de dados em cenários urbanos pode ser facilmente bloqueada por prédios ou outros obstáculos. Tais fatores contribuem para tornar a comunicação inter-veicular intermitente, e dificultar o roteamento de pacotes. Um dos principais desafios dos protocolos de roteamento em VANETs é evitar as ruas onde o volume de tráfego esteja baixo, uma vez que a escassez de veículos nessas ruas tende a impossibilitar a propagação de pacotes através delas. Por esse motivo, a informação sobre o volume de tráfego em cada rua é fundamental para se determinar a melhor rota entre dois veículos. Especificamente em cenários urbanos, a mudança de estado dos semáforos provoca uma flutuação do tráfego de veículos ao longo do tempo. Em vista disso, esta tese propõe o TLAR (Traffic Light Aided Routing), um novo algoritmo de roteamento para VANETs que explora a variação de estado dos semáforos para inferir quais ruas oferecerão uma maior probabilidade de sucesso de propagação de pacotes. Resultados de simulação mostram que o algoritmo apresenta um bom desempenho comparado ao de propostas existentes. / [en] VANETs (Vehicle Ad Hoc NETworks) are a special case of mobile ad hoc networks where vehicles are equiped with wireless communication interfaces. These vehicles may move at high speeds and data transmission in urban scenarios may easily be blocked by buildings and other sort of obstacles. Such factors contribute to make inter-vehicle communication intermitent and packet routing more difficult. One of the main challenges faced by routing protocols is avoiding low-traffic streets, where the lack of vehicles tend to make packet forwarding impossible. For this reason, traffic information on each street is essential for the computation of the best route between any given two vehicles. Specifically in urban scenarios, traffic light transitions cause significant fluctuations on traffic flow over time. Given this fact, this thesis proposes TLAR (Traffic Light Aided Routing), a new routing algorithm for VANETs that exploits traffic light transition timings in order to determine which streets will offer the greatest probabilities for successful packet forwarding. Simulation results indicate a good performance of this algorithm compared to existing approaches.

[pt] O objetivo deste trabalho é o de estudar propriedades geométricas de curvas poligonais genéricas. Inicialmente abordamos resultados clássicos para curvas quanto à sua curvatura total no caso discreto e discutimos aqueles pertinentes a nós poligonais. Também é feito o estudo do Grafo de Maxwel para poligonais. No caso, temos uma interessante relação entre a natureza do grafo quanto ao seu número de componentes e à condição de a poligonal ser ou não convexa. / [en] The aim of this work is to study geometrical properties of generic polygonal lines. We begin with some classical results for curves with respect to total curvature, in the discrete case, and discuss results related to polygonal knots. Maxwell graphs are also considered for polygonal lines: We study the relation between the number of components of the graph and the convexity of the polygonal line.

[pt] A montagem de fragmentos de sequências biológicas é um problema fundamental na bioinformática. Na montagem de tipo De Novo, onde não existe um genoma de referência, é usada a estrutura de dados do grafo de Bruijn para auxiliar com o processamento computacional. Em particular, é necessário considerar um conjunto grande de k-mers, substrings das sequências biológicas. No entanto, a construção deste grafo tem grande custo computacional, especialmente muito consumo de memoria principal, tornando-se inviável no caso da montagem de grandes conjuntos de k-mers. Há soluções na literatura que utilizam o modelo de memória externa para conseguir executar o procedimento. Porém, todas envolvem alta redundância nos cálculos envolvendo os k-mers, aumentando consideravelmente o número de operações de E/S. Esta tese propõe uma nova abordagem para a construção do grafo de Bruijn que torna desnecessária a geração de todos os k-mer. A solução permite uma redução dos requisitos computacionais e a viabilidade da execução, o que é confirmado com os resultados experimentais. / [en] Fragment assembly is a current fundamental problem in bioinformatics. In the absence of a reference genome sequence that could guide the whole process, a de Bruijn Graph data structure has been considered to improve the computational processing. Notably, we need to count on a broad set of k-mers, biological sequences substrings. However, the construction of de Bruijn Graphs has a high computational cost, primarily due to main memory consumption. Some approaches use external memory processing to achieve feasibility. These solutions generate all k-mers with high redundancy, increasing the number of managed data and, consequently, the number of I/O operations. This thesis proposes a new approach for de Bruijn Graph construction that does not need to generate all k-mers. The solution enables to reduce computational requirements and execution feasibility, which is confirmed with the experimental results.

[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.

[pt] A otimização do desempenho dos modelos de aprendizado de máquina supervisionados representa um desafio constante, especialmente em contextos com conjuntos de dados de alta dimensionalidade ou com numerosos atributos correlacionados. Neste estudo, é proposto um método para o enriquecimento de conjuntos de dados tabulares, fundamentado na utilização de estatísticas provenientes de um grafo construído a partir da similaridade entre as instâncias presentes neste conjunto de dados, buscando capturar correlações estruturais entre esses dados. As instâncias assumem o papel de vértices no grafo, enquanto as conexões entre elas refletem sua similaridade. O conjunto de características originais (FO) é enriquecido com as estatísticas extraídas do grafo (FG) na busca pela melhora do poder preditivo dos modelos de aprendizado de máquina. O método foi avaliado em dez conjuntos de dados públicos de distintas áreas de conhecimento, em dois cenários distintos, sobre sete modelos de aprendizado de máquina, comparando a predição sobre o conjunto de dados inicial (FO) com o conjunto de dados enriquecido com as estatísticas extraídas do seu grafo (FO+FG). Os resultados revelaram melhorias significativas na métrica de acurácia, com um aprimoramento médio de aproximadamente 4,9 por cento. Além de sua flexibilidade para integração com outras técnicas de enriquecimento existentes, o método se apresenta como uma alternativa eficaz, sobretudo em situações em que os conjuntos de dados originais carecem das características necessárias para as abordagens tradicionais de enriquecimento com a utilização de grafo. / [en] The optimization of supervised machine learning models performancerepresents a constant challenge, especially in contexts with high-dimensionaldatasets or numerous correlated attributes. In this study, we propose a methodfor enriching tabular datasets, based on the use of statistics derived from agraph constructed from the similarity between instances in the dataset, aimingto capture structural correlations among the data. Instances take on the role ofvertices in the graph, while connections between them reflect their similarity.The original feature set (FO) is enriched with statistics extracted from thegraph (FG) to enhance the predictive power of machine learning models. Themethod was evaluated on ten public datasets from different domains, in twodistinct scenarios, across seven machine learning models, comparing predictionon the initial dataset (FO) with the dataset enriched with statistics extractedfrom its graph (FO+FG). The results revealed significant improvements inaccuracy metrics, with an average enhancement of approximately 4.9 percent. Inaddition to its flexibility for integration with existing enrichment techniques,the method presents itself as a effective alternative, particularly in situationswhere original datasets lack the necessary characteristics for traditional graph-based enrichment approaches.

[pt] Este trabalho é uma elaboração, com exemplos, e evolução do Algoritmo de Compressão Horizontal (HC) apresentado e seu Conjunto de Regras de Compressão. Este trabalho apresenta uma prova, feita no Provador Interativo de Teoremas Lean, de que o algoritmo HC pode obter uma Derivação Comprimida, representada por um Grafo Acíclico Dirigido, a partir de qualquer Derivação Tipo-Árvore em Dedução Natural para a Lógica Minimal Puramente Implicacional. Finalmente, a partir da Cobertura e Corretude do algoritmo HC, pode-se argumentar que NP = PSPACE. / [en] This work is an elaboration, with examples, and evolution of the presented Horizontal Compression Algorithm (HC) and its set of Compression Rules. This work argues a proof, done in the Lean Interactive Theorem Prover, that the HC algorithm can obtain a Compressed Derivation, represented by a Directed Acyclic Graph, from any Tree-Like Natural Deduction Derivation in Minimal Purely Implicational Logic. Finally, from the Coverage and Soundness of the HC algorithm, one can argue that NP = PSPACE.

[pt] Busca por palavras-chave fornece uma interface fácil de usar para recuperar informação. Esta tese contribui para os problemas de busca por palavras chave em conjuntos de dados sem esquema e trajetórias semânticas baseados no Resource Description Framework. Para endereçar o problema da busca por palavras-chave em conjuntos de dados RDF sem esquema, a tese introduz um algoritmo para traduzir automaticamente uma consulta K baseada em palavras-chave especificadas pelo usuário em uma consulta SPARQL Q de tal forma que as respostas que Q retorna também são respostas para K. O algoritmo não depende de um esquema RDF, mas sintetiza as consultas SPARQL explorando a semelhança entre os domínios e contradomínios das propriedades e os conjuntos de instâncias de classe observados no grafo RDF. O algoritmo estima a similaridade entre conjuntos com base em sinopses, que podem ser precalculadas, com eficiência, em uma única passagem sobre o conjunto de dados RDF. O trabalho inclui dois conjuntos de experimentos com uma implementação do algoritmo. O primeiro conjunto de experimentos mostra que a implementação supera uma ferramenta de pesquisa por palavras-chave sobre grafos RDF que explora o esquema RDF para sintetizar as consultas SPARQL, enquanto o segundo conjunto indica que a implementação tem um desempenho melhor do que sistemas de pesquisa por palavras-chave em conjuntos de dados RDF baseados na abordagem de documentos virtuais denominados TSA+BM25 e TSA+VDP. Finalmente, a tese também computa a eficácia do algoritmo proposto usando uma métrica baseada no conceito de relevância do grafo resposta. O segundo problema abordado nesta tese é o problema da busca por palavras-chave sobre trajetórias semânticas baseadas em RDF. Trajetórias semânticas são trajetórias segmentadas em que as paradas e os deslocamentos de um objeto móvel são semanticamente enriquecidos com dados adicionais. Uma linguagem de consulta para conjuntos de trajetórias semânticas deve incluir seletores para paradas ou deslocamentos com base em seus enriquecimentos e expressões de sequência que definem como combinar os resultados dos seletores com a sequência que a trajetória semântica define. A tese inicialmente propõe um framework formal para definir trajetórias semânticas e introduz expressões de sequências de paradas-e-deslocamentos (stop-and-move sequences), com sintaxe e semântica bem definidas, que atuam como uma linguagem de consulta expressiva para trajetórias semânticas. A tese descreve um modelo concreto de trajetória semântica em RDF, define expressões de sequências de paradas-e-deslocamentos em SPARQL e discute estratégias para compilar tais expressões em consultas SPARQL. A tese define consultas sobre trajetórias semânticas com base no uso de palavras-chave para especificar paradas e deslocamentos e a adoção de termos com semântica predefinida para compor expressões de sequência. Em seguida, descreve como compilar tais expressões em consultas SPARQL, mediante o uso de padrões predefinidos. Finalmente, a tese apresenta uma prova de conceito usando um conjunto de trajetórias semânticas construído com conteúdo gerado pelos usuários do Flickr, combinado com dados da Wikipedia. / [en] Keyword search provides an easy-to-use interface for retrieving information. This thesis contributes to the problems of keyword search over schema-less datasets and semantic trajectories based on RDF. To address the keyword search over schema-less RDF datasets problem, this thesis introduces an algorithm to automatically translate a user-specified keyword-based query K into a SPARQL query Q so that the answers Q returns are also answers for K. The algorithm does not rely on an RDF schema, but it synthesizes SPARQL queries by exploring the similarity between the property domains and ranges, and the class instance sets observed in the RDF dataset. It estimates set similarity based on set synopses, which can be efficiently precomputed in a single pass over the RDF dataset. The thesis includes two sets of experiments with an implementation of the algorithm. The first set of experiments shows that the implementation outperforms a baseline RDF keyword search tool that explores the RDF schema, while the second set of experiments indicate that the implementation performs better than the stateof- the-art TSA+BM25 and TSA+VDP keyword search systems over RDF datasets based on the virtual documents approach. Finally, the thesis also computes the effectiveness of the proposed algorithm using a metric based on the concept of graph relevance. The second problem addressed in this thesis is the keyword search over RDF semantic trajectories problem. Stop-and-move semantic trajectories are segmented trajectories where the stops and moves are semantically enriched with additional data. A query language for semantic trajectory datasets has to include selectors for stops or moves based on their enrichments, and sequence expressions that define how to match the results of selectors with the sequence the semantic trajectory defines. The thesis first proposes a formal framework to define semantic trajectories and introduces stop and move sequence expressions, with well-defined syntax and semantics, which act as an expressive query language for semantic trajectories. Then, it describes a concrete semantic trajectory model in RDF, defines SPARQL stop-and-move sequence expressions, and discusses strategies to compile such expressions into SPARQL queries. Next, the thesis specifies user-friendly keyword search expressions over semantic trajectories based on the use of keywords to specify stop and move queries, and the adoption of terms with predefined semantics to compose sequence expressions. It then shows how to compile such keyword search expressions into SPARQL queries. Finally, it provides a proof-of-concept experiment over a semantic trajectory dataset constructed with user-generated content from Flickr, combined with Wikipedia data.