O objetivo deste trabalho é avaliar a recuperação de imagem por conteúdo (CBIR - Content-based Image Retrieval) em uma rede de computadores, estabelecendo-se métricas de controle que otimizem a utilização da rede e ao mesmo tempo garanta melhor qualidade na resposta. Prevê-se a recuperação de imagens baseada em consulta por similaridade, combinando-se o extrator de características com a função de distância. O desenvolvimento é realizado em uma linguagem de programação independente da plataforma e de âmbito de internet, utilizado Java, desenvolvendo-se uma API (Application Programming Interface), visando, em especial, a reutilização de código, o que implica na diminuição do tempo de desenvolvimento. O trabalho demonstra a utilização de estruturas de indexação sequencial, comparada com a estrutura de indexação de árvore \"Slim-tree\". A principal contribuição deste trabalho é a análise e a utilização de métricas na rede de computadores em um projeto de CBIR. / The objective of this study is to evaluate the Content-based Image Retrieval (CBIR) in a computer network, establishing control metrics that optimize the use of network while ensuring better quality in the response. It is expected that images are going to be recovered based on queries that are similar, combining the features extractor with the distance function. The development environment is an independent language of the platform and of the Internet scope, using Java, that has developed an Application Programming Interfaces (API), aiming primarily the code reuse, which implies a decrease in the development time. This thesis demonstrates the use of sequential indexing structures compared to the tree index structure \"Slim-tree\". The main contribution of this thesis is the analysis and utilization of metrics in a computer network project in CBIR.

O objetivo deste trabalho é avaliar a recuperação de imagem por conteúdo (CBIR - Content-based Image Retrieval) em uma rede de computadores, estabelecendo-se métricas de controle que otimizem a utilização da rede e ao mesmo tempo garanta melhor qualidade na resposta. Prevê-se a recuperação de imagens baseada em consulta por similaridade, combinando-se o extrator de características com a função de distância. O desenvolvimento é realizado em uma linguagem de programação independente da plataforma e de âmbito de internet, utilizado Java, desenvolvendo-se uma API (Application Programming Interface), visando, em especial, a reutilização de código, o que implica na diminuição do tempo de desenvolvimento. O trabalho demonstra a utilização de estruturas de indexação sequencial, comparada com a estrutura de indexação de árvore \"Slim-tree\". A principal contribuição deste trabalho é a análise e a utilização de métricas na rede de computadores em um projeto de CBIR. / The objective of this study is to evaluate the Content-based Image Retrieval (CBIR) in a computer network, establishing control metrics that optimize the use of network while ensuring better quality in the response. It is expected that images are going to be recovered based on queries that are similar, combining the features extractor with the distance function. The development environment is an independent language of the platform and of the Internet scope, using Java, that has developed an Application Programming Interfaces (API), aiming primarily the code reuse, which implies a decrease in the development time. This thesis demonstrates the use of sequential indexing structures compared to the tree index structure \"Slim-tree\". The main contribution of this thesis is the analysis and utilization of metrics in a computer network project in CBIR.

O presente trabalho tem como objetivo principal analisar a morfogênese do ciberespaço fluminense a partir da investigação do processo de constituição da RedeRio de Computadores, rede acadêmica de cooperação científica, mantida pelo governo do estado do Rio de Janeiro. A escolha de uma rede acadêmica como objeto de estudo resulta do esforço em entender como as modernas tecnologias informacionais contribuem nos processos espaciais. Nesse sentido, nos foi possível constatar, em primeiro lugar, o papel decisivo da RedeRio na constituição do ciberespaço fluminense e brasileiro, visto que a rede regional fluminense foi um dos pilares de estruturação da Rede Nacional de Pesquisa (RNP). Em segundo lugar, verificamos que, ao longo de 14 anos, a rede manteve seu perfil de rede acadêmica, evidenciando a força de seu processo de constituição, voltando-se, mais recentemente, ao desenvolvimento de aplicativos compatíveis com transmissão em alta velocidade, como educação a distância e telemedicina. Por fim, observamos que a RedeRio de Computadores reforça a centralidade das áreas mais dinâmicas e importantes do município não promovendo, face a sua condição de rede informacional de educação, a superação dos históricos índices de exclusão. / The present work has as main objective to analyze the morphogenesis of the Rio de Janeiro state cyberspace from the inquiry of the process of constitution of RedeRio of Computers, academic network of scientific cooperation, kept by the Rio de Janeiro state government. The choice of an academic network as a study object results of the effort in understanding as the modern informational technologies contributes in the space processes. In this direction, in them it was possible to evidence, in first place, the decisive role of the RedeRio in the constitution process of the Rio de Janeiro state and Brazilian cyberspace, since the Rio de Janeiro state regional network was one of the pillars of structuring the National Network of Research (RNP). In according to place, we verify that, throughout 14 years, the network kept its profile of academic network, evidencing the force of its process of constitution, turning itself, more recently, to the development of applicatory compatible with transmission in high speed, as e-learning and telemedicine. Finally, we observe that, in contradiction to the waited one, the RedeRio of Computers strengthens the centrally of the important areas most dynamic and of the city not promoting, face its condition of informational network of education, the overcoming of the historical index of exclusion.

O presente trabalho tem como objetivo principal analisar a morfogênese do ciberespaço fluminense a partir da investigação do processo de constituição da RedeRio de Computadores, rede acadêmica de cooperação científica, mantida pelo governo do estado do Rio de Janeiro. A escolha de uma rede acadêmica como objeto de estudo resulta do esforço em entender como as modernas tecnologias informacionais contribuem nos processos espaciais. Nesse sentido, nos foi possível constatar, em primeiro lugar, o papel decisivo da RedeRio na constituição do ciberespaço fluminense e brasileiro, visto que a rede regional fluminense foi um dos pilares de estruturação da Rede Nacional de Pesquisa (RNP). Em segundo lugar, verificamos que, ao longo de 14 anos, a rede manteve seu perfil de rede acadêmica, evidenciando a força de seu processo de constituição, voltando-se, mais recentemente, ao desenvolvimento de aplicativos compatíveis com transmissão em alta velocidade, como educação a distância e telemedicina. Por fim, observamos que a RedeRio de Computadores reforça a centralidade das áreas mais dinâmicas e importantes do município não promovendo, face a sua condição de rede informacional de educação, a superação dos históricos índices de exclusão. / The present work has as main objective to analyze the morphogenesis of the Rio de Janeiro state cyberspace from the inquiry of the process of constitution of RedeRio of Computers, academic network of scientific cooperation, kept by the Rio de Janeiro state government. The choice of an academic network as a study object results of the effort in understanding as the modern informational technologies contributes in the space processes. In this direction, in them it was possible to evidence, in first place, the decisive role of the RedeRio in the constitution process of the Rio de Janeiro state and Brazilian cyberspace, since the Rio de Janeiro state regional network was one of the pillars of structuring the National Network of Research (RNP). In according to place, we verify that, throughout 14 years, the network kept its profile of academic network, evidencing the force of its process of constitution, turning itself, more recently, to the development of applicatory compatible with transmission in high speed, as e-learning and telemedicine. Finally, we observe that, in contradiction to the waited one, the RedeRio of Computers strengthens the centrally of the important areas most dynamic and of the city not promoting, face its condition of informational network of education, the overcoming of the historical index of exclusion.

Ces dernières années, les réseaux sont devenus une source importante d’informations dans différents domaines aussi variés que les sciences sociales, la physique ou les mathématiques. De plus, la taille de ces réseaux n’a cessé de grandir de manière conséquente. Ce constat a vu émerger de nouveaux défis, comme le besoin de mesures précises et intuitives pour caractériser et analyser ces réseaux de grandes tailles en un temps raisonnable.<p>La première partie de cette thèse introduit une nouvelle mesure de similarité entre deux noeuds d’un réseau dirigé et pondéré :la covariance “sum-over-paths”. Celle-ci a une interprétation claire et précise :en dénombrant tous les chemins possibles deux noeuds sont considérés comme fortement corrélés s’ils apparaissent souvent sur un même chemin – de préférence court. Cette mesure dépend d’une distribution de probabilités, définie sur l’ensemble infini dénombrable des chemins dans le graphe, obtenue en minimisant l'espérance du coût total entre toutes les paires de noeuds du graphe sachant que l'entropie relative totale injectée dans le réseau est fixée à priori. Le paramètre d’entropie permet de biaiser la distribution de probabilité sur un large spectre :allant de marches aléatoires naturelles où tous les chemins sont équiprobables à des marches biaisées en faveur des plus courts chemins. Cette mesure est alors appliquée à des problèmes de classification semi-supervisée sur des réseaux de taille moyennes et comparée à l’état de l’art.<p>La seconde partie de la thèse introduit trois nouveaux algorithmes de classification de noeuds en sein d’un large réseau dont les noeuds sont partiellement étiquetés. Ces algorithmes ont un temps de calcul linéaire en le nombre de noeuds, de classes et d’itérations, et peuvent dés lors être appliqués sur de larges réseaux. Ceux-ci ont obtenus des résultats compétitifs en comparaison à l’état de l’art sur le large réseaux de citations de brevets américains et sur huit autres jeux de données. De plus, durant la thèse, nous avons collecté un nouveau jeu de données, déjà mentionné :le réseau de citations de brevets américains. Ce jeu de données est maintenant disponible pour la communauté pour la réalisation de tests comparatifs.<p>La partie finale de cette thèse concerne la combinaison d’un graphe de citations avec les informations présentes sur ses noeuds. De manière empirique, nous avons montré que des données basées sur des citations fournissent de meilleurs résultats de classification que des données basées sur des contenus textuels. Toujours de manière empirique, nous avons également montré que combiner les différentes sources d’informations (contenu et citations) doit être considéré lors d’une tâche de classification de textes. Par exemple, lorsqu’il s’agit de catégoriser des articles de revues, s’aider d’un graphe de citations extrait au préalable peut améliorer considérablement les performances. Par contre, dans un autre contexte, quand il s’agit de directement classer les noeuds du réseau de citations, s’aider des informations présentes sur les noeuds n’améliora pas nécessairement les performances.<p>La théorie, les algorithmes et les applications présentés dans cette thèse fournissent des perspectives intéressantes dans différents domaines.<p><p><p>In recent years, networks have become a major data source in various fields ranging from social sciences to mathematical and physical sciences. Moreover, the size of available networks has grow substantially as well. This has brought with it a number of new challenges, like the need for precise and intuitive measures to characterize and analyze large scale networks in a reasonable time. <p>The first part of this thesis introduces a novel measure between two nodes of a weighted directed graph: The sum-over-paths covariance. It has a clear and intuitive interpretation: two nodes are considered as highly correlated if they often co-occur on the same -- preferably short -- paths. This measure depends on a probability distribution over the (usually infinite) countable set of paths through the graph which is obtained by minimizing the total expected cost between all pairs of nodes while fixing the total relative entropy spread in the graph. The entropy parameter allows to bias the probability distribution over a wide spectrum: going from natural random walks (where all paths are equiprobable) to walks biased towards shortest-paths. This measure is then applied to semi-supervised classification problems on medium-size networks and compared to state-of-the-art techniques.<p>The second part introduces three novel algorithms for within-network classification in large-scale networks, i.e. classification of nodes in partially labeled graphs. The algorithms have a linear computing time in the number of edges, classes and steps and hence can be applied to large scale networks. They obtained competitive results in comparison to state-of-the-art technics on the large scale U.S.~patents citation network and on eight other data sets. Furthermore, during the thesis, we collected a novel benchmark data set: the U.S.~patents citation network. This data set is now available to the community for benchmarks purposes. <p>The final part of the thesis concerns the combination of a citation graph with information on its nodes. We show that citation-based data provide better results for classification than content-based data. We also show empirically that combining both sources of information (content-based and citation-based) should be considered when facing a text categorization problem. For instance, while classifying journal papers, considering to extract an external citation graph may considerably boost the performance. However, in another context, when we have to directly classify the network citation nodes, then the help of features on nodes will not improve the results.<p>The theory, algorithms and applications presented in this thesis provide interesting perspectives in various fields.<p> / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed.<p><p>We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time.<p><p>We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results.<p><p>After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances.<p><p>Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them.<p><p>Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case.<p><p>------------------------------------------------<p><p>Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits.<p><p>Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes.<p><p>Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3.<p><p>Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème.<p><p>Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas. <p> / Doctorat en sciences, Spécialisation Informatique / info:eu-repo/semantics/nonPublished