As biomedical research and advances in biotechnology generate expansive datasets, the need to process this data into information has grown simultaneously. Specifically, recognizing and extracting these “key” phrases comprising the named entities from this information databank promises a plethora of applications for scientists. The ability to construct interaction maps,identify proteins as drug targets are two important applications. Since we have the choice of defining what is “useful”, we can potentially utilize text mining for our purpose. In a novel attempt to beat the challenge, we have put information theory and text compression through this task. Prediction by partial matching is an adaptive text encoding scheme that blends together a set of finite context Markov models to predict the probability of the next token in a given symbol stream. We observe, named entities such as gene names, protein names, gene functions, protein-protein interactions – all follow symbol statistics uniquely different from normal scientific text. By using well defined training sets that allow us to selectively differentiate between named entities and the rest of the symbols; we were able to extract them with a good accuracy. We have implemented our tests, using the Text Mining Toolkit, on identification of gene functions and protein-protein interactions with f-scores (based on precision & recall) of 0.9737 and 0.6865 respectively. With our results, we foresee the application of such an approach in automated information retrieval in the realm of biology.

Made available in DSpace on 2015-05-14T12:36:32Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1384872 bytes, checksum: 17a26f8a3828692a7cd893ffaf2ff3f9 (MD5) Previous issue date: 2010-04-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The usage of mammographic image databases in digital form and the practice of telemedicine require to store and to transmit large amounts of data. The image digitization from a single mammographic exam with appropriate resolution can take up to 120MB of space in disk, which becomes even more critical when considering the large number of exams per day on a clinic. Thus, efficient data compression techniques are needed to reduce storage and transmission costs. This document describes the development of a high-performance lossless compressor based on Prediction by Partial Matching (PPM) algorithm with modules for segmentation, mapping, gray code, bit planes decomposition and move-to-front transform, for mammographic image compression. The compressor developed was efficient in both compression ratio and processing time, and compresses 27MB images in about 13 seconds with an average compression ratio of 5,39. / A utilização de bancos de dados de imagens mamográficas em formato digital e as práticas de telemedicina exigem que se armazene e transmita grandes quantidades de dados. A digitalização das quatro imagens de um único exame mamográfico com resolução adequada pode ocupar até 120MB de espaço em disco. Esta quantidade de dados leva a uma situação ainda mais crítica ao considerar-se o grande número de exames diários efetuados rotineiramente em uma clínica. Assim, técnicas eficientes de compressão de dados são necessárias para reduzir os custos relativos ao armazenamento e à transmissão destas imagens. O presente trabalho descreve o desenvolvimento de um sistema de alto desempenho para compressão sem perdas de imagens mamográficas baseado no algoritmo Prediction by Partial Matching (PPM), em conjunto com módulos para segmentação, mapeamento, codificação com Código Gray, decomposição em planos de bits e transformada move-to-front (MTF). O sistema desenvolvido mostrou-se eficiente tanto no que tange à razão de compressão quanto ao tempo de processamento, comprimindo imagens de 27MB em aproximadamente 13 segundos com razão de compressão média de 5,39.

Submitted by Lucienne Costa (lucienneferreira@ufcg.edu.br) on 2018-05-03T21:26:06Z No. of bitstreams: 1 FRANCISCO DANTAS NOBRE NETO – TESE (PPGCC) 2017.pdf: 3110801 bytes, checksum: e2803429a1a01abf91502c50bc0ea1df (MD5) / Made available in DSpace on 2018-05-03T21:26:06Z (GMT). No. of bitstreams: 1 FRANCISCO DANTAS NOBRE NETO – TESE (PPGCC) 2017.pdf: 3110801 bytes, checksum: e2803429a1a01abf91502c50bc0ea1df (MD5) Previous issue date: 2017-05 / Com a ampla difusão de smartphones equipados com dispositivos GPS (Global Positioning System), rastrear a localização de objetos (como pessoas e veículos) tem sido uma tarefa mais factível, resultando em novas oportunidades de pesquisas em variadas áreas do conhecimento. Dentre estas oportunidades, esta pesquisa lida com o desafio da área de previsão de rotas e destinos. Saber antecipadamente o destino de um usuário assim que ele inicia um deslocamento tem muitas utilidades práticas, tais como: indicar rotas menos congestionadas ou vias mais seguras, e sugerir a visita a algum ponto de interesse (POI) antes do destino almejado. Sistemas que fornecem previsão de rota e destino estão disponíveis comercialmente, no entanto, estes podem requerer interações constantes do usuário. Para deslocamentos diários, porém, a necessidade de uma interação frequente do usuário com um aplicativo pode tornar seu uso pouco prático e pouco ubíquo. Além disso, muitos trabalhos que apresentam modelos de previsão de rotas e destinos, disponíveis na literatura, não contemplam uma importante informação contextual, que é o papel que os lugares visitados representam para um usuário (por exemplo, se é sua casa ou seu local de trabalho). Não obstante, a maioria dos preditores disponíveis não possuem a funcionalidade de prever lugares nunca visitados. Esta tese de doutorado propõe uma família de métodos de predição baseada no algoritmo de compressão de dados Prediction by Partial Matching (PPM). Ainda com relação a esta pesquisa, é proposto um mecanismo capaz de identificar que uma rota em curso está sendo realizada pela primeira vez e, portanto, ter a possibilidade de prever um destino ainda não visitado. Neste estudo, também foram implementados outros preditores consolidados na literatura, que são as Cadeias de Markov e as Cadeias Ocultas de Markov, utilizados para comparação. É importante observar que ambos os preditores são capazes de prever apenas o destino de um trajeto, ao invés da rota restante. Nos experimentos realizados, foram utilizadas as métricas de Precisão, Recall e Medida-F (F1 Score), com validação cruzada (contendo 10 partições mutuamente exclusivas), para avaliação dos modelos de previsão implementados. A base de dados utilizada nesta pesquisa é composta por mais de 1.500 rotas, coletadas por aproximadamente três meses, referentes a 21 usuários. Os preditores baseados em PPM apresentaram resultados competitivos (ou superiores) comparados aos da literatura. / Thanks to the widely diffusion of smartphones with GPS devices natively embedded, the task of tracking object locations, such as people or vehicles, is more feasible nowadays, fostering new research opportunities. Among these new opportunities, this work addresses the challenge of route and destination prediction. Knowing in advance the destination where a user might reach as soon as he or she starts to move can be useful in various situations. For instance, to suggest to users less jammed or safer routes, as well to warn about points of interest located along their route. There are commercial systems capable of predicting destination and routes, however, these systems usually require frequent user interaction. Nonetheless, such a requirement could make the application unusable for daily routines. Moreover, most existing works do not consider an important contextual information: the information about the places that the users visit, i.e., the role that the places play to the user (for instance, if the place is home or work). In addition, most predictors described in the literature are not able to predict places that users have never visited. This thesis proposes a family of algorithms based on Prediction by Partial Matching (PPM). Furthermore, this work proposes a mechanism for identifying whether a route is being performed for the first time, resulting in the feasibility for predicting a never visited place. This research also provides a comparison between our proposed predictors, and the predictors based on Markov Models and Hidden Markov Models (HMM), which have been used in related works. It is important to mention that both Markov and HMM predictors that we implemented are able to predict just the destination, instead the remaining route. For the statistical assessment of the predictors, the metrics Precision, Recall and F1 Score are used, together with the process of 10-fold cross- validation. The database contains about 1,500 routes extracted from 21 users, gathered for three months. The predictors based on PPM performed similarly (or better) than others reported in the literature.

No description available.

Made available in DSpace on 2015-05-14T12:36:48Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 1280792 bytes, checksum: d335d67b212e054f48f0e8bca0798fe5 (MD5) Previous issue date: 2010-01-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Authorship attribution consists in categorizing an unknown document among some classes of authors previously selected. Knowledge about authorship of a text can be useful when it is required to detect plagiarism in any literary document or to properly give the credits to the author of a book. The most intuitive form of human analysis of a text is by selecting some characteristics that it has. The study of selecting attributes in any written document, such as average word length and vocabulary richness, is known as stylometry. For human analysis of an unknown text, the authorship discovery can take months, also becoming tiring activity. Some computational tools have the functionality of extracting such characteristics from the text, leaving the subjective analysis to the researcher. However, there are computational methods that, in addition to extract attributes, make the authorship attribution, based in the characteristics gathered in the text. Techniques such as neural network, decision tree and classification methods have been applied to this context and presented results that make them relevant to this question. This work presents a data compression method, Prediction by Partial Matching (PPM), as a solution of the authorship attribution problem of Brazilian literary works. The writers and works selected to compose the authors database were, mainly, by their representative in national literature. Besides, the availability of the books has also been considered. The PPM performs the authorship identification without any subjective interference in the text analysis. This method, also, does not make use of attributes presents in the text, differently of others methods. The correct classification rate obtained with PPM, in this work, was approximately 93%, while related works exposes a correct rate between 72% and 89%. In this work, was done, also, authorship attribution with SVM approach. For that, were selected attributes in the text divided in two groups, one word based and other in function-words frequency, obtaining a correct rate of 36,6% and 88,4%, respectively. / Atribuição de autoria consiste em categorizar um documento desconhecido dentre algumas classes de autores previamente selecionadas. Saber a autoria de um texto pode ser útil quando é necessário detectar plágio em alguma obra literária ou dar os devidos créditos ao autor de um livro. A forma mais intuitiva ao ser humano para se analisar um texto é selecionando algumas características que ele possui. O estudo de selecionar atributos em um documento escrito, como tamanho médio das palavras e riqueza vocabular, é conhecido como estilometria. Para análise humana de um texto desconhecido, descobrir a autoria pode demandar meses, além de se tornar uma tarefa cansativa. Algumas ferramentas computacionais têm a funcionalidade de extrair tais características do texto, deixando a análise subjetiva para o pesquisador. No entanto, existem métodos computacionais que, além de extrair atributos, atribuem a autoria baseado nas características colhidas ao longo do texto. Técnicas como redes neurais, árvores de decisão e métodos de classificação já foram aplicados neste contexto e apresentaram resultados que os tornam relevantes para tal questão. Este trabalho apresenta um método de compressão de dados, o Prediction by Partial Matching (PPM), para solução do problema de atribuição de autoria de obras da literatura brasileira. Os escritores e obras selecionados para compor o banco de autores se deram, principalmente, pela representatividade que possuem na literatura nacional. Além disso, a disponibilidade dos livros em formato eletrônico também foi considerada. O PPM realiza a identificação de autoria sem ter qualquer interferência subjetiva na análise do texto. Este método, também, não faz uso de atributos presentes ao longo do texto, diferentemente de outros métodos. A taxa de classificação correta alcançada com o PPM, neste trabalho, foi de aproximadamente 93%, enquanto que trabalhos relacionados mostram uma taxa de acerto entre 72% e 89%. Neste trabalho, também foi realizado atribuição de autoria com a abordagem SVM. Para isso, foram selecionados atributos no texto dividido em dois tipos, sendo um baseado em palavras e o outro na contagem de palavrasfunção, obtendo uma taxa de acerto de 36,6% e 88,4%, respectivamente.

Web cluster systems provide cost-effective solutions when scalable and reliable web services are required. However, as the number of servers in web cluster systems increase, web cluster systems incur long and unpredictable delays to manage servers. This study presents the efficient management schemes for web cluster systems. First of all, we propose an efficient request distribution scheme in web cluster systems. Distributor-based systems forward user requests to a balanced set of waiting servers in complete transparency to the users. The policy employed in forwarding requests from the frontend distributor to the backend servers plays an important role in the overall system performance. In this study, we present a proactive request distribution (ProRD) to provide an intelligent distribution at the distributor. Second, we propose the heuristic memory management schemes through a web prefetching scheme. For this study, we design a Double Prediction-by-Partial-Match Scheme (DPS) that can be adapted to the modern web frameworks. In addition, we present an Adaptive Rate Controller (ARC) to determine the prefetch rate depending on the memory status dynamically. For evaluating the prefetch gain in a server node, we implement an Apache module. Lastly, we design an adaptive web streaming system in wireless networks. The rapid growth of new wireless and mobile devices accessing the internet has contributed to a whole new level of heterogeneity in web streaming systems. Particularly, in-home networks have also increased in heterogeneity by using various devices such as laptops, cell phone and PDAs. In our study, a set-top box(STB) is the access pointer between the internet and a home network. We design an ActiveSTB which has a capability of buffering and quality adaptation based on the estimation for the available bandwidth in the wireless LAN.

Purpose of this thesis is to describe the context-based compression methods and their application to multimedia data. There is described the principle of arithmetic coding and prediction by partial matching method, including creation of the probability model. There are also described multimedia data and the basic principles of their compression. The next section presents compression methods, that I implemented at work and their results.

Made available in DSpace on 2015-05-14T12:36:26Z (GMT). No. of bitstreams: 1 parte1.pdf: 2704137 bytes, checksum: 1bc9cc5c3099359131fb11fa1878c22f (MD5) Previous issue date: 2010-08-31 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / This work analyzes methods for textures images classification and segmentation using lossless data compression algorithms models. Two data compression algorithms are evaluated: the Prediction by Partial Matching (PPM) and the Lempel-Ziv-Welch (LZW) that had been applied in textures classification in previous works. The textures are pre-processed using histogram equalization. The classification method is divided into two stages. In the learning stage or training, the compression algorithm builds statistical models for the horizontal and the vertical structures of each class. In the classification stage, samples of textures to be classified are compressed using models built in the learning stage, sweeping the samples horizontally and vertically. A sample is assigned to the class that obtains the highest average compression. The classifier tests were made using the Brodatz textures album. The classifiers were tested for various contexts sizes (in the PPM case), samples number and training sets. For some combinations of these parameters, the classifiers achieved 100% of correct classifications. Texture segmentation process was made only with the PPM. Initially, the horizontal models are created using eight textures samples of size 32 x 32 pixels for each class, with the PPM context of a maximum size 1. The images to be segmented are compressed by the models of classes, initially in blocks of size 64 x 64 pixels. If none of the models achieve a compression ratio at a predetermined interval, the block is divided into four blocks of size 32 x 32. The process is repeated until a model reach a compression ratio in the range of the compression ratios set for the size of the block in question. If the block get the 4 x 4 size it is classified as belonging to the class of the model that reached the highest compression ratio. / Este trabalho se propõe a analisar métodos de classificação e segmentação de texturas de imagens digitais usando algoritmos de compressão de dados sem perdas. Dois algoritmos de compressão são avaliados: o Prediction by Partial Matching (PPM) e o Lempel-Ziv-Welch (LZW), que já havia sido aplicado na classificação de texturas em trabalhos anteriores. As texturas são pré-processadas utilizando equalização de histograma. O método de classificação divide-se em duas etapas. Na etapa de aprendizagem, ou treinamento, o algoritmo de compressão constrói modelos estatísticos para as estruturas horizontal e vertical de cada classe. Na etapa de classificação, amostras de texturas a serem classificadas são comprimidas utilizando modelos construídos na etapa de aprendizagem, varrendo-se as amostras na horizontal e na vertical. Uma amostra é atribuída à classe que obtiver a maior compressão média. Os testes dos classificadores foram feitos utilizando o álbum de texturas de Brodatz. Os classificadores foram testados para vários tamanhos de contexto (no caso do PPM), amostras e conjuntos de treinamento. Para algumas das combinações desses parâmetros, os classificadores alcançaram 100% de classificações corretas. A segmentação de texturas foi realizada apenas com o PPM. Inicialmente, são criados os modelos horizontais usados no processo de segmentação, utilizando-se oito amostras de texturas de tamanho 32 x 32 pixels para cada classe, com o contexto PPM de tamanho máximo 1. As imagens a serem segmentadas são comprimidas utilizando-se os modelos das classes, inicialmente, em blocos de tamanho 64 x 64 pixels. Se nenhum dos modelos conseguir uma razão de compressão em um intervalo pré-definido, o bloco é dividido em quatro blocos de tamanho 32 x 32. O processo se repete até que algum modelo consiga uma razão de compressão no intervalo de razões de compressão definido para o tamanho do bloco em questão, podendo chegar a blocos de tamanho 4 x 4 quando o bloco é classificado como pertencente à classe do modelo que atingiu a maior taxa de compressão.

Traditionally, local shape descriptors or color and texture based descriptors are used to describe the content of images. Although, these solutions achieving good results, they are not able to distinguish scenes that contain objects with the same colors, but with a different spatial organization or do not supports partial matching. In this work we focus on a particular case of the partial matching that is to find individual objects in images that contain various objects. Since the color is one of the most visually distinguishable properties, we propose a new descriptor based only on color able to find pictures of objects that are contained in other images. Although our descriptor has shown better results when compared to related works, this new color descriptor is not able to discriminate objects topologically different but having the same colors. To overcome this problem, we also propose a new approach to the partial matching of images that combine color and topological features on a single descriptor. This new descriptor, first performs a simplification process of the original image, which identifies the color regions that make up the image. Then, we represent the spatial information among the color regions using a topological graph, where vertices represent the color regions and the edges represent the spatial connections between them. To calculate the descriptor from this graph representation, we use the spectral theory of graphs, avoiding the need to make a direct comparison between graphs. To support the partial matching, we propose a decomposition of the main graph into several subgraphs, and also calculate descriptors for these subgraphs. / Tradicionalmente, descritores de forma, ou descritores baseados em cor e textura, são utilizados para descrever o conteúdo visual das imagens. Embora essas abordagens apresentem bons resultados, elas não são capazes de diferenciar adequadamente imagens que contêm objetos com as mesmas cores, mas com organização espacial diferente ou não suportam a pesquisa parcial de imagens. Neste trabalho focamos em um caso particular da pesquisa parcial de imagens, que é encontrar objetos em imagens que contenham vários objetos, não deixando de lado a pesquisa total (encontrar imagens similares à original). Dado que a cor é uma das propriedades visuais mais discriminativas, propomos um novo descritor baseado somente em cor capaz de encontrar imagens de objetos que estão contidos em outras imagens. Embora tenha apresentado melhores resultados quando comparado a trabalhos correlatos, esse novo descritor de cor não é capaz de discriminar objetos topologicamente diferentes mas que possuam as mesmas cores. Com o intuito de resolver esse problema, também propomos uma nova abordagem para a recuperação parcial de imagens que combina características topológicas e de cor em um único descritor. Esse novo descritor primeiramente realiza um processo de simplificação da imagem original, onde são identificadas as regiões de cor que compõem a imagem. Após esse processo de simplificação, a organização espacial das regiões de cor previamente identificadas é representada por meio de um grafo topológico, onde os vértices representam as regiões de cor e as arestas representam as conexões entre essas regiões. O descritor topológico é então calculado a partir do grafo de topologia utilizando a teoria espectral de grafos, evitando a necessidade de se realizar uma comparação direta entre grafos. Para suportar a pesquisa parcial de imagens, é realizada uma decomposição do grafo principal em diversos subgrafos. / Mestre em Ciência da Computação

Submitted by Johnny Rodrigues (johnnyrodrigues@ufcg.edu.br) on 2018-08-03T19:45:39Z No. of bitstreams: 1 HIDELGARD PAULINO BARBOSA - DISSERTAÇÃO PPGCC 2013..pdf: 11966764 bytes, checksum: 077a69b5088eea2f7109e71871f4e57d (MD5) / Made available in DSpace on 2018-08-03T19:45:39Z (GMT). No. of bitstreams: 1 HIDELGARD PAULINO BARBOSA - DISSERTAÇÃO PPGCC 2013..pdf: 11966764 bytes, checksum: 077a69b5088eea2f7109e71871f4e57d (MD5) Previous issue date: 2013-08 / A voz é o meio de comunicação mais utilizado pelo ser humano. Porém, o sistema fonador humano é suscetível a diversos tipos de patologias que podem prejudicar a produção da voz e, consequentemente, a comunicação. Alguns tipos de exames têm sido utilizados para detectar estas patologias. Porém, eles apresentam desvantagens referentes à acurácia e ao conforto do paciente durante a aplicação, que podem desestimular a busca por tratamento. Por essa razão, técnicas computacionais têm sido empregadas com o intuito de detectar de modo confortável e preciso a presença e o tipo de patologia apresentada pelo sistema fonador. No entanto, os resultados obtidos ainda não possibilitam sua aplicação nas clínicas, principalmente pelo fato de ainda ser considerado um número reduzido de patologias. Visando a contornar esse problema, esta pesquisa propõe uma abordagem fundamentada em um método ainda não utilizado neste contexto: a Predição por Casamento Parcial (Prediction by Partial Matching - PPM), concebida originalmente com fins à compressão de dados. O modelo criado e mantido a partir deste método é alimentado com características acústicas, temporais e estatísticas extraídas dos sinais de voz e permite sua classificação no que se refere à identificação da presença e do tipo de patologia a um baixo custo computacional (velocidade e recursos de armazenamento). Foram obtidos resultados satisfatórios no tocante à presença de patologias. Quanto à discriminação de patologias, os resultados sugerem um potencial do método, embora a sua aplicação ainda necessite de investigações mais aprofundadas / Voice is the most widely used means of communication of mankind. However, speech organs are susceptible to several sort of pathologies, which may harm voice production and, therefore, communication. Several techniques have been used to detect these pathologies. However, they present drawbacks related to accuracy and comfort of patients during the application, which may discourage search for treatment. Thence, computational techniques have been used in order to detect the presence and type of speech pathology comfortably and accurately. But, results are still not good enough for its application in clinics, due to the fact it is considered a small number of distinct pathologies. Aiming to solve this problem, this research proposes using a method not previously employed in classification of vocal tract diseases: Prediction by Partial Matching (PPM), originally conceived for data compression purposes. The PPM model is fed with acoustical, temporal, and statistical features, ali of them extracted from voice signals. This method allowed a satisfactory classification, concerning presence and type of pathology while requiring a low computational cost (speed and storage resources). It were obtained satisfactory results regarding presence of speech pathologies. With regard to pathologies discrimination, the results suggest that this is a highly promising technique, although its application still needs deeper investigations.