Master of Science / Department of Computer Science / Doina Caragea / In the last few decades, we have witnessed many natural disasters that have shaken the nations across the world. Millions of people have lost their lives, cities have been destroyed, people have gone homeless, injured and their lives have been affected. Sometimes hours or even days after a disaster, people are still stuck in the disaster sites, powerless, homeless and without food, as the rescue teams do not always get information about people in need in a timely manner. Whenever there is a natural disaster like a hurricane or an earthquake, people start tweeting about it. Most of the tweets are posted by users who are in the disaster sites, and may contain information about victims of the disaster: where they are and what the problem is, in what areas the rescue teams should work or focus on, or if someone needs special help. Such information can be very useful for the response teams, which can leverage this information in the recovery or rescue process. However, rescue team are faced with an information overload problem, due to the large number of tweets they need to sift through. To help with this issue, computational approaches can be used to analyze and prioritize information that may be useful to the rescue teams. In this project, we have crawled tweets related to natural disasters, and extracted useful information in CSV files. Then, we have designed and developed a database to store the tweets. The design of the database is such that it will help us to query and gain information about a natural disaster. We have also performed some statistical analysis, such as deriving word clouds of the tweets posted during natural disasters. The analysis shows the areas where the users who post tweet about disaster are highly concerned. The word cloud analysis can help in comparing multiple natural disasters to understand patterns that are common or specific to disasters in terms of how Twitter users talk about them.

We study the following geometric representation problem: Given a graph whose vertices correspond to axis-aligned rectangles with fixed dimensions, arrange the rectangles without overlaps in the plane such that two rectangles touch if the graph contains an edge between them. This problem is called Contact Representation of Word Networks (Crown) since it formalizes the geometric problem behind drawing word clouds in which semantically related words are close to each other. Crown is known to be NP-hard, and there are approximation algorithms for certain graph classes for the optimization version, Max-Crown, in which realizing each desired adjacency yields a certain profit. We present the first O(1)-approximation algorithm for the general case, when the input is a complete weighted graph, and for the bipartite case. Since the subgraph of realized adjacencies is necessarily planar, we also consider several planar graph classes (namely stars, trees, outerplanar, and planar graphs), improving upon the known results. For some graph classes, we also describe improvements in the unweighted case, where each adjacency yields the same profit. Finally, we show that the problem is APX-complete on bipartite graphs of bounded maximum degree.

No description available.

A análise de dados multidimensionais tem sido por muitos anos tópico de contínua investigação e uma das razões se deve ao fato desse tipo de dados ser encontrado em diversas áreas da ciência. Uma tarefa comum ao se analisar esse tipo de dados é a investigação de padrões pela interação em projeções multidimensionais dos dados para o espaço visual. O entendimento da relação entre as características do conjunto de dados (dataset) e a técnica utilizada para se obter uma representação visual desse dataset é de fundamental importância uma vez que esse entendimento pode fornecer uma melhor intuição a respeito do que se esperar da projeção. Por isso motivado, no presente trabalho investiga-se alguns aspectos de centralidade dos dados em dois cenários distintos: coleções de documentos com grafos de coautoria; dados multidimensionais mais gerais. No primeiro cenário, o dado multidimensional que representa os documentos possui informações mais específicas, o que possibilita a combinação de diferentes aspectos para analisá-los de forma sumarizada, bem como a noção de centralidade e relevância dentro da coleção. Isso é levado em consideração para propor uma metáfora visual combinada que possibilite a exploração de toda a coleção, bem como de documentos individuais. No segundo cenário, de dados multidimensionais gerais, assume-se que tais informações não estão disponíveis. Ainda assim, utilizando um conceito de estatística não-paramétrica, deno- minado funções de profundidade de dados (data-depth functions), é feita a avaliação da ação de técnicas de projeção multidimensionais sobre os dados, possibilitando entender como suas medidas de profundidade (centralidade) foram alteradas ao longo do processo, definindo uma também medida de qualidade para projeções. / Analysis of multidimensional data has been for many years a topic of continuous research and one of the reasons is such kind of data can be found on several different areas of science. A common task analyzing such data is to investigate patterns by interacting with spatializations of the data onto the visual space. Understanding the relation between underlying dataset characteristics and the technique used to provide a visual representation of such dataset is of fundamental importance since it can provide a better intuition on what to expect from the spatialization. Motivated by this, in this work we investigate some aspects of centrality on the data in two different scenarios: document collection with co-authorship graphs; general multidimensional data. In the first scenario, the multidimensional data which encodes the documents is much more information specific, meaning it makes possible to combine different aspects such as a summarized analysis, as well as the centrality and relevance notions among the documents in the collection. In order to propose a combined visual metaphor, this is taken into account make possible the visual exploration of the whole document collection as well as individual document analysis. In the second case, of general multidimensional data, there is an assumption that such additional information is not available. Nevertheless, using the concept of data-depth functions from non-parametric statistics it is analyzed the action of multidimensional projection techniques on the data, during the projection process, in order to make possible to understand how depth measures computed in the data have been modified along the process, which also defines a quality measure for multidimensional projections.

A análise de dados multidimensionais tem sido por muitos anos tópico de contínua investigação e uma das razões se deve ao fato desse tipo de dados ser encontrado em diversas áreas da ciência. Uma tarefa comum ao se analisar esse tipo de dados é a investigação de padrões pela interação em projeções multidimensionais dos dados para o espaço visual. O entendimento da relação entre as características do conjunto de dados (dataset) e a técnica utilizada para se obter uma representação visual desse dataset é de fundamental importância uma vez que esse entendimento pode fornecer uma melhor intuição a respeito do que se esperar da projeção. Por isso motivado, no presente trabalho investiga-se alguns aspectos de centralidade dos dados em dois cenários distintos: coleções de documentos com grafos de coautoria; dados multidimensionais mais gerais. No primeiro cenário, o dado multidimensional que representa os documentos possui informações mais específicas, o que possibilita a combinação de diferentes aspectos para analisá-los de forma sumarizada, bem como a noção de centralidade e relevância dentro da coleção. Isso é levado em consideração para propor uma metáfora visual combinada que possibilite a exploração de toda a coleção, bem como de documentos individuais. No segundo cenário, de dados multidimensionais gerais, assume-se que tais informações não estão disponíveis. Ainda assim, utilizando um conceito de estatística não-paramétrica, deno- minado funções de profundidade de dados (data-depth functions), é feita a avaliação da ação de técnicas de projeção multidimensionais sobre os dados, possibilitando entender como suas medidas de profundidade (centralidade) foram alteradas ao longo do processo, definindo uma também medida de qualidade para projeções. / Analysis of multidimensional data has been for many years a topic of continuous research and one of the reasons is such kind of data can be found on several different areas of science. A common task analyzing such data is to investigate patterns by interacting with spatializations of the data onto the visual space. Understanding the relation between underlying dataset characteristics and the technique used to provide a visual representation of such dataset is of fundamental importance since it can provide a better intuition on what to expect from the spatialization. Motivated by this, in this work we investigate some aspects of centrality on the data in two different scenarios: document collection with co-authorship graphs; general multidimensional data. In the first scenario, the multidimensional data which encodes the documents is much more information specific, meaning it makes possible to combine different aspects such as a summarized analysis, as well as the centrality and relevance notions among the documents in the collection. In order to propose a combined visual metaphor, this is taken into account make possible the visual exploration of the whole document collection as well as individual document analysis. In the second case, of general multidimensional data, there is an assumption that such additional information is not available. Nevertheless, using the concept of data-depth functions from non-parametric statistics it is analyzed the action of multidimensional projection techniques on the data, during the projection process, in order to make possible to understand how depth measures computed in the data have been modified along the process, which also defines a quality measure for multidimensional projections.