With the extremely rapid development of the Internet in recent years, emerging peer-to-peer network overlays are meeting the requirements of a more sophisticated communications environment, providing a useful substrate for applications such as scalable file sharing, data storage, large-scale multicast, web-cache, and publish-subscribe services. Due to its design flexibility, peer-to-peer networks can offer features including self-organization, fault-tolerance, scalability, load-balancing, locality and anonymity. As the Internet grows, there is an urgent requirement to understand real-time network performance degradation. Measurement tools currently used are ping, traceroute and variations of these. SNMP (Simple Network Management Protocol) is also used by network administrators to monitor local networks. However, ping and traceroute can only be used temporarily, SNMP can only be deployed at certain points in networks and these tools are incapable of sharing network measurements among end-users. Due to the distributed nature of networking performance data, peer-to-peer overlay networks present an attractive platform to distribute this information among Internet users. This thesis aims at investigating the desirable locality property of peer-to-peer overlays to create an application to share Internet measurement performance. When measurement data are distributed amongst users, it needs to be localized in the network allowing users to retrieve it when external Internet links fail. Thus, network locality and robustness are the most desirable properties. Although some unstructured overlays also integrate locality in design, they fail to reach rarely located data items. Consequently, structured overlays are chosen because they can locate a rare data item deterministically and they can perform well during network failures. In structured peer-to-peer overlays, Tapestry, Pastry and Chord with proximity neighbour selection, were studied due to their explicit notion of locality. To differentiate the level of locality and resiliency in these protocols, P2Psim simulations were performed. The results show that Tapestry is the more suitable peer-to-peer substrate to build such an application due to its superior localizing data performance. Furthermore, due to the routing similarity between Tapestry and Pastry, an implementation that shares network measurement information was developed on freepastry, verifying the application feasibility. This project also contributes to the extension of P2Psim to integrate with GT-ITM and link failures.

abstract: K-Nearest-Neighbors (KNN) search is a fundamental problem in many application domains such as database and data mining, information retrieval, machine learning, pattern recognition and plagiarism detection. Locality sensitive hash (LSH) is so far the most practical approximate KNN search algorithm for high dimensional data. Algorithms such as Multi-Probe LSH and LSH-Forest improve upon the basic LSH algorithm by varying hash bucket size dynamically at query time, so these two algorithms can answer different KNN queries adaptively. However, these two algorithms need a data access post-processing step after candidates' collection in order to get the final answer to the KNN query. In this thesis, Multi-Probe LSH with data access post-processing (Multi-Probe LSH with DAPP) algorithm and LSH-Forest with data access post-processing (LSH-Forest with DAPP) algorithm are improved by replacing the costly data access post-processing (DAPP) step with a much faster histogram-based post-processing (HBPP). Two HBPP algorithms: LSH-Forest with HBPP and Multi- Probe LSH with HBPP are presented in this thesis, both of them achieve the three goals for KNN search in large scale high dimensional data set: high search quality, high time efficiency, high space efficiency. None of the previous KNN algorithms can achieve all three goals. More specifically, it is shown that HBPP algorithms can always achieve high search quality (as good as LSH-Forest with DAPP and Multi-Probe LSH with DAPP) with much less time cost (one to several orders of magnitude speedup) and same memory usage. It is also shown that with almost same time cost and memory usage, HBPP algorithms can always achieve better search quality than LSH-Forest with random pick (LSH-Forest with RP) and Multi-Probe LSH with random pick (Multi-Probe LSH with RP). Moreover, to achieve a very high search quality, Multi-Probe with HBPP is always a better choice than LSH-Forest with HBPP, regardless of the distribution, size and dimension number of the data set. / Dissertation/Thesis / M.S. Computer Science 2011

La hiérarchie mémoire des serveurs de calcul est de plus en plus complexe. Les machines disposent de plusieurs niveaux de caches plus ou moins partagés et d’une mémoire distribuée. Plus récemment le paysage du Calcul Haute Performance (CHP) a vu apparaître des mémoires adressables embarquées dans le processeur ainsi que de nouvelles mémoires non-volatiles (périphérique mémoire sur le bus d’entrées sorties et prochainement de la mémoire non-volatile directement sur le bus mémoire). Cette hiérarchie est nécessaire pour espérer obtenir de bonnes performances de calcul, au prix d’une gestion minutieuse du placement des données et des tâches de calcul. Là où la gestion des caches était entièrement matérielle et masquée au développeur, le choix du placement des données dans telle ou telle zone de mémoire, plus ou moins rapide, volatile ou non, volumineuse ou non, est maintenant paramétrable logiciellement. Cette nouvelle flexibilité donne une grande liberté aux développeurs mais elle complexifie surtout leur travail quand il s’agit de choisir les stratégies d’allocation, de communication, de placement, etc. En effet, les caractéristiques des nombreux niveaux de hiérarchie impliqués varient significativement en vitesse, taille et fonctionnalités. Dans cette thèse, co-encadrée entre Atos Bull Technologies et Inria Bordeaux– Sud-Ouest, nous détaillons la structure des plates-formes contemporaines et caractérisons la performance des accès à la mémoire selon plusieurs scénarios de localité des tâches de calcul et des données accédées. Nous expliquons comment la sémantique du langage de programmation impacte la localité des données dans la machine et donc la performance des applications. En collaboration avec le laboratoire INESC-ID de Lisbonne, nous proposons une extension au célèbre modèle Roofline pour exposer de manière intelligible les compromis de performance et de localité aux développeurs d’applications. Nous proposons par ailleurs un outil de synthèse de métriques de localité mettant en lien les évènements de performance de l’application et de la machine avec la topologie de cette dernière. Enfin, nous proposons une approche statistique pour sélectionner automatiquement la meilleure politique de placement des tâches de calcul sur les coeurs de la machine et des données sur les mémoires. / Through years, the complexity of High Performance Computing (HPC) systems’ memory hierarchy has increased. Nowadays, large scale machines typically embed several levels of caches and a distributed memory. Recently, on-chip memories and non-volatile PCIe based flash have entered the HPC landscape. This memory architecture is a necessary pain to obtain high performance, but at the cost of a thorough task and data placement. Hardware managed caches used to hide the tedious locality optimizations. Now, data locality, in local or remote memories, in fast or slow memory, in volatile or non-volatile memory, with small or wide capacity, is entirely software manageable. This extra flexibility grants more freedom to application designers but with the drawback of making their work more complex and expensive. Indeed, when managing tasks and data placement, one has to account for several complex trade-offs between memory performance, size and features. This thesis has been supervised between Atos Bull Technologies and Inria Bordeaux – Sud-Ouest. In the hereby document, we detail contemporary HPC systems and characterize machines performance for several locality scenarios. We explain how the programming language semantics affects data locality in the hardware, and thus applications performance. Through a joint work with the INESC-ID laboratory in Lisbon, we propose an insightful extension to the famous Roofline performance model in order to provide locality hints and improve applications performance. We also present a modeling framework to map platform and application performance events to the hardware topology, in order to extract synthetic locality metrics. Finally, we propose an automatic locality policy selector, on top of machine learning algorithms, to easily improve applications tasks and data placement.

Since their original introduction, strongly complementary observables have been a fundamental ingredient of the ZX calculus, one of the most successful fragments of Categorical Quantum Mechanics (CQM). In this thesis, we show that strong complementarity plays a vastly greater role in quantum theory. Firstly, we use strong complementarity to introduce dynamics and symmetries within the framework of CQM, which we also extend to infinite-dimensional separable Hilbert spaces: these were long-missing features, which open the way to a wealth of new applications. The coherent treatment presented in this work also provides a variety of novel insights into the dynamics and symmetries of quantum systems: examples include the extremely simple characterisation of symmetry-observable duality, the connection of strong complementarity with the Weyl Canonical Commutation Relations, the generalisations of Feynman's clock construction, the existence of time observables and the emergence of quantum clocks. Secondly, we show that strong complementarity is a key resource for quantum algorithms and protocols. We provide the first fully diagrammatic, theory-independent proof of correctness for the quantum algorithm solving the Hidden Subgroup Problem, and show that strong complementarity is the feature providing the quantum advantage. In quantum foundations, we use strong complementarity to derive the exact conditions relating non-locality to the structure of phase groups, within the context of Mermin-type non-locality arguments. Our non-locality results find further application to quantum cryptography, where we use them to define a quantum-classical secret sharing scheme with provable device-independent security guarantees. All in all, we argue that strong complementarity is a truly powerful and versatile building block for quantum theory and its applications, and one that should draw a lot more attention in the future.

This thesis is an attempt to better understand the inter-relationship between deprivation, locality and health. This study explores the views of different residents in St Ann s, a deprived neighbourhood in Nottingham, to find out how they make sense of their health. The thesis is based on some participant observation in the area but mainly draws on qualitative interviews with diverse residents in St Ann's: (including, in particular, working-class older adults of different ethnicities; some working-class parents with children; middle-class younger adults living in the area; and activists and professionals providing services to the area, such as volunteers running the food bank, the local priest and GPs. As I asked all of my participants questions about their lives and their health, as well as their perceptions of what health was like in St Ann s generally, I realised they did not mention what talk about things that I, or public health professionals, would expect them to i.e. whether they took regular exercise or ate fruits and vegetables. Rather than individual lifestyle choices , people mostly talked about places, doing rounds and routines. They also talked about other groups, which allegedly were less healthy than them. Further, different groups of people in the area spoke about health quite differently. It is these broader discussions and concerns, and differences between groups of people, that I make sense of throughout my thesis. I argue that existing quantitative research on health, deprivation and the physical environment typically focuses on how health varies across different neighbourhoods. Some of these studies examine how factors, such as the proximity of supermarkets or leisure facilitates, produce health inequalities. However, while I found residents in St Ann s mentioned the proximity of shops, I also found that health and place had broader meanings to people in terms of gathering together and structuring routines. Additionally, I found that different people had conflicting ideas about health, place and one another. Addressing health therefore needs to take these conflicts into consideration rather than implementing public health policy that mainly articulates the views and habits of the middle-class. I use concepts from Bourdieu (1979), such as habitus , field and symbolic violence to make sense of these conflicts, arguing that the reasons why people act as they do is beyond their cognitive and rational understanding. In circumstances such as those in St Ann's, where the working-class residents were most at home in their given social space where habitus meshes with field - their apprehension of their social environment is more practical than it is theoretical and more tacit than it is explicit. In other words, I argue that residents in St Ann s are curtailed by their habitus. Additionally, I argue that there is insufficient previous work which has acknowledged and validated the experiences of residents in deprived neighbourhoods. Residents may articulate deprivation and lack of understanding of what constitutes health, but they also draw attention to important issues that, whilst often mentioned in the literature (e.g. social cohesion and health), have not been sufficiently accounted for, such as the importance of sociability, community activities, amenities and services. Finally, it should be acknowledged that these issues are not equally or similarly important for all residents, so that middle-class residents are unlikely to mix with locals at the community centre for example and that also older and younger residents considered different places important. So, instead of accepting the premise inherent in much public health research that seeks to identify the barriers to change with individuals, there first needs to be a more rigorous examination of the practices and lifestyles of the working-class residents within deprived communities such as St Ann s. We should seek to understand that their current practices are important for their well-being and sense of community. However, and, at the same time, we should seek to identify appropriate approaches that can improve their health that does not only fit the middle-class agenda. A key element of this is to take the various elements of their practical, tacit knowledge more seriously as part of these conditions of possibility. Then, it may be possible to more fruitfully identify how and why such practices are created, and what might be the conditions of possibility for change.

The thesis titled "Health and social situation of people living in the excluded locality "Stalingrad", arose because nowadays they are socially excluded localities increasingly viewfinder researchers, scholars and not least the media. Residents of socially excluded localities get from their neighbors in most cases verbal abuse and an overall disinterest. Locations also receive various nicknames, such as "house of horror" or "gypsy ghetto". The theoretical part of the thesis describes and explains the basic concepts and phenomena that are the subject of the thesis. Such concepts and phenomena are eg. social exclusion and its effects on the lives of individuals affected, or causes of socially excluded localities and what people are at risk of social exclusion. Furthermore, the theoretical part describes the health situation of people living in socially excluded locality in general. There are presented the basic concepts that bind to a medical situation such as quality of life and determinants that affect health and condition. In the last part of the theoretical background is given governs employment and economic situation of the socially excluded locality, focusing on unemployment, work accidents and the impact of unemployment on health. The main aim of this thesis was to describe what health and social situation of people living in the excluded locality "Stalingrad" and the sub-objective was to determine what relationships are residents of the excluded localities "Stalingrad" with their neighbors who live near the site. Have been established two research questions were: VO1: What is the history of people living in the excluded locality "Stalingrad" in the health and social context? VO2: There is a relationship between social and health situation of people living in the Czech excluded locality "Stalingrad"? In the research part of the work is characterized by the research group, which consisted of two informants from socially excluded locality "Stalingrad" and three neighbors who live near that site. For data acquisition, qualitative and strategy to be exact, narrative interviews. Before beginning the interview informants were familiar to the interview and its course, and were satisfied that the talks are completely anonymous and will be used only for the purposes of this thesis. It was determined topic of conversation for people living in excluded locality "Stalingrad" I set the question "Tell me about your life in "Stalingrad" from the time you've moved up until now.". For people living close to the site was established topic question "Tell me about your relationship with the neighbors of "Stalingrad". Interviews were transcribed verbatim and then analyzed using open coding and axial coding. In the discussion of the information obtained is compared with the available literature and research. The results are that the health situation of these people of "Stalingrad" is hampered mainly because of the physically demanding work (work in the forest, in a construction company, car service). Health situation of the signed occupational injuries suffered by the informant and his friend. These injuries are undoubtedly permanently signed on the quality of life of these people. A potential threat to the health status of the moisture that gets into the homes destroyed because of the structure of the garage. The social situation is such that informant have due to high spending three jobs that have yet demanding working hours. Social situation affects the fact that residents of "Stalingrad" must commute to work, and that it must invest a larger sum of money to refurbishment of dwellings. In the past, there were some conflicts and problems with the adoption of the residents of "Stalingrad" in the village community. In the conclusion of thesis is mentioned possible use of this work. The work may be assisted by social workers or Roma coordinators in solving health and social situation of people living in the surveyed area.

This diploma thesis with the title ?Non-Romani inhabitants of socially excluded ?Romani? localities is divided into two parts: the theoretical and the empiric parts. The theoretical part of the diploma thesis deals mainly with defining the terms of social exclusion and socially excluded locality. At the same time, it describes the phenomenon of the poverty, underclass and white trash culture and ethnicity. The research part deals with the description of the actual research methodology, interpretation and the presentation of the research investigation results. The aim of the diploma thesis is to describe the perception of life in a socially excluded ?Romani? locality, by non-Romani inhabitants. With respect to the aim of the diploma thesis I chose the qualitative research strategy. The qualitative investigation was conducted by the method of questioning. The questioning technique was a semi-structured interview consisting of open questions. The target set consists of twelve respondents living in three excluded localities in the territory of the town of České Budějovice, who do not consider themselves, on the basis of self-identification, as members of the Romani ethnic group. The results of my research investigation shows what leads non-Romani inhabitants up to living in socially excluded localities, if they feel safely there and how they perceive coexistence with Romani ethnic group.

This diploma thesis is focused on identifying the image of excluded localities in media discourse. During the recent few years, the media have been forming the views of the majority population of the Roma minority, while the concept of social exclusion in the Czech Republic has been used most often in relation to the localities inhabited mostly by the members of the Roma minority. Excluded localities have become a very hot topic in the media and the media have been presenting excluded localities as problematic in terms of unemployment, poverty, maximum use of social welfare by their inhabitants, housing problems, crime, organized crime, disorder and problems with school attendance of the children.

As shared memory systems support terabyte-sized main memory, they provide an opportunity to perform efficient graph analytics on a single machine. Graph analytics is characterised by frequent synchronisation, which is addressed in part by shared memory systems. However, performance is limited by load imbalance and poor memory locality, which originate in the irregular structure of small-world graphs. This dissertation demonstrates how graph partitioning can be used to optimise (i) load balance, (ii) Non-Uniform Memory Access (NUMA) locality and (iii) temporal locality of graph partitioning in shared memory systems. The developed techniques are implemented in GraphGrind, a new shared memory graph analytics framework. At first, this dissertation shows that heuristic edge-balanced partitioning results in an imbalance in the number of vertices per partition. Thus, load imbalance exists between partitions, either for loops iterating over vertices, or for loops iterating over edges. To address this issue, this dissertation introduces a classification of algorithms to distinguish whether they algorithmically benefit from edge-balanced or vertex-balanced partitioning. This classification supports the adaptation of partitions to the characteristics of graph algorithms. Evaluation in GraphGrind, shows that this outperforms state-of-the-art graph analytics frameworks for shared memory including Ligra by 1.46x on average, and Polymer by 1.16x on average, using a variety of graph algorithms and datasets. Secondly, this dissertation demonstrates that increasing the number of graph partitions is effective to improve temporal locality due to smaller working sets. However, the increasing number of partitions results in vertex replication in some graph data structures. This dissertation resorts to using a graph layout that is immune to vertex replication and an automatic graph traversal algorithm that extends the previously established graph traversal heuristics to a 3-way graph layout choice is designed. This new algorithm furthermore depends upon the classification of graph algorithms introduced in the first part of the work. These techniques achieve an average speedup of 1.79x over Ligra and 1.42x over Polymer. Finally, this dissertation presents a graph ordering algorithm to challenge the widely accepted heuristic to balance the number of edges per partition and minimise edge or vertex cut. This algorithm balances the number of edges per partition as well as the number of unique destinations of those edges. It balances edges and vertices for graphs with a power-law degree distribution. Moreover, this dissertation shows that the performance of graph ordering depends upon the characteristics of graph analytics frameworks, such as NUMA-awareness. This graph ordering algorithm achieves an average speedup of 1.87x over Ligra and 1.51x over Polymer.

abstract: Similarity search in high-dimensional spaces is popular for applications like image processing, time series, and genome data. In higher dimensions, the phenomenon of curse of dimensionality kills the effectiveness of most of the index structures, giving way to approximate methods like Locality Sensitive Hashing (LSH), to answer similarity searches. In addition to range searches and k-nearest neighbor searches, there is a need to answer negative queries formed by excluded regions, in high-dimensional data. Though there have been a slew of variants of LSH to improve efficiency, reduce storage, and provide better accuracies, none of the techniques are capable of answering queries in the presence of excluded regions. This thesis provides a novel approach to handle such negative queries. This is achieved by creating a prefix based hierarchical index structure. First, the higher dimensional space is projected to a lower dimension space. Then, a one-dimensional ordering is developed, while retaining the hierarchical traits. The algorithm intelligently prunes the irrelevant candidates while answering queries in the presence of excluded regions. While naive LSH would need to filter out the negative query results from the main results, the new algorithm minimizes the need to fetch the redundant results in the first place. Experiment results show that this reduces post-processing cost thereby reducing the query processing time. / Dissertation/Thesis / Masters Thesis Computer Science 2016