Power Laws são leis estatísticas que permeiam os mais variados campos do conhecimento humano tais como Biologia, Sociologia, Geografia, Linguística, Astronomia, entre outros, e que têm como característica mais importante a disparidade entre os elementos causadores, ou seja, alguns poucos elementos são responsáveis pela grande maioria dos efeitos. Exemplos famosos são o Princípio de Pareto, a Lei de Zipf e o modelo de Incêndios Florestais. O Princípio de Pareto diz que 80% da riqueza de uma nação está nas mãos de apenas 20% da população; em outras palavras, uma relação causa e efeito chamada 80-20. A Lei de Zipf enuncia que o comportamento da frequência versus o ranking de ocorrência é dado por uma curva hiperbólica com um comportamento semelhante a 1/x. O modelo de Incêndios Florestais modela o comportamento do crescimento de árvores em uma floresta entre sucessivas queimadas que causam destruição de agrupamentos de árvores. As Power Laws demonstram que uma porcentagem pequena de uma distribuição tem uma alta frequência de ocorrência, enquanto o restante dos casos que aparecem tem uma frequência baixa, o que levaria a uma reta decrescente em uma escala logarítmica. A partir de simulações utilizando o conjunto de benchmarks SPEC-CPU2000, este estudo procura investigar como essas leis estatísticas podem ser utilizadas para entender e melhorar o desempenho de caches baseados em diferentes políticas de substituição de linhas de cache. O estudo sobre a possibilidade de uma nova política de substituição composta por um cache Pareto, bem como um novo mecanismo de chaveamento do comportamento de algoritmos adaptativos de substituição de linhas de cache, chamado de Forest Fire Switching Mechanism, ambos baseados em Power Laws, são propostos a fim de se obter ganhos de desempenho na execução de aplicações. / Power Laws are statistical laws that permeate the most varied fields of human knowledge such as Biology, Sociology, Geography, Linguistics, Astronomy, among others, and have as most important characteristic the disparity between the cause events, in other words, some few elements are responsible for most of the effects. Famous examples are the Pareto Principle, the Zipfs Law and the Forest Fire model. The Pareto Principle says that 80% of a nations wealth is in the hands of just 20% of the population; in other words, a cause and effect relationship called 80-20. Zipf\'s Law states that the behavior of frequency versus ranking of occurrence is given by a hyperbolic curve with a behavior similar to 1/x. The Forest Fire model represents the behavior of trees growing in a forest between successive fires that cause the destruction of clusters of trees. The Power Laws demonstrate that a small percentage of a distribution has a high frequency of occurrence, while the rest of the cases that appear have a low frequency, which would take to a decreasing line in a logarithmic scale. Based on simulations using the SPEC-CPU2000 benchmarks, this work seeks to investigate how these distributions can be used in order to understand and improve the performance of caches based on different cache line replacement policies. The study about the possibility of a new replacement policy composed by a Pareto cache, and a new switching mechanism of the behavior of cache line replacement adaptive algorithms, called Forest Fire Switching Mechanism, both based on Power Laws, are proposed in order to obtain performance gains on the execution of applications.

Power Laws são leis estatísticas que permeiam os mais variados campos do conhecimento humano tais como Biologia, Sociologia, Geografia, Linguística, Astronomia, entre outros, e que têm como característica mais importante a disparidade entre os elementos causadores, ou seja, alguns poucos elementos são responsáveis pela grande maioria dos efeitos. Exemplos famosos são o Princípio de Pareto, a Lei de Zipf e o modelo de Incêndios Florestais. O Princípio de Pareto diz que 80% da riqueza de uma nação está nas mãos de apenas 20% da população; em outras palavras, uma relação causa e efeito chamada 80-20. A Lei de Zipf enuncia que o comportamento da frequência versus o ranking de ocorrência é dado por uma curva hiperbólica com um comportamento semelhante a 1/x. O modelo de Incêndios Florestais modela o comportamento do crescimento de árvores em uma floresta entre sucessivas queimadas que causam destruição de agrupamentos de árvores. As Power Laws demonstram que uma porcentagem pequena de uma distribuição tem uma alta frequência de ocorrência, enquanto o restante dos casos que aparecem tem uma frequência baixa, o que levaria a uma reta decrescente em uma escala logarítmica. A partir de simulações utilizando o conjunto de benchmarks SPEC-CPU2000, este estudo procura investigar como essas leis estatísticas podem ser utilizadas para entender e melhorar o desempenho de caches baseados em diferentes políticas de substituição de linhas de cache. O estudo sobre a possibilidade de uma nova política de substituição composta por um cache Pareto, bem como um novo mecanismo de chaveamento do comportamento de algoritmos adaptativos de substituição de linhas de cache, chamado de Forest Fire Switching Mechanism, ambos baseados em Power Laws, são propostos a fim de se obter ganhos de desempenho na execução de aplicações. / Power Laws are statistical laws that permeate the most varied fields of human knowledge such as Biology, Sociology, Geography, Linguistics, Astronomy, among others, and have as most important characteristic the disparity between the cause events, in other words, some few elements are responsible for most of the effects. Famous examples are the Pareto Principle, the Zipfs Law and the Forest Fire model. The Pareto Principle says that 80% of a nations wealth is in the hands of just 20% of the population; in other words, a cause and effect relationship called 80-20. Zipf\'s Law states that the behavior of frequency versus ranking of occurrence is given by a hyperbolic curve with a behavior similar to 1/x. The Forest Fire model represents the behavior of trees growing in a forest between successive fires that cause the destruction of clusters of trees. The Power Laws demonstrate that a small percentage of a distribution has a high frequency of occurrence, while the rest of the cases that appear have a low frequency, which would take to a decreasing line in a logarithmic scale. Based on simulations using the SPEC-CPU2000 benchmarks, this work seeks to investigate how these distributions can be used in order to understand and improve the performance of caches based on different cache line replacement policies. The study about the possibility of a new replacement policy composed by a Pareto cache, and a new switching mechanism of the behavior of cache line replacement adaptive algorithms, called Forest Fire Switching Mechanism, both based on Power Laws, are proposed in order to obtain performance gains on the execution of applications.

Cette thèse propose d’étudier l’évolution des hiérarchies des villes et de la croissance urbaine en s’appuyant sur le cas du Maroc. Le Maroc a connu ces dernières décennies un processus d’urbanisation soutenu, tant dans les grandes villes que dans les petites et moyennes villes. D’où la nécessité de procéder à une structuration démographique urbaine primatiale qui exige une coordination entre certaines politiques économiques nationales et les politiques d’aménagement menées par les grandes métropoles afin de faire preuve d’une réelle efficacité. Une politique d’aménagement résolument tournée jusqu’ici vers la gestion de la pression urbaine dans les grandes métropoles. Ce qui a conduit par conséquent à une polarisation des activités dans quelques régions du territoire. Ainsi, cette thèse se structure autour de trois chapitres. Le premier chapitre examine la loi rang-taille et l’apport des économistes et des géographes dans ce processus. Le second chapitre analyse les trois approches théoriques qui traitent la question de la croissance urbaine notamment les théories de la croissance aléatoire, de la croissance déterministe et l’intersection de ces deux approches dites d’hybrides. Enfin, le dernier chapitre est basé sur une étude empirique à l’échelle régionale afin de recenser les déterminants de la croissance urbaine des régions marocaine. Le travail engagé dans cette thèse s’appuie sur des bases de données originales fournies par le Haut-Commissariat au Plan permettant de recenser la taille des agglomérations marocaines et utilise un ensemble d’instruments statistiques et économétriques. Les différents résultats obtenus s’inscrivent dans le prolongement de différentes études effectuées en sciences régionales. Ces résultats indiquent que les hiérarchies urbaines marocaines sont appelées à changer dans les décennies à venir, mais également que la croissance économique des régions du Maroc n’affecte pas immédiatement la croissance de la population urbaine. / This thesis proposes to study the evolution of city hierarchies and urban growth based on the case of Morocco. This country has experienced in recent decades a sustained urbanization process, both in large cities and small and medium-sized cities. Hence the need to proceed to a primatial urban demographic structure that requires coordination between certain national economic policies and planning policies carried out by major cities to be truly effective. A development policy resolutely turned so far towards the management of urban pressure in major cities. This led to a polarization of activities in some regions of the territory. Thus, this thesis is divided into three chapters. The first chapter examines the rank-size law and the contribution of economists and geographers in this process. The second chapter analyzes the three theoretical approaches that deal with the issue of urban growth, in particular theories of random growth, deterministic growth and the intersection of these two approaches, called hybrid. Finally, the last chapter is based on an empirical study at the regional level to identify the determinants of urban growth in Moroccan regions. The work undertaken in this thesis is based on original databases provided by the Office of the “Haut-Commissariat au Plan” to identify the size of Moroccan agglomerations and uses a set of statistical and econometric instruments. The various results obtained are a continuation of various studies carried out in regional sciences. These results indicate that Moroccan urban hierarchies are destined to change in the decades to come, but also that the economic growth of the regions of Morocco does not immediately affect the growth of the urban population.

La recuperación de documentos similares a un documento dado en la Web, es un problema no resuelto por los motores de búsqueda tradicionales. Esto se debe, a que los motores de búsqueda están pensados para resolver necesidades de información de usuarios basadas en conjuntos pequeños de términos clave. En este trabajo, se define el problema de recuperación de documentos similares como el proceso en que un usuario ingresa un párrafo a un sistema de información y éste le retorna los documentos con mayor similitud a éste en la Web. Los documentos recuperados son rankeados por medio de una métrica de similitud estimada por el sistema. La resolución del problema, podría ser utilizado en contextos como la detección de plagio, el análisis de impacto de documentos en la Web y la recuperación de ideas similares. Se propone una metodología basada en modelos de lenguaje generativos y metabuscadores. Los modelos de lenguaje son utilizados como generadores de consultas aleatorizadas sobre el texto del documento entregado, donde se propone un modelo que extrae términos relevantes sin reposición llamado Modelo de Lenguaje Hipergeométrico. El conjunto de consultas generado intenta ser una representación de la información relevante del documento. Posteriormente, cada consulta es enviada como entrada a una lista de motores de búsqueda de la Web. Para luego combinar los resultados de cada búsqueda en una única respuesta. A este proceso se le conoce como metabúsqueda. Finalmente, los resultados son ordenados por relevancia y presentados al usuario. Para estimar la relevancia entre el documento de entrada y los documentos encontrados se propone una función de scoring basada en la ley de Zipf, la cual considera los rankings locales de aparición de cada resultado, la confianza en los motores de búsqueda utilizados y la cantidad instancias de búsqueda en que éstos son recuperados. Se definen los requerimientos de software junto a un análisis preliminar de las características de éste donde se define una arquitectura basada en capas. La capa de aplicación de la herramienta es diseñada acorde a una arquitectura orientada a servicios, de manera que pueda interoperar con otros sistemas. La herramienta se diseña en base al paradigma de orientación a objetos y el uso patrones de diseño conocidos. Esto se realiza para permitir la mantenibilidad y extensibilidad del modelo al uso de diversas estrategias para la generación de consultas, rankeo de resultados y para permitir al metabuscador hacer uso de diversos motores de búsqueda externos. La capa de interfaz se diseña como una interfaz Web donde el usuario ingresa el párrafo dentro de un cuadro de texto, permitiéndole a éste además, evaluar la calidad de los resultados entregados. Los resultados son registrados dentro de la capa de datos, para poder evaluar continuamente la calidad predictiva del modelo al adaptar sus parámetros al conocimiento entregado por los usuarios. Una vez implementada la herramienta, se realiza una serie de experimentos basados en métricas de recuperación de información para evaluar la calidad del modelo en la herramienta implementada. Se obtiene una precisión de 0.87 para los primeros resultados recuperados al evaluar la relevancia de 2400 documentos recuperados sobre una muestra de 160 párrafos entregados como entrada al sistema. Además, se valida que la combinación de varios motores de búsquedas mejora la precisión del modelo, al ampliar la cobertura de la Web. Finalmente, se evalúan la calidad del diseño y la implementación del software. Para el caso del diseño de software la evaluación se realiza en base a métricas de orientación a objetos, y para el caso de la implementación se evalúan la funcionalidad y el rendimiento en base a casos de pruebas. En ambos casos, los resultados obtenidos comprueban la extensibilidad y mantenibilidad del diseño junto al cumplimiento de los requerimientos funcionales y no funcionales establecidos.

Fantasy literature has a rather strong position in countries with an English-speaking population but not in Sweden. The supply of fantasy in Sweden is much smaller than that in for example United Kingdom. Does this affect the Swedish readers of this genre? If it does, how does it affect them? The aim of this thesis is to find out how a few fantasy-reading students at the Swedish School of Library and Information Science get hold of the fiction they want to read and who and/or what influence their decision of which book to read. In order to avoid confusion we are also going to try to find out how they define fantasy since it varies from person to person what is included in the genre. To get a result we interviewed eight students using the method of qualitative interviews. Then we analyzed the result using George Kingsley Zipf’s principle of least effort, the theory of the economic man and Patrick Wilson’s cognitive authority. The result show that almost all of the students have the same definition of fantasy and uses different ways to get hold of fantasy compared to how they get hold of other kinds of fiction. It also shows that most of them have different influences when choosing a book in the genre of fantasy and when choosing a book from a different genre. / Uppsatsnivå: D

Submitted by Suethene Souza (suethene.souza@ufpe.br) on 2015-03-13T17:41:46Z No. of bitstreams: 2 TESE Diego Firmino da Silva.pdf: 3130241 bytes, checksum: e7b2cd66fd0da5d77dedd1c9bcf818c8 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) / Made available in DSpace on 2015-03-13T17:41:46Z (GMT). No. of bitstreams: 2 TESE Diego Firmino da Silva.pdf: 3130241 bytes, checksum: e7b2cd66fd0da5d77dedd1c9bcf818c8 (MD5) license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) Previous issue date: 2014-03-13 / Esta tese tem como foco principal a dinâmica populacional brasileira entre 1970 e 2010. Neste sentido, o primeiro objetivo é explorar o comportamento da distribuição populacional, utilizando tanto a abordagem tradicional de rank quanto as cadeias de Markov. A fim de obter informações mais precisas sobre a dinâmica e a evolução da distribuição populacional, a dependência espacial é introduzida através da análise de LISA Markov e Spatial Markov Chains. O formato da distribuição indica que a divergência no tamanho populacional das Áreas Mínimas Comparáveis (AMC) é decrescente. A estimação da lei de Zipf traz evidências de que a distribuição populacional está, a cada década, de distanciando da distribuição de Pareto. A abordagem utilizando as cadeias de Markov traz como principais evidências a alta persistência das AMCs permanecerem nas suas classes iniciais com o passar das décadas e o fenômeno que diferentes contextos espaciais tem efeitos diferentes sobre a transição das localidades. O segundo e principal objetivo da tese é modelar a dinâmica do crescimento populacional das AMCs brasileiras a fim de avaliar os determinantes do crescimento populacional destas unidades entre 1970 e 2010, bem como examinar a existência e magnitude da interação espacial e dos efeitos de spillovers espaciais associados a estes determinantes. Neste sentido, o modelo de crescimento populacional desenvolvido por Glaeser et al (1995) e Glaeser (2008) é ampliado para incluir efeitos de interações espaciais. Este modelo é, então, testado empiricamente através da estimação de um modelo espacial dinâmico com dados em painel incluindo efeitos fixos e comparando a performance de uma ampla gama de matrizes de vizinhança através de modelos Bayesianos de probabilidade posterior. Seis dos treze determinantes do crescimento populacional considerados nesta tese apresentaram efeitos de interação espacial significantes. Isto implica que uma mudança em uma destas variáveis de uma unidade também afeta significantemente o crescimento populacional nas unidades vizinhas, um efeito que tem sido ignorado na maiorias dos estudos anteriores a este.

Tropical Cyclones are a continuing threat to life and property. Willoughby (2012) found that a Pareto (power-law) cumulative distribution fitted to the most damaging 10% of US hurricane seasons fit their impacts well. Here, we find that damage follows a Pareto distribution because the assets at hazard follow a Zipf distribution, which can be thought of as a Pareto distribution with exponent 1. The Z-CAT model is an idealized hurricane catastrophe model that represents a coastline where populated places with Zipf- distributed assets are randomly scattered and damaged by virtual hurricanes with sizes and intensities generated through a Monte-Carlo process. Results produce realistic Pareto exponents. The ability of the Z-CAT model to simulate different climate scenarios allowed testing of sensitivities to Maximum Potential Intensity, landfall rates and building structure vulnerability. The Z-CAT model results demonstrate that a statistical significant difference in damage is found when only changes in the parameters create a doubling of damage.

This master thesis contains three independent papers on the Zip's law for cities. In the first essay I summarize accumulated knowledge and use examples from the Czech Republic to show problems of the empirical research. The main findings of this essay are: City size distribution in the Czech Republic can be better described by a log-normal distribution than by a Pareto distribution; Pareto exponents are sensitive to sample selection. The second essay is the largest empirical cross-country study on Zipf's law for cites. The mean value for 157 countries is 0.919. The comparison with the study by Soo (2005) showed a decreasing tendency of the Pareto exponent, since for the same countries, the average exponent decreased from 1.11 to 1.02. One possible explanation of this trend is the process of urbanization. The last essay looks at the topic from a different angle. I have developed an agent based model to describe the process of suburbanization and cities merging and its impact on the size of the Pareto exponent. I have shown that when cities merge, the exponent starts to fall down from a steady state.

<div>In the past decade, Big Data analysis has become a central part of many industries including entertainment, social networking, and online commerce. MapReduce, pioneered by Google, is a popular programming model for Big Data analysis, famous for its easy programmability due to automatic data partitioning, fault tolerance, and high performance. Majority of MapReduce workloads are summarizations, where the final output is a per-key ``reduced" version of the input, highlighting a shared property of each key in the input dataset.</div><div><br></div><div>While MapReduce was originally proposed for massive data analyses on networked clusters, the model is also applicable to datasets small enough to be analyzed on a single server. In this single-server context the intermediate tuple state generated by mappers is saved to memory, and only after all Map tasks have finished are reducers allowed to process it. This Map-then-Reduce sequential mode of execution leads to distant reuse of the intermediate state, resulting in poor locality for memory accesses. In addition the size of the intermediate state is often too large to fit in the on-chip caches, leading to numerous cache misses as the state grows during execution, further degrading performance. It is well known, however, that many large datasets used in these workloads possess a Zipfian/Power Law skew, where a minority of keys (e.g., 10\%) appear in a majority of tuples/records (e.g., 70\%). </div><div><br></div><div>I propose ZipThru, a novel MapReduce software architecture that exploits this skew to keep the tuples for the popular keys on-chip, processing them on the fly and thus improving reuse of their intermediate state and curtailing off-chip misses. ZipThru achieves this using four key mechanisms: 1) Concurrent execution of both Map and Reduce phases; 2) Holding only the small, reduced state of the minority of popular keys on-chip during execution; 3) Using a lookup table built from pre-processing a subset of the input to distinguish between popular and unpopular keys; and 4) Load balancing the concurrently executing Map and Reduce phases to efficiently share on-chip resources. </div><div><br></div><div>Evaluations using Phoenix, a shared-memory MapReduce implementation, on 16- and 32-core servers reveal that ZipThru incurs 72\% fewer cache misses on average over traditional MapReduce while achieving average speedups of 2.75x and 1.73x on both machines respectively.</div>

Nous nous interrogeons, dans le cadre de la NEG, sur la validité empirique d'un certain nombre de grands facteurs explicatifs de la répartition spatiale des activités (le coût du travail local, les coûts de la concurrence, localisation de la demande finale, le coût de transport etc). Nos résultats, trouvés à l'aide de différentes simulations dans un contexte de processus d'intégration régionale au sein des PVD, suggèrent que les firmes semblent réaliser un arbitrage entre s'agglomérer pour bénéficier de rendements croissants dus à l'effet taille du marché et se disperser pour bénéficier des coûts du travail plus faibles. Nous modélisons, en particulier, l'avantage des régions côtières par rapport aux régions intérieures dans le commerce avec le reste du monde. Ce constat est particulièrement vrai dans le bassin méditerranéen qui est caractérisé par une littoralisation excessive de l'activité économique et démographique. Il apparaît qu'au-delà des politiques d'ouverture internationale mises en évidence par Krugman et Elizondo (1996), la dotation régionale en terme d'infrastructures de transport a un impact certain sur le degré et l'efficacité de la concentration spatiale au sein des PVD. Le second grand enseignement de cette étude est que la tendance au redéploiement des activités des grands pôles urbains vers les zones de moindre densité se confirme avec la considération des forces centrifuges. En effet, cette extension influence directement la fonction de production des firmes et conduit à une répartition plus égale de l'activité économique entre deux régions. De ce fait, les possibilités d'équilibres de long terme sont plus larges avec la prise en compte des coûts de congestion.