The approximate nearest neighbor(ANN) search over high dimensional data has become an unavoidable service for online applications. Fast and high-quality results of unknown queries are the largest challenge that most algorithms faced with. Locality Sensitive Hashing(LSH) is a well-known ANN search algorithm while suffers from inefficient index structure, poor accuracy in distributed scheme. The traditional index structures have most significant bits(MSB) problem, which is their indexing strategies have an implicit assumption that the bits from one direction in the hash value have higher priority. In this thesis, we propose a new content-based index called Random Draw Forest(RDF), which not only uses an adaptive tree structure by applying the dynamic length of compound hash functions to meet the different cardinality of data, but also applies the shuffling permutations to solve the MSB problem in the traditional LSH-based index. To raise the accuracy in the distributed scheme, we design a variable steps lookup strategy to search the multiple step sub-indexes which are most likely to hold the mistakenly partitioned similar objects. By analyzing the index, we show that RDF has a higher probability to retrieve the similar objects compare to the original index structure. In the experiment, we first learn the performance of different hash functions, then we show the effect of parameters in RDF and the performance of RDF compared with other LSH-based methods to meet the ANN search. / Thesis / Master of Science (MSc)

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-06-29T11:57:33Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) template.pdf: 1023711 bytes, checksum: bb469b82eb53b63f6e13f942f61ae867 (MD5) / Made available in DSpace on 2016-06-29T11:57:33Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) template.pdf: 1023711 bytes, checksum: bb469b82eb53b63f6e13f942f61ae867 (MD5) Previous issue date: 2014-08-14 / CNPq / As fun c~oes de Bell s~ao conhecidas pelo papel central desempenhado na caracteriza c~ao da n~ao localidade da teoria qu^antica. Usualmente s~ao empregadas na quanti ca c~ao do grau de n~ao localidade de sistemas qu^anticos espec cos atrav es do calculo do seu valor m aximo entre todos os poss veis estados e con gura c~oes associadas aos detectores. No entanto, embora dois estados qu^anticos tenham diferentes \densidades de con gura c~ao n~ao local"( Estados com diferentes contribui c~oes de con gura c~oes associadas aos detectores que geram n~ao localidade), se eles possuem o mesmo valor do m aximo da fun c~ao de Bell, ent~ao s~ao considerados igualmente n~ao locais. Usando este crit erio, Ac n et al. (Phys. Rev. A 65, 052325, 2002) encontraram que para qunits (Estados de sistemas qu^anticos conjuntos d-dimensionais), o estado maximamente emaranhado n~ao corresponde ao estado maximamente n~ao local, fato que e considerado como uma anomalia da n~ao localidade da teoria qu^antica (M ethot & Scarani; Quant. Inf. Comput. 7, 157, 2008). A m de resolver o problema da anomalia, nesta disserta c~ao e proposta uma medida do grau de n~ao localidade, na qual s~ao tomadas em conta todas as contribui c~oes de con- gura c~oes dos detectores que geram n~ao localidade do estado. Tal medida e proporcional a integral da fun c~ao de Bell na regi~ao de viola c~ao, no espa co dos par^ametros que caracterizam as con gura c~oes (Em geral ^angulos relativos entre orienta c~oes dos detectores). Foi calculado o grau de n~ao localidade de v arios sistemas de dois e tr^es n veis, com e sem uma contribui c~ao de ru do qu^antico ao estado, usando tr^es tipos de desigualdades de Bell: A desigualdade na vers~ao original, a desigualdade CHSH e a desigualdade GCLMP (Ac n et al. 2002). Em todos os casos estudados foi observada concond^ancia entre o estado maximamente emaranhado e o estado maximamente n~ao local, resolvendo assim o problema da anomalia da n~ao localidade. / Bell functions are known by the central role played on the characterization of non-locality in quantum theory. They are often used in the quanti cation of the non-locality strength for speci c quantum systems by calculating their maximum among all possible states and detector's con gurations. However, even if two quantum states present di erent \nonlocal density con gurations"(States with di erent contributions of detector con gurations that generate non-locality), if these display the same value for the maximum of Bell function, then they are considered equally non-local. Making use of this criteria, Ac n et al. (Phys. Rev. A 65, 052325, 2002) found that for qunits (Joint states of d-dimensional quantum systems), the maximally entangled state does not match with the maximally non-local state, this is known as an anomaly of quantum non-locality (M ethot & Scarani; Quant. Inf. Comput. 7, 157, 2008). In order to solve the anomaly problem, in this dissertation it is proposed a nonlocality strength measure in which the whole contributions of detector's con gurations that give rise to non-locality are taken into account. Such a measure is proportional to the Bell function integration over the violation region on the space of the parameters that characterize the detector's con guration (Usually, relative angles between orientations of detectors). The non-locality strength was calculated for several two and three-level bipartite systems, with and without a contribution of white noise to the whole state of the system, by using three kinds of Bell inequalities: Bell inequality in its original version, CHSH inequality and GCLMP inequality (Ac n et al. 2002). In all the cases, it was observed agreement between maximally entangled states and maximally non-local ones, thus solving the problem of anomaly of non-locality.

Recent years have witnessed the emergence of microprocessors that are embedded within a plethora of devices used in everyday life. Embedded architectures are customized through a meticulous and time consuming design process to satisfy stringent constraints with respect to performance, area, power, and cost. In embedded systems, the cost of the memory hierarchy limits its ability to play as central a role. This is due to stringent constraints that fundamentally limit the physical size and complexity of the memory system. Ultimately, application developers and system engineers are charged with the heavy burden of reducing the memory requirements of an application. This thesis offers the intriguing possibility that compilers can play a significant role in the automatic design space exploration and optimization of embedded memory systems. This insight is founded upon a new analytical model and novel compiler optimizations that are specifically designed to increase the synergy between the processor and the memory system. The analytical models serve to characterize intrinsic program properties, quantify the impact of compiler optimizations on the memory systems, and provide deep insight into the trade-offs that affect memory system design.

The thesis deals with the influence of specific localities on the price of a family house. The introductory part is devoted to defining the basic concepts of work and the characteristics of specific localities within the Czech Republic. The application part opens up the formulation of problems, setting the goals of the thesis solution and the methodology used in the research. From various specific locations that may affect the price of a family house were selected protected landscape areas and spas. Based on these specific territories, cities were selected for market analysis. Using statistical methods, the obtained data set was tested and the influence of a specific location on the price of a family house could be determined from the resulting information.

Data-centers increasingly deploy commodity servers with high-speed network interfaces to enable low-latency communication. However, achieving low latency at high data rates crucially depends on how the incoming traffic interacts with the system's caches. When packets that need to be processed in the same way are consecutive, i.e., exhibit high temporal and spatial locality, CPU caches deliver great benefits. This licentiate thesis systematically studies the impact of temporal and spatial traffic locality on the performance of commodity servers equipped with high-speed network interfaces. The results are that (i) the performance of a variety of widely deployed applications degrade substantially with even the slightest lack of traffic locality, and (ii) a traffic trace from our organization's link to/from its upstream provider reveals poor traffic locality as networking protocols, drivers, and the underlying switching/routing fabric spread packets out in time (reducing locality).  To address these issues, we built Reframer, a software solution that deliberately delays packets and reorders them to increase traffic locality. Despite introducing µs-scale delays of some packets, Reframer increases the throughput of a network service chain by up to 84% and reduces the flow completion time of a web server by 11% while improving its throughput by 20%. / Datacenter distribuerar alltmer rå varuservrar med höghastighets-nätverksgränssnitt för att möjliggöra kommunikation med låg latens. Att uppnå låg latens vid höga datahastigheter beror dock mycket på hur den inkommande trafiken interagerar med systemets cacheminnen. När paket som behöver bearbetas på samma sätt är konsekutiva, dvs. uppvisar hög tids- och rumslig lokalitet, ger cacher stora fördelar. I denna licentiatuppsats studerar vi systematiskt effekterna av tidsmässig och rumslig trafikplats på  prestanda för rå varuservrar utrustade med höghastighetsnätgränssnitt.Vå ra resultat visar att (i) prestandan för en mängd allmänt distribuerade applikationer försämras avsevärt med till och med den minsta bristen på trafikplats, och (ii) visar ett trafikspår från vår organisation dålig trafikplats som nätverksprotokoll, drivrutiner och den underliggande omkopplingen/dirigera tygspridningspaket i tid (minska lokaliteten). För att ta itu med dessa problem byggde vi Reframer, en mjukvarulösning som medvetet fördröjer paket och ordnar dem för att öka trafikplatsen. Trots införandet av µs-skalafördröjningar för vissa paket visar vi att Reframer ökar genomströmningen för en nätverkstjänstkedja med upp till 84% och minskar flödet för en webbserver med 11% samtidigt som dess genomströmning förbättras med 20%. / <p>QC 20210512</p> / ULTRA

A new locality of the Alum Shale Formation at Björnberget, Västerbotten County, of the lower allochthon of the Caledonian front is described herein. Two new species of acrotretid brachiopods were found. Tingitanella vilhelminia n. sp. adds another species to the monospecific genus. T. vilhelminia also extend the genus distribution to Sweden. Anabolotreta furcatus n. sp. is the first member of the genus found in Sweden and extend the stratigraphic range to Stage 5 of Cambrian Series 3. It also exhibits an unusual bifurcating shell structure described for the first time herein. One trilobite was found at the locality, Acadoparadoxides torelli, indicating that the exposures at Björnberget belong to the upper Acadoparadoxides (Baltoparadoxides) oelandicus superzone. The fauna found is impoverished in comparison to the fauna that has been described from Jämtland and reflects the depositional environment on the deep outer shelf with low sediment input. The known exposure at Granberget, close to Björnberget, is described with respect to the paleontology and sedimentology of the section. The fauna at Granberget could be extended with two new species of agnostids, Hypagnostus lingula and Hypagnostus mammillatus, to a total of six taxa of trilobites. The depositional environment was periodically affected by storms, depositing limestone layers composed of skeletal material. The Alum shale does not exhibit these sedimentary structures and have probably lost the majority of the them during diagenesis. / En hitintills obeskriven lokal av Alunskifferformationen vid Björnberget, Västerbottens län, beskrivs här med fokus på paleontologi och sedimentologi. Två nya arter av brachiopoder (Acrotretida) upptäcktes. Tingitanella vilhelminia n. sp. utökar släktet med ytterligare en art och utökar även den geografiska distributionen av släktet till Sverige. Anabolotreta furcatus n. sp. är den första medlemmen av släktet som beskrivits från Sverige och utökar den stratigrafiska spännvidden till lägre mellersta Kambrium. A. furcatus har även en skalstruktur med förgrenande pelare som beskrivs för första gången. En trilobit upptäcktes vid lokalen, Acadoparadoxides torelli, vilket tyder på att exponeringarna vid Björnberget tillhör övre delen av superzonen Acadoparadoxides (Baltoparadoxides) oelandicus. Faunan är artfattig i jämförelse med vad som tidigare har beskrivits från Jämtland och reflekterar en depositionsmiljö på den yttre kontinentalsockeln med ett lågt inflöde av klastiska sediment. Den sedan tidigare kända lokalen vid Granberget, nära lokalen vid Björnberget, beskrivs häri med avseende på paleontologi och sedimentologi. Faunan vid Granberget kan utökas med två nya arter av agnostider, Hypagnostus lingula och Hypagnostus mammillatus, till att totalt innehålla sex arter av trilobiter. Depositionsmiljön påverkades periodvis av stormar som avsatte kalkstenslager bestående av skelettdelar. Alunskiffern har förlorat majoriteten av dessa strukturer under diagenes som annars återfinns i kalkstenskonkretionerna.

Changes in society are often discussed on an aggregated level and it is argued that society is changing from a modern industrial society to a post-industrial society. Through studying changes on a local level it is possible to study the complexity and variations of the general and aggregated theories of societal changes, and place changes in a context of time and place. The main object of this study is to analyse change in a locality. The study is a case study which studies Halmstad, a municipality on the west coast of Sweden, between the years of 1968 and 2006. The empirical material consists of analysis of demographic statistics and labour market statistics, using official statistical databases. The empirical material also consists of an analysis of official and historical documents as well as interviews with persons active in Halmstad. Three time periods are identified in the analyses which are characterised by different patterns in the population. The periods are also characterised by changes in the labour market and the employment of the population. These changes are analysed through the interplay between actors in the locality and actors and influences from outside the locality. Through the analysis of reflexivity it is shown how change and stability are interrelated through the interplay between the new and existing or innovation and tradition. / Förändringar i samhället diskuteras ofta på en aggregerad nivå där det argumenteras för att samhället förändras från ett modernt industrisamhälle till ett postindustriellt samhälle. Genom att studera samhället på en lokal nivå är det möjligt att studera komplexitet och variationer av de aggregerade teorierna kring samhällsförändring, det vill säga studera förändring i ett kontext av tid och plats. Utgångspunkten i denna studie är att analysera förändring i ett lokalsamhälle. Studien är en fallstudie av Halmstad, en kommun på Sveriges västkust, mellan åren 1968 och 2006. Det empiriska materialet består av analyser av demografisk statistik och arbetsmarknadsstatistik där offentlig statistik har används. Dessutom har analyser av officiella och historiska dokument samt intervjuer med personer aktiva i Halmstad gjorts. Tre tidsperioder identifieras i analysen, vilka karaktäriseras av olika mönster i befolkningen. Perioderna karaktäriseras även av förändringar på arbetsmarknaden och i befolkningens sysselsättning. Dessa förändringar analyseras genom samspelet mellan aktörer i lokalsamhället och aktörer och influenser som kommer utifrån. Genom analyser av reflexivitet visas hur förändring och stabilitet influeras av samspelet mellan det nya och det existerande, eller innovation och tradition.

A large number of machine learning algorithms are critically dependent on the underlying distance/metric/similarity function. Learning an appropriate distance function is therefore crucial to the success of many methods. The class of distance functions that can be learned accurately is characterized by the amount and type of supervision available to the particular application. In this thesis, we explore a variety of such distance learning problems using different amounts/types of supervision and provide efficient and scalable algorithms to learn appropriate distance functions for each of these problems. First, we propose a generic regularized framework for Mahalanobis metric learning and prove that for a wide variety of regularization functions, metric learning can be used for efficiently learning a kernel function incorporating the available side-information. Furthermore, we provide a method for fast nearest neighbor search using the learned distance/kernel function. We show that a variety of existing metric learning methods are special cases of our general framework. Hence, our framework also provides a kernelization scheme and fast similarity search scheme for such methods. Second, we consider a variation of our standard metric learning framework where the side-information is incremental, streaming and cannot be stored. For this problem, we provide an efficient online metric learning algorithm that compares favorably to existing methods both theoretically and empirically. Next, we consider a contrasting scenario where the amount of supervision being provided is extremely small compared to the number of training points. For this problem, we consider two different modeling assumptions: 1) data lies on a low-dimensional linear subspace, 2) data lies on a low-dimensional non-linear manifold. The first assumption, in particular, leads to the problem of matrix rank minimization over polyhedral sets, which is a problem of immense interest in numerous fields including optimization, machine learning, computer vision, and control theory. We propose a novel online learning based optimization method for the rank minimization problem and provide provable approximation guarantees for it. The second assumption leads to our geometry-aware metric/kernel learning formulation, where we jointly model the metric/kernel over the data along with the underlying manifold. We provide an efficient alternating minimization algorithm for this problem and demonstrate its wide applicability and effectiveness by applying it to various machine learning tasks such as semi-supervised classification, colored dimensionality reduction, manifold alignment etc. Finally, we consider the task of learning distance functions under no supervision, which we cast as a problem of learning disparate clusterings of the data. To this end, we propose a discriminative approach and a generative model based approach and we provide efficient algorithms with convergence guarantees for both the approaches. / text

Distributed shared memory (DSM) systems have been recognised as a compelling platform for parallel computing due to the programming advantages and scalability. DSM systems allow applications to access data in a logically shared address space by abstracting away the distinction of physical memory location. As the location of data is transparent, the sources of overhead caused by accessing the distant memories are difficult to analyse. This memory locality problem has been identified as crucial to DSM performance. Many researchers have investigated the problem using simulation as a tool for conducting experiments resulting in the progressive evolution of DSM systems. Nevertheless, both the diversity of architectural configurations and the rapid advance of DSM implementations impose constraints on simulation model designs in two issues: the limitation of the simulation framework on model extensibility and the lack of verification applicability during a simulation run causing the delay in verification process. This thesis studies simulation modelling techniques for memory locality analysis of various DSM systems implemented on top of a cluster of symmetric multiprocessors. The thesis presents a simulation technique to promote model extensibility and proposes a technique for verification applicability, called a Specification-based Parameter Model Interaction (SPMI). The proposed techniques have been implemented in a new interpretation-driven simulation called DSiMCLUSTER on top of a discrete event simulation (DES) engine known as HASE. Experiments have been conducted to determine which factors are most influential on the degree of locality and to determine the possibility to maximise the stability of performance. DSiMCLUSTER has been validated against a SunFire 15K server and has achieved similarity of cache miss results, an average of +-6% with the worst case less than 15% of difference. These results confirm that the techniques used in developing the DSiMCLUSTER can contribute ways to achieve both (a) a highly extensible simulation framework to keep up with the ongoing innovation of the DSM architecture, and (b) the verification applicability resulting in an efficient framework for memory analysis experiments on DSM architecture.

Existing cache organization suffers from the inability to distinguish different types of localities, and non-selectively cache all data rather than making any attempt to take special advantage of the locality type. This causes unnecessary movement of data among the levels of the memory hierarchy and increases in miss ratio. In this dissertation I propose a split data cache architecture that will group memory accesses as scalar or array references according to their inherent locality and will subsequently map each group to a dedicated cache partition. In this system, because scalar and array references will no longer negatively affect each other, cache-interference is diminished, delivering better performance. Further improvement is achieved by the introduction of victim cache, prefetching, data flattening and reconfigurability to tune the array and scalar caches for specific application. The most significant contribution of my work is the introduction of novel cache architecture for embedded microprocessor platforms. My proposed cache architecture uses reconfigurability coupled with split data caches to reduce area and power consumed by cache memories while retaining performance gains. My results show excellent reductions in both memory size and memory access times, translating into reduced power consumption. Since there was a huge reduction in miss rates at L-1 caches, further power reduction is achieved by partially or completely shutting down L-2 data or L-2 instruction caches. The saving in cache sizes resulting from these designs can be used for other processor activities including instruction and data prefetching, branch-prediction buffers. The potential benefits of such techniques for embedded applications have been evaluated in my work. I also explore how my cache organization performs for non-numeric data structures. I propose a novel idea called "Data flattening" which is a profile based memory allocation technique to compress sparsely scattered pointer data into regular contiguous memory locations and explore the potentials of my proposed Spit cache organization for data treated with data flattening method.