Dissertations / Theses on the topic 'Matching'
To see the other types of publications on this topic, follow the link: Matching.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Matching.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Ranger, Martin. "Matching issues." College Park, Md. : University of Maryland, 2005. http://hdl.handle.net/1903/2690.
Abstract:
Thesis (Ph. D.) -- University of Maryland, College Park, 2005.Thesis research directed by: Economics. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.
2
Prakash, Piyush Martin Alain J. "Slack matching /." Diss., Pasadena, Calif. : California Institute of Technology, 2005. http://resolver.caltech.edu/CaltechETD:etd-05272005-134017.
3
Jin, Wei. "GRAPH PATTERN MATCHING, APPROXIMATE MATCHING AND DYNAMIC GRAPH INDEXING." Case Western Reserve University School of Graduate Studies / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=case1307547974.
4
Tam, Siu-lung. "Linear-size indexes for approximate pattern matching and dictionary matching." Click to view the E-thesis via HKUTO, 2010. http://sunzi.lib.hku.hk/hkuto/record/B44205326.
5
Tam, Siu-lung, and 譚小龍. "Linear-size indexes for approximate pattern matching and dictionary matching." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2010. http://hub.hku.hk/bib/B44205326.
6
Ko, E. Soon. "Product Matching through Multimodal Image and Text Combined Similarity Matching." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-301306.
Abstract:
Product matching in e-commerce is an area that faces more and more challenges with growth in the e-commerce marketplace as well as variation in the quality of data available online for each product. Product matching for e-commerce provides competitive possibilities for vendors and flexibility for customers by identifying identical products from different sources. Traditional methods in product matching are often conducted through rule-based methods and methods tackling the issue through machine learning usually do so through unimodal systems. Moreover, existing methods would tackle the issue through product identifiers which are not always unified for each product. This thesis provides multimodal approaches through product name, description, and image to the problem area of product matching that outperforms unimodal approaches. Three multimodal approaches were taken, one unsupervised and two supervised. The unsupervised approach uses straight-forward embedding space to nearest neighbor search that provides better results than unimodal approaches. One of the supervised multimodal approaches uses Siamese network on the embedding space which outperforms the unsupervised multi- modal approach. Finally, the last supervised approach instead tackles the issue by exploiting distance differences in each modality through logistic regression and a decision system that provided the best results.Produktmatchning inom e-handel är ett område som möter fler och fler utmaningar med hänsyn till den tillväxt som e-handelsmarknaden undergått och fortfarande undergår samt variation i kvaliteten på den data som finns tillgänglig online för varje produkt. Produktmatchning inom e-handel är ett område som ger konkurrenskraftiga möjligheter för leverantörer och flexibilitet för kunder genom att identifiera identiska produkter från olika källor. Traditionella metoder för produktmatchning genomfördes oftast genom regelbaserade metoder och metoder som utnyttjar maskininlärning gör det vanligtvis genom unimodala system. Dessutom utnyttjar mestadels av befintliga metoder produktidentifierare som inte alltid är enhetliga för varje produkt mellan olika källor. Denna studie ger istället förslag till multimodala tillvägagångssätt som istället använder sig av produktnamn, produktbeskrivning och produktbild för produktmatchnings-problem vilket ger bättre resultat än unimodala metoder. Tre multimodala tillvägagångssätt togs, en unsupervised och två supervised. Den unsupervised metoden använder embeddings vektorerna rakt av för att göra en nearest neighborsökning vilket gav bättre resultat än unimodala tillvägagångssätt. Ena supervised multimodal tillvägagångssätten använder siamesiska nätverk på embedding utrymmet vilket gav resultat som överträffade den unsupervised multimodala tillvägagångssättet. Slutligen tar den sista supervised metoden istället avståndsskillnader i varje modalitet genom logistisk regression och ett beslutssystem som gav bästa resultaten.
7
Karichery, Sureshan. "Sequential matching problem." [S.l. : s.n.], 2004. http://deposit.ddb.de/cgi-bin/dokserv?idn=971627754.
8
Michalis, Konstantinos. "Background matching camouflage." Thesis, University of Bristol, 2017. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.723478.
9
Neou, Both Emerite. "Permutation pattern matching." Thesis, Paris Est, 2017. http://www.theses.fr/2017PESC1239/document.
Abstract:
Cette thèse s'intéresse au problème de la recherche de motif dans les permutations, qui a pour objectif de savoir si un motif apparaît dans un texte, en prenant en compte que le motif et le texte sont des permutations. C'est-à-dire s'il existe des éléments du texte tel que ces éléments sont triés de la même manière et apparaissent dans le même ordre que les éléments du motif. Ce problème est NP complet. Cette thèse expose des cas particuliers de ce problème qui sont solvable en temps polynomial.Pour cela nous étudions le problème en donnant des contraintes sur le texte et/ou le motif. En particulier, le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 2413 et 3142 (appelé permutation séparable) et le cas où le texte et/ou le motif sont des permutations qui ne contiennent pas les motifs 213 et 231 sont considérés. Des problèmes dérivés de la recherche de motif et le problème de la recherche de motif bivinculaire sont aussi étudiésThis thesis focuses on permutation pattern matching problem, which askswhether a pattern occurs in a text where both the pattern and text are permutations.In other words, we seek to determine whether there exist elements ofthe text such that they are sorted and appear in the same order as the elementsof the pattern. The problem is NP-complete. This thesis examines particularcases of the problem that are polynomial-time solvable.For this purpose, we study the problem by giving constraints on the permutationstext and/or pattern. In particular, the cases in which the text and/orpattern are permutations in which the patterns 2413 and 3142 do not occur(also known as separable permutations) and in which the text and/or patternare permutations in which the patterns 213 and 231 do not occur (also known aswedge permutations) are also considered. Some problems related to the patternmatching and the permutation pattern matching with bivincular pattern arealso studied
10
Modi, Amit. "Matching Based Diversity." The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306866934.
11
Burq, Maximilien. "Dynamic matching algorithms." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/121713.
Abstract:
This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2019
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 203-213).
We study marketplaces in which participants arrive over time, looking to interact with each other. While such interactions have historically been decentralized, the past few years have seen a dramatic increase in the number of internet-enabled platforms which facilitate the process of connecting together, or matching, sets of two or more participants. We will focus mainly on centralized matching markets such as kidney exchange and carpooling platforms. In such platforms, the algorithm which determines whom to match and when to do so plays an important role in the efficiency of the marketplace. In the first part, we study the interface between the participant heterogeneity, the types of matchings that are allowed, and the frequency at which the platform computes the allocations. We provide an empirical analysis of the effect of match frequency based on data from major US Kidney exchange programs. We then study models that enable us to compare the participants' match rates and waiting times under varying matching policies. We show both in theory and in practice that matching quickly can be beneficial, compared to policies which try to increase opportunities for optimization through artificial waiting. Until now, the theory of matching algorithms has focused mostly on static environments and little is known in the case where all participants arrive and depart dynamically. In our second part, we help bridge this gap by introducing a new theoretical problem for dynamic matching when anyone can arrive online. We provide new algorithms with state-of-the-art theoretical guarantees, both in the case of adversarial and random order inputs. Finally, we show that these algorithms perform well on kidney exchange and carpooling data.
by Maximilien Burq.
Ph. D.
Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center
12
Kharghoria, Arun. "Field scale history matching and assisted history matching using streamline simulation." Texas A&M University, 2003. http://hdl.handle.net/1969.1/1151.
Abstract:
In this study, we apply the streamline-based production data integration method to condition a multimillion cell geologic model to historical production response for a giant Saudi Arabian reservoir. The field has been under peripheral water injection with 16 injectors and 70 producers. There is also a strong aquifer influx into the field. A total of 30 years of production history with detailed rate, infill well and re-perforation schedule were incorporated via multiple pressure updates during streamline simulation. Also, gravity and compressibility effects were included to account for water slumping and aquifer support. To our knowledge, this is the first and the largest such application of production data integration to geologic models accounting for realistic field conditions. We have developed novel techniques to analytically compute the sensitivities of the production response in the presence of gravity and changing field conditions. This makes our method computationally extremely efficient. The field application takes less than 6 hours to run on a PC.
The geologic model derived after conditioning to production response was validated using field surveillance data. In particular, the flood front movement, the aquifer encroachment and bypassed oil locations obtained from the geologic model was found to be consistent with field observations. Finally, an examination of the permeability changes during production data integration revealed that most of these changes were aligned along the facies distribution, particularly the 'good' facies distribution with no resulting loss in geologic realism.
We also propose a novel assisted history matching procedure for finite difference simulators using streamline derived sensitivity calculations. Unlike existing assisted history matching techniques where the user is required to manually adjust the parameters, this procedure combines the rigor of finite difference models and efficiencies of streamline simulators to perform history matching. Finite difference simulator is used to solve for pressure, flux and saturations which, in turn, are used as input for the streamline simulator for estimating the parameter sensitivities analytically. The streamline derived sensitivities are then used to update the reservoir model. The updated model is then used in the finite difference simulator in an iterative mode until a significant satisfactory history match is obtained.
The assisted history matching procedure has been tested for both synthetic and field examples. The results show a significant speed-up in history matching using conventional finite difference simulators.
13
Nikjoo, Soukhtabandani Ali. "Partial shape matching using CCP map and weighted graph transformation matching." Thesis, Université Laval, 2014. http://www.theses.ulaval.ca/2014/30611/30611.pdf.
Abstract:
La détection de la similarité ou de la différence entre les images et leur mise en correspondance sont des problèmes fondamentaux dans le traitement de l'image. Pour résoudre ces problèmes, on utilise, dans la littérature, différents algorithmes d'appariement. Malgré leur nouveauté, ces algorithmes sont pour la plupart inefficaces et ne peuvent pas fonctionner correctement dans les situations d’images bruitées. Dans ce mémoire, nous résolvons la plupart des problèmes de ces méthodes en utilisant un algorithme fiable pour segmenter la carte des contours image, appelée carte des CCPs, et une nouvelle méthode d'appariement. Dans notre algorithme, nous utilisons un descripteur local qui est rapide à calculer, est invariant aux transformations affines et est fiable pour des objets non rigides et des situations d’occultation. Après avoir trouvé le meilleur appariement pour chaque contour, nous devons vérifier si ces derniers sont correctement appariés. Pour ce faire, nous utilisons l'approche « Weighted Graph Transformation Matching » (WGTM), qui est capable d'éliminer les appariements aberrants en fonction de leur proximité et de leurs relations géométriques. WGTM fonctionne correctement pour les objets à la fois rigides et non rigides et est robuste aux distorsions importantes. Pour évaluer notre méthode, le jeu de données ETHZ comportant cinq classes différentes d'objets (bouteilles, cygnes, tasses, girafes, logos Apple) est utilisé. Enfin, notre méthode est comparée à plusieurs méthodes célèbres proposées par d'autres chercheurs dans la littérature. Bien que notre méthode donne un résultat comparable à celui des méthodes de référence en termes du rappel et de la précision de localisation des frontières, elle améliore significativement la précision moyenne pour toutes les catégories du jeu de données ETHZ.Matching and detecting similarity or dissimilarity between images is a fundamental problem in image processing. Different matching algorithms are used in literature to solve this fundamental problem. Despite their novelty, these algorithms are mostly inefficient and cannot perform properly in noisy situations. In this thesis, we solve most of the problems of previous methods by using a reliable algorithm for segmenting image contour map, called CCP Map, and a new matching method. In our algorithm, we use a local shape descriptor that is very fast, invariant to affine transform, and robust for dealing with non-rigid objects and occlusion. After finding the best match for the contours, we need to verify if they are correctly matched. For this matter, we use the Weighted Graph Transformation Matching (WGTM) approach, which is capable of removing outliers based on their adjacency and geometrical relationships. WGTM works properly for both rigid and non-rigid objects and is robust to high order distortions. For evaluating our method, the ETHZ dataset including five diverse classes of objects (bottles, swans, mugs, giraffes, apple-logos) is used. Finally, our method is compared to several famous methods proposed by other researchers in the literature. While our method shows a comparable result to other benchmarks in terms of recall and the precision of boundary localization, it significantly improves the average precision for all of the categories in the ETHZ dataset.
14
Mäkinen, Veli. "Parameterized approximate string matching and local-similarity-based point-pattern matching." Helsinki : University of Helsinki, 2003. http://ethesis.helsinki.fi/julkaisut/mat/tieto/vk/makinen/.
15
Ochs, Christopher S. "Independent b-matching Approximation Algorithm with Applications to Peer-to-Peer Networks." University of Cincinnati / OhioLINK, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1593273022789919.
16
Baltsavias, Emmanuel P. Baltsavias Emmanuel P. Baltsavias Emmanuel P. "Multiphoto geometrically constrained matching /." Zürich, 1991. http://e-collection.ethbib.ethz.ch/show?type=diss&nr=9561.
17
Bilke, Alexander. "Duplicate based schema matching." [S.l.] : [s.n.], 2006. http://opus.kobv.de/tuberlin/volltexte/2007/1558.
18
Abdelsaid, Sherif H. Kamal. "Matching remote sensing images." Thesis, University of Ottawa (Canada), 1996. http://hdl.handle.net/10393/9560.
Abstract:
Image analysis plays a crucial role in many computer vision applications in which images of the same scene with different geometrical orientations need to be compared for further processing. This thesis describes the design and implementation of a model-based vision system for the recognition of aerial images. The main objective is to register two remote sensing images taken at different times. First, some distinctive features are extracted and matched then, these matched features are used as marking points in defining a geometric mapping function. Once registered, the reference image can be used as an aid to automatic interpretation and as a framework for detecting changes between successive images. A two stage matching procedure is used for this task. In the first part, corners are extracted and matched in both images and an initial estimation of the mapping function is computed. This initial function is then used in the second part to estimate the parameters of a global mapping function for the entire image. The process ends when all the extracted features in one image are either mapped to features in the other image, or rejected if no match could be found.
19
Tuckey, Charles E. "Pattern matching in charity." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1997. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp04/mq24702.pdf.
20
Soo, Terry. "Coupling, matching, and equivariance." Thesis, University of British Columbia, 2010. http://hdl.handle.net/2429/24237.
Abstract:
This thesis consists of four research papers and one expository note that study factors of point processes in the contexts of thinning and matching.
In "Poisson Splitting by Factors," we prove that given a Poisson point process on Rd with intensity λ, as a deterministic function of the process, we can colour the points red and blue, so that each colour class forms a Poisson point process on Rd, with any given pair of intensities summing λ; furthermore, the function can be chosen as an isometry-equivariant finitary factor (that is, if an isometry is applied to the points of the original process the points are still coloured the same way). Thus using only local information, without a central authority or additional
randomization, points of a Poisson process can split into two groups, each of which are still Poisson.
In "Deterministic Thinning of Finite Poisson Processes," we investigate similar questions for Poisson point processes on a finite volume. In this setting we find that even without considerations of equivariance, thinning can not always be achieved as a deterministic function of the Poisson process and the existence of such a function depends on the intensities of the original and resulting Poisson process.
In "Insertion and Deletion Tolerance of Point Processes," we define for point processes a version of the concept of finite-energy. This simple concept has many interesting consequences. We explore the consequences of having finite-energy in the contexts of the Boolean continuum percolation model, Palm theory and stable matchings of point processes.
In "Translation-Equivariant Matchings of Coin-Flips on Zd," as a factor of i.i.d. fair coin-flips on Zd, we construct perfect matchings of heads and tails and prove power law upper bounds on the expected distance between matched pairs.
In the expository note "A Nonmeasurable Set from Coin-Flips," using the notion of an equivariant function, we give an example of a nonmeasurable set in the probability space for an infinite sequence of coin-flips.
21
Lie, Chin Cheong Patrick. "Geometrically constrained matching schemes." Thesis, McGill University, 1992. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=39316.
Abstract:
We present an effective method for solving different types of noisy pattern matching problems in Euclidean space. The matching is performed in either a least-squares or a mixed-norm sense under the constraint that a transformation matrix $ Theta$ is restricted to belong to the orthogonal group. Matching problems of this type can be recast as function optimization problems which can be solved by representing the orthogonal group to which $ Theta$ belongs as a Lie group and then investigating the gradient vector field associated with the function to be optimized. The projection of the gradient field onto the tangent space of the Lie group at $ Theta$, i.e., the Lie algebra, results in a descent/ascent equation for the function. The descent/ascent equation so obtained is used in a classical steepest-descent/ascent algorithm and a singular value decomposition-based recursive method in order to determine the maximum or minimum point of the function under consideration. Since $ Theta$ belongs to the orthogonal group which includes the group of permutations as a subgroup, the proposed procedure works not only for patterns consisting of ordered feature points, but also for the combinatorial problem involving patterns having unordered feature points. Generalizations of the matching problem are also formulated and include the matching of patterns from Euclidean spaces of different dimensions and the matching of patterns having unequal numbers of feature points from the same Euclidean space. Simulations are performed which demonstrate the effectiveness and the efficiency of the proposed approach in solving some practical matching problems which arise in computer vision and pattern analysis.
22
Agarwal, Nikhil. "Essays in Empirical Matching." Thesis, Harvard University, 2013. http://dissertations.umi.com/gsas.harvard:10745.
Abstract:
This thesis combines three essays on empirical applications and methods in two-sided matching markets. The first essay uses existing methods to estimate preferences for schools using rank order lists from New York City's new high school assignment system launched in Fall 2003 to study the consequences of coordinating school admissions in a mechanism based on the student-proposing deferred acceptance algorithm. The second essay develops techniques for estimating preferences in two-sided matching markets with non-transferable utility using only data on final matches. It uses these techniques to estimate preferences in the market for family medicine residents. These estimates are then used to analyze two economic questions. First, it investigates whether centralization in the market for medical residents is primarily responsible for low salaries paid to medical residents. Second, it analyzes the effects of government interventions intended to encourage training of medical residents in rural areas. The final essay studies estimation and non-parametric identfication of preferences in two-sided matching markets with non-transferable utility. It studies the special case in which preferences of each side of the market is vertical and data from a pairwise stable match, in a single large market is observed.Economics
23
Wei, YaNing. "Image registration and matching." Thesis, University of Nottingham, 2005. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.430757.
24
Delgado, Lisa A. "Matching Market for Skills." Diss., Temple University Libraries, 2009. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/41030.
Abstract:
EconomicsPh.D.
This dissertation builds a model of information exchange, where the information is skills. A two-sided matching market for skills is employed that includes two distinct sides, skilled and unskilled agents, and the matches that connect these agents. The unskilled agents wish to purchase skills from the skilled agents, who each possess one valuable and unique skill. Skilled agents may match with many unskilled agents, while each unskilled agent may match with only one skilled agent. Direct interaction is necessary between the agents to teach and learn the skill. Thus, there must be mutual consent for a match to occur and the skill to be exchanged. In this market for skills, a discrete, simultaneous move game is employed where all agents announce their strategies at once, every skilled agent announcing a price and every unskilled agent announcing the skill she wishes to purchase. First, both Nash equilibria and a correlated equilibrium are determined for an example of this skills market game. Next, comparative statics are employed on this discrete, simultaneous move game through computer simulations. Finally, a continuous, simultaneous move game is studied where all agents announce their strategies at once, every skilled agent announcing a price and every unskilled agent announcing a skill and price pair. For this game, an algorithm is developed that if used by all agents to determine their strategies leads to a strong Nash equilibrium for the game.
Temple University--Theses
25
BRAUNER, DANIELA FRANCISCO. "INSTANCE-BASED SCHEMA MATCHING." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2008. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=12573@1.
Abstract:
CONSELHO NACIONAL DE DESENVOLVIMENTO CIENTÍFICO E TECNOLÓGICOUm mediador é um componente de software que auxilia o acesso a fontes de dados. Com o advento da Web, a construção de mediadores impõe desafios importantes, tais como a capacidade de fornecer acesso integrado a fontes de dados independentes e dinâmicas e a habilidade de resolver a heterogeneidade semântica entre os esquemas destas fontes. Para lidar com esses desafios, o alinhamento de esquemas é uma questão fundamental. Nesta tese são propostas abordagens de alinhamento de esquemas de classificação (tesauros) e esquemas conceituais, utilizando instâncias como evidências para os mapeamentos. As abordagens propostas são classificadas em dois tipos: adaptativa e a priori, referindo-se, respectivamente, à descoberta dos mapeamentos de forma incremental ou à definição dos mapeamentos antes da implantação do mediador. Por fim, são apresentados experimentos para validação e teste das abordagens propostas.
A mediator is a software component that helps accessing data sources. With the advent of the Web, the design of mediators imposes important challenges, such as the ability of providing integrated access to independent and dynamic data sources and the ability of resolving the semantic heterogeneity between different data source schemas. To deal with these challenges, schema matching is a fundamental issue. In this thesis, matching approaches for classification schemas (thesauri) and conceptual schemas are proposed, using instances as evidences for the mappings. The proposed approaches are classified as adaptative and a priori, referring to, respectively, the discovery of the mappings in an incremental way or the definition of the mappings before the deployment of the mediator. Finally, experiments to validate and test the proposed approaches are presented.
26
Thornton, Mark Philip. "Matching problems in graphs." Thesis, Imperial College London, 1990. http://hdl.handle.net/10044/1/46579.
27
Kabiri, Isfahani Yasin. "Injection matching of antenna." Thesis, University of Birmingham, 2016. http://etheses.bham.ac.uk//id/eprint/7136/.
Abstract:
One of the most important modules of the current and next generation of the wireless communications is the antenna. The coexistence of the machine and human in the next communication system will open-up a vast range of new applications and communication services which need to be supported by the antenna. Moreover, the forthcoming 5G technology vision is prognosticated on the use of multiple communication bands and standards in a seamless fashion. This can force the mobile devices to have multiple antennas on a single device which will add significant complexity or using an antenna with wideband reconfiguration capability. On the other hand, switched-off analogue communications provides the opportunity for re-using prime spectrum in UHF bands. Considering the size of hand-held devices, this will need strong miniaturization. To address these requirements, electrically small, tunable, wideband and highly efficient antenna technology is strongly desired. In this thesis a new area of research in antenna design is introduced which has been unexplored by the other researchers. A new theory called Injection Matching Theory (IMT) is proposed which uses multi-port configuration. This will enable to control current distribution on the antenna structure at its extremities and couple a wave length, much larger than what the antenna dimensions naturally allow. Apart from electrically small operation this can be used for improving band width and efficiency, and providing reconfiguration capability. To illustrate the versatility of the proposed theory, for every feature mentioned above a chapter is provided which demonstrates the potential capability of the proposed theory via simulation and fabrication of the prototyped examples.
28
Zager, Laura (Laura A. ). "Graph similarity and matching." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/34119.
Abstract:
Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.Includes bibliographical references (p. 85-88).
Measures of graph similarity have a broad array of applications, including comparing chemical structures, navigating complex networks like the World Wide Web, and more recently, analyzing different kinds of biological data. This thesis surveys several different notions of similarity, then focuses on an interesting class of iterative algorithms that use the structural similarity of local neighborhoods to derive pairwise similarity scores between graph elements. We have developed a new similarity measure that uses a linear update to generate both node and edge similarity scores and has desirable convergence properties. This thesis also explores the application of our similarity measure to graph matching. We attempt to correctly position a subgraph GB within a graph GA using a maximum weight matching algorithm applied to the similarity scores between GA and GB. Significant performance improvements are observed when the topological information provided by the similarity measure is combined with additional information about the attributes of the graph elements and their local neighborhoods. Matching results are presented for subgraph matching within randomly-generated graphs; an appendix briefly discusses matching applications in the yeast interactome, a graph representing protein-protein interactions within yeast.
by Laura Zager.
S.M.
29
Lundin, Gustav. "Pattern Matching in Encore." Thesis, Uppsala universitet, Institutionen för informationsteknologi, 2016. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-294513.
Abstract:
Encore is a young object-oriented programming language. The standard object-oriented model which embraces encapsulation works well for many kinds of problems but not all; it does not perform well when the algorithm inherently demands many objects to be decomposed at once. To address the need for an elegant way to write programs that solve such problems we have extended Encore with a pattern matching construct capable of decomposing objects. This thesis recounts how we designed and implemented pattern matching in Encore and presents some examples of how it can be used. We found that for problems that are not well suited for fully encapsulated objects, pattern matching leads to much more concise and clean code. However, this comes at the cost of additional run-time.
30
Kudrya, V. G., and D. A. Voronenko. "Designing Nanotechnology Matching Devices." Thesis, Sumy State University, 2013. http://essuir.sumdu.edu.ua/handle/123456789/35357.
Abstract:
The work describes the features of simulation of the ultrahigh-frequency electromagnetic interaction, which forms an internal solenoid status of monolithic integrated circuits. As an example, is the study of matching devices, which are made in the form of the band-pass lines. The proposed method of modeling, to determine the dependence of the finite frequency and temporal characteristics of the cascading schemes amplifiers. Thus, the proposed method of modeling physical processes appear not only domestic but also external display spatially distributed nano-and micro-strip technology structures.
When you are citing the document, use the following link http://essuir.sumdu.edu.ua/handle/123456789/35357
31
Zilberstein, Ofer. "Relational matching for stereopsis /." The Ohio State University, 1991. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487759436328173.
32
Klinkmüller, Christopher. "Adaptive Process Model Matching." Doctoral thesis, Universitätsbibliothek Leipzig, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:15-qucosa-224884.
Abstract:
Process model matchers automate the detection of activities that represent similar functionality in different models. Thus, they provide support for various tasks related to the management of business processes including model collection management and process design. Yet, prior research primarily demonstrated the matchers’ effectiveness, i.e., the accuracy and the completeness of the results. In this context (i) the size of the empirical data is often small, (ii) all data is used for the matcher development, and (iii) the validity of the design decisions is not studied. As a result, existing matchers yield a varying and typically low effectiveness when applied to different datasets, as among others demonstrated by the process model matching contests in 2013 and 2015. With this in mind, the thesis studies the effectiveness of matchers by separating development from evaluation data and by empirically analyzing the validity and the limitations of design decisions. In particular, the thesis develops matchers that rely on different sources of information. First, the activity labels are considered as natural-language descriptions and the Bag-of-Words Technique is introduced which achieves a high effectiveness in comparison to the state of the art. Second, the Order Preserving Bag-of-Words Technique analyzes temporal dependencies between activities in order to automatically configure the Bag-of-Words Technique and to improve its effectiveness. Third, expert feedback is used to adapt the matchers to the domain characteristics of process model collections. Here, the Adaptive Bag-of-Words Technique is introduced which outperforms the state-of-the-art matchers and the other matchers from this thesis.
33
Kadam, Sangram Vilasrao. "Models of Matching Markets." Thesis, Harvard University, 2016. http://nrs.harvard.edu/urn-3:HUL.InstRepos:33493461.
Abstract:
The structure, length, and characteristics of matching markets affect the outcomes for their participants. This dissertation attempts to fill the lacuna in our understanding about matching markets on three dimensions through three essays. The first essay highlights the role of constraints at the interviewing stage of matching markets where participants have to make choices even before they discover their own preferences entirely. Two results stand out from this setting. When preferences are ex-ante aligned, relaxing the interviewing constraints for one side of the market improves the welfare for everyone on the other side. Moreover, such interventions can lead to a decrease in the number of matched agents. The second essay elucidates the importance of rematching opportunities when relationships last over multiple periods. It identifies sufficient conditions for existence of a stable matching which accommodates the form of preferences we expect to see in multi-period environments. Preferences with inter-temporal complementarities, desire for variety and a status-quo bias are included in this setting. The third essay furthers our understanding while connecting two of the sufficient conditions in a specialized matching with contracts setting. It provides a novel linkage by providing a constructive way of arriving at a preference condition starting from another and thus proving that the later implies the former.Economics
34
Jeong, Jinyong. "Essays in Matching Theory." Thesis, Boston College, 2018. http://hdl.handle.net/2345/bc-ir:107959.
Abstract:
Thesis advisor: Utku UnverMy doctoral research focuses on the matching theory and its market design application. Specifically, I work on matching with property rights, where property rights not only mean the ownership, but also refer to the ability to determine how the good is used. In the matching with property rights model, an agent who owns a resource can claim how her resource is offered, depending on what she gets from the system. For example, in a housing exchange for vacation, an agent who gets a house with a car will offer her house also with a car. However, if she is assigned only a house without a car, she might refuse to offer a car. This restriction can be thought as a matching with externality, as someone's consuming my resource in certain way affects my utility. With property rights present, it is not clear how we can achieve a desirable outcome while satisfying the rights. I am currently pursuing two main lines of research in this topic that constitute the two chapters dissertation. In Matching with Property Rights: an Application to a Parking Space Assignment Problem, I introduce parking in urban areas as a matching problem. First, I model the street-parking market as a strategic game and show that the set of Nash equilibrium outcomes is equivalent to the set of stable allocations. However, it is not reasonable to expect drivers to reach a Nash equilibrium in the decentralized system due to lack of information and coordination failure. Therefore, I suggest a centralized mechanism that would enable a parking authority to assign available spaces to drivers in a stable way. The model incorporates resident parking spaces, such that visitors could access vacant resident spaces. To use the resident parking spaces, the system needs to protect exclusive property rights over their parking spaces. I show that, however, there is no mechanism that is stable and protects residents' rights. To resolve this issue, I introduce a new concept, a claim contract, and suggest a mechanism that protects property rights, is strategy proof for the drivers, and approximates a stable matching. Besides its market-design focus, this paper handles both priority-based and property right-based assignment, which considered separately in the matching theory literature. In Housing Market with Contracts, I study matching with property rights problem in the housing market framework. To introduce property rights in housing market, I assume the house can be offered in two contractual terms. Property rights requires that when an agent gets a house in a certain term, her house should also be offered as the same term. Moreover, when every agent owns a house, property rights reduces to an equal-term matching. After defining efficiency and core in equal-term domain, I show that, in a housing market with contracts problem, core may be empty. However, there always exists an efficient, individually rational, and equal-term matching in every housing market with contracts problem. Then I present a mechanism that always produces an efficient, individually rational, and equal-term matching. This is the first attempt to model a matching with contract in a exchange economy
Thesis (PhD) — Boston College, 2018
Submitted to: Boston College. Graduate School of Arts and Sciences
Discipline: Economics
35
Sun, Yi. "New matching algorithm -- Outlier First Matching (OFM) and its performance on Propensity Score Analysis (PSA) under new Stepwise Matching Framework (SMF)." Thesis, State University of New York at Albany, 2014. http://pqdtopen.proquest.com/#viewpdf?dispub=3633233.
Abstract:
An observational study is an empirical investigation of treatment effect when randomized experimentation is not ethical or feasible (Rosenbaum 2009). Observational studies are common in real life due to the following reasons: a) randomization is not feasible due to the ethical or financial reason; b) data are collected from survey or other resources where the object and design of the study has not been determined (e.g. retrospective study using administrative records); c) little knowledge on the given region so that some preliminary studies of observational data are conducted to formulate hypotheses to be tested in subsequent experiments. When statistical analysis are done using observational studies, the following issues need to be considered: a) the lack of randomization may lead to a selection bias; b) representativeness of sampling with respect to the problem under consideration (e.g. study of factors influencing a rare disease using a nationally representative survey with respective to race, income, and gender but not with respect to the rare disease condition).We will use the following sample to illustrate the challenges of observational studies and possible mitigation measures.
Our example is based on the study by Lalonde (1986), which evaluated the impact of job training on the earnings improvement of low-skilled workers in 1970's (In Paper 1 section 1.5.2, we will discuss this data set in more detail). The treatment effect estimated from the observational study was quite different from the one obtained using the baseline randomized "National Supported Work (NSW) Experiment" carried out in the mid-1970's. Now we understand the treatment effect which is the impact of job training. Selection bias may contaminate the treatment effect, in other words, workers who receive the job training may be fundamentally different from those who do not. Furthermore, the sample of control group selected for observational study by Lalonde may not represent the sample of control group from the original NSW experiment.
In this study, we address the issue of lack of randomization by applying a new matching algorithm (Outlier First Matching, OFM) which can be used in conjunction with the Propensity Score Analysis (PSA) or other similar methods to achieve the convincible treatment effect estimation in observational studies.
This dissertation consists of three papers.
Paper 1 proposes a new "Stepwise Matching Framework (SMF)" and rationalizes its usage in causal inference study (especially for PSA study using observational data). Furthermore, under the new framework of SMF, one new matching algorithm (Outlier First Matching or OFM in short) will be introduced. Its performance along with other well-known matching algorithms will be studied using the cross sectional data.
Paper 2 extends methods of paper 1 to correlated data (especially to longitudinal data). In the circumstance of correlated data (e.g. longitudinal data), besides the selection bias as in cross-sectional observational data, the repeated measures bring out the between-subject and within-subject correlation. Furthermore, the repeated measures can also bring out the missing value problem and rolling enrollment problem. All of above challenges from correlated data complexity the data structure and need to be addressed using more complex model and methodology. Our methodology calculate the variant p-score of control subjects at each time point and generate the p-score difference from each control subject to every treatment subject at treatment subject's time point. Then such p-score differences are summarized to create the distance matrix for next step analysis. Once again, the performance of OFM and other well-established matching algorithms are compared side by side and the conclusion will be summarized through simulation and real data applications.
Paper 3 handles missing value problem in longitudinal data. As we have mentioned in paper 2, the complexity of data structure of longitudinal data often comes with the problem of missing data. Due to the possibility of between subject and within subject correlation, the traditional imputation methodology will probably ignore the above two correlations so that it may lead to biased or inefficient imputation of missing data. We adopt one missing value imputation strategy introduced by Schafer and Yucel (2002) through one R package "pan" to handle the above two correlations. The "imputed complete data" will be treated using the similar methodology as paper 2. Then MI results will be summarized using Rubin's rule (1987). The conclusion will be drawn based on the findings through simulation study and compared to what we have found in complete longitudinal data study in paper 2.
In last section, we conclude the dissertation with the discussion of preliminary results, as well as the strengths and limitations of the present research. Also we will point out the direction of the future study and provide suggestions to practice works.
36
Lachance, Bernard 1967. "A new penumbra generator for matching of electron for matching of electron fields." Thesis, McGill University, 1996. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=24018.
Abstract:
We describe the geometric and dosimetric characteristics of a device developed to modify the penumbra of an electron beam and thereby improve the dose uniformity in the overlap region when fields are abutted. The device is a Lipowitz metal block placed on top of the electron applicator's insertion plate and positioned to stop part of the electron beam. The air-scattered electrons beyond the block increase the penumbra width from about 1.4 to 2.7-3.4 cm. The modified penumbra is broad and almost linear at all depths for the 9 MeV and 12 MeV electron beams used in this study. Film dosimetry was used to obtain beam profiles and isodose distributions. Without the penumbra generator, lateral setup errors of 2 to 3 mm may introduce dose variations of up to 20% in the junction region. Similar setup errors cause less than 5% dose variations when the penumbra generator is used to match the fields.
37
Van, der Merwe Nick. "Development of an image matching scheme using feature- and area based matching techniques." Doctoral thesis, University of Cape Town, 1995. http://hdl.handle.net/11427/21341.
Abstract:
Image matching is widely considered to be one of the most difficult tasks of a digital photogrammetric system. Traditionally image matching has been approached from either an area based or a feature based point of view. In recent years significant progress has been made in Area Based Matching (ABM) techniques such as Multiphoto Geometrically Constrained Least Squares Matching. Also in the field of Feature Based Matching (FBM) improvements have been made in extracting and matching image features, using for example the Forstner Operator followed by feature matching. Generally, area- and feature based matching techniques have been developed independently from each other. The aim of this research project was to design an automated image matching scheme that combines aspects of Feature Based Matching (FBM) and Area Based Matching (ABM). The reason for taking a hybrid approach is to encapsulate only the advantages of each matching scheme while cancelling out the disadvantages. The approach taken was to combine traditional aspects of ABM in digital photogrammetry with image analysis techniques found more commonly in the area of image processing and specifically machine vision.
38
Ngo, Duy Hoa. "Enhancing Ontology Matching by Using Machine Learning, Graph Matching and Information Retrieval Techniques." Thesis, Montpellier 2, 2012. http://www.theses.fr/2012MON20096/document.
Abstract:
Ces dernières années, les ontologies ont suscité de nombreux travaux dans le domaine du web sémantique. Elles sont utilisées pour fournir le vocabulaire sémantique permettant de rendre la connaissance du domaine disponible pour l'échange et l'interprétation au travers des systèmes d'information. Toutefois, en raison de la nature décentralisée du web sémantique, les ontologies sont très hétérogènes. Cette hétérogénéité provoque le problème de la variation de sens ou ambiguïté dans l'interprétation des entités et, par conséquent, elle empêche le partage des connaissances du domaine. L'alignement d'ontologies, qui a pour but la découverte des correspondances sémantiques entre des ontologies, devient une tâche cruciale pour résoudre ce problème d'hétérogénéité dans les applications du web sémantique. Les principaux défis dans le domaine de l'alignement d'ontologies ont été décrits dans des études récentes. Parmi eux, la sélection de mesures de similarité appropriées ainsi que le réglage de la configuration de leur combinaison sont connus pour être des problèmes fondamentaux que la communauté doit traiter. En outre, la vérification de la cohérence sémantique des correspondances est connue pour être une tâche importante. Par ailleurs, la difficulté du problème augmente avec la taille des ontologies. Pour faire face à ces défis, nous proposons dans cette thèse une nouvelle approche, qui combine différentes techniques issues des domaines de l'apprentissage automatique, d'appariement de graphes et de recherche d'information en vue d'améliorer la qualité de l'alignement d'ontologies. En effet, nous utilisons des techniques de recherche d'information pour concevoir de nouvelles mesures de similarité efficaces afin de comparer les étiquettes et les profils d'entités de contexte au niveau des entités. Nous appliquons également une méthode d'appariement de graphes appelée propagation de similarité au niveau de la structure qui découvre effectivement des correspondances en exploitant des informations structurelles des entités. Pour combiner les mesures de similarité au niveau des entités, nous transformons la tâche de l'alignement d'ontologie en une tâche de classification de l'apprentissage automatique. Par ailleurs, nous proposons une méthode dynamique de la somme pondérée pour combiner automatiquement les correspondances obtenues au niveau des entités et celles obtenues au niveau de la structure. Afin d'écarter les correspondances incohérentes, nous avons conçu une nouvelle méthode de filtrage sémantique. Enfin, pour traiter le problème de l'alignement d'ontologies à large échelle, nous proposons deux méthodes de sélection des candidats pour réduire l'espace de calcul.Toutes ces contributions ont été mises en œuvre dans un prototype nommé YAM++. Pour évaluer notre approche, nous avons utilisé des données du banc d'essai de la compétition OAEI : Benchmark, Conference, Multifarm, Anatomy, Library and Large Biomedical Ontologies. Les résultats expérimentaux montrent que les méthodes proposées sont très efficaces. De plus, en comparaison avec les autres participants à la compétition OAEI, YAM++ a montré sa compétitivité et a acquis une position de haut rangIn recent years, ontologies have attracted a lot of attention in the Computer Science community, especially in the Semantic Web field. They serve as explicit conceptual knowledge models and provide the semantic vocabularies that make domain knowledge available for exchange and interpretation among information systems. However, due to the decentralized nature of the semantic web, ontologies are highlyheterogeneous. This heterogeneity mainly causes the problem of variation in meaning or ambiguity in entity interpretation and, consequently, it prevents domain knowledge sharing. Therefore, ontology matching, which discovers correspondences between semantically related entities of ontologies, becomes a crucial task in semantic web applications.Several challenges to the field of ontology matching have been outlined in recent research. Among them, selection of the appropriate similarity measures as well as configuration tuning of their combination are known as fundamental issues that the community should deal with. In addition, verifying the semantic coherent of the discovered alignment is also known as a crucial task. Furthermore, the difficulty of the problem grows with the size of the ontologies. To deal with these challenges, in this thesis, we propose a novel matching approach, which combines different techniques coming from the fields of machine learning, graph matching and information retrieval in order to enhance the ontology matching quality. Indeed, we make use of information retrieval techniques to design new effective similarity measures for comparing labels and context profiles of entities at element level. We also apply a graph matching method named similarity propagation at structure level that effectively discovers mappings by exploring structural information of entities in the input ontologies. In terms of combination similarity measures at element level, we transform the ontology matching task into a classification task in machine learning. Besides, we propose a dynamic weighted sum method to automatically combine the matching results obtained from the element and structure level matchers. In order to remove inconsistent mappings, we design a new fast semantic filtering method. Finally, to deal with large scale ontology matching task, we propose two candidate selection methods to reduce computational space.All these contributions have been implemented in a prototype named YAM++. To evaluate our approach, we adopt various tracks namely Benchmark, Conference, Multifarm, Anatomy, Library and Large BiomedicalOntologies from the OAEI campaign. The experimental results show that the proposed matching methods work effectively. Moreover, in comparison to other participants in OAEI campaigns, YAM++ showed to be highly competitive and gained a high ranking position
39
Banks, Jasmine. "Reliability analysis of transform-based stereo matching techniques, and a new matching constraint." Thesis, Queensland University of Technology, 2000. https://eprints.qut.edu.au/36106/6/Jasmine%20Banks_Digitised_Thesis.pdf.
Abstract:
Stereo vision is a method of depth perception, in which depth information is inferred from two (or more) images of a scene, taken from different perspectives. Practical applications for stereo vision include aerial photogrammetry, autonomous vehicle guidance, robotics and industrial automation. The initial motivation behind this work was to produce a stereo vision sensor for mining automation applications. For such applications, the input stereo images would consist of close range scenes of rocks.
A fundamental problem faced by matching algorithms is the matching or correspondence problem. This problem involves locating corresponding points or features in two images. For this application, speed, reliability, and the ability to produce a dense depth map are of foremost importance. This work implemented a number of areabased matching algorithms to assess their suitability for this application. Area-based techniques were investigated because of their potential to yield dense depth maps, their amenability to fast hardware implementation, and their suitability to textured scenes such as rocks. In addition, two non-parametric transforms, the rank and census, were also compared. Both the rank and the census transforms were found to result in improved reliability of matching in the presence of radiometric distortion - significant since radiometric distortion is a problem which commonly arises in practice.
In addition, they have low computational complexity, making them amenable to fast hardware implementation. Therefore, it was decided that matching algorithms using these transforms would be the subject of the remainder of the thesis.
An analytic expression for the process of matching using the rank transform was derived from first principles. This work resulted in a number of important contributions.
Firstly, the derivation process resulted in one constraint which must be satisfied for a correct match. This was termed the rank constraint. The theoretical derivation of this constraint is in contrast to the existing matching constraints which have little theoretical basis. Experimental work with actual and contrived stereo pairs has shown that the new constraint is capable of resolving ambiguous matches, thereby improving match reliability. Secondly, a novel matching algorithm incorporating the rank constraint has been proposed. This algorithm was tested using a number of stereo pairs.
In all cases, the modified algorithm consistently resulted in an increased proportion of correct matches. Finally, the rank constraint was used to devise a new method for identifying regions of an image where the rank transform, and hence matching, are more susceptible to noise.
The rank constraint was also incorporated into a new hybrid matching algorithm, where it was combined a number of other ideas. These included the use of an image pyramid for match prediction, and a method of edge localisation to improve match accuracy in the vicinity of edges. Experimental results obtained from the new algorithm showed that the algorithm is able to remove a large proportion of invalid matches, and improve match accuracy.
40
Vitali, Federico. "Map-Matching su Piattaforma BigData." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/18089/.
Abstract:
Nell'ambito dell'analisi dei dati di movimento atto all'estrazione di informazioni utili, il map matching ha l'obiettivo di proiettare i punti GPS generati dagli oggetti in movimento sopra i segmenti stradali in modo da rappresentare l'attuale posizione degli oggetti. Fino ad ora, il map matching è stato sfruttato in ambiti come l'analisi del traffico, l'estrazione dei percorsi frequenti e la predizione della posizione degli oggetti, oltre a rappresentare un'importante fase di pre-processing nell'intero procedimento di trajectory mining. Sfortunatamente, le implementazioni allo stato dell'arte degli algoritmi di map matching sono tutte sequenziali o inefficienti. In questa tesi viene quindi proposto un algoritmo il quale si basa su di un algoritmo sequenziale conosciuto per la sua accuratezza ed efficienza il quale viene completamente riformulato in maniera distribuita in modo tale da raggiungere anche un elevata scalabilità nel caso di utilizzo con i big data. Inoltre, viene migliorata la robustezza dell'algoritmo, il quale è basato sull'Hidden Markov Model di primo ordine, introducendo una strategia per gestire i possibili buchi di informazione che si possono venire a creare tra i segmenti stradali assegnati. Infatti, il problema può accadere in caso di campionamento variabile dei punti GPS in aree urbane con un elevata frammentazione dei segmenti stradali. L'implementazione è basata su Apache Spark e testata su un dataset di oltre 7.8 milioni di punti GPS nella città di Milano.
41
U, Leong-Hou. "Matching problems in large databases." Click to view the E-thesis via HKUTO, 2010. http://sunzi.lib.hku.hk/hkuto/record/B43910488.
42
Solé, Ribalta Albert. "Multiple graph matching and applications." Doctoral thesis, Universitat Rovira i Virgili, 2012. http://hdl.handle.net/10803/86941.
Abstract:
En aplicaciones de reconocimiento de patrones, los grafos con atributos son en gran medida apropiados. Normalmente, los vértices de los grafos representan partes locales de los objetos i las aristas relaciones entre estas partes locales. No obstante, estas ventajas vienen juntas con un severo inconveniente, la distancia entre dos grafos no puede ser calculada en un tiempo polinómico. Considerando estas características especiales el uso de los prototipos de grafos es necesariamente omnipresente. Las aplicaciones de los prototipos de grafos son extensas, siendo las más habituales clustering, clasificación, reconocimiento de objetos, caracterización de objetos i bases de datos de grafos entre otras. A pesar de la diversidad de aplicaciones de los prototipos de grafos, el objetivo del mismo es equivalente en todas ellas, la representación de un conjunto de grafos. Para construir un prototipo de un grafo todos los elementos del conjunto de enteramiento tienen que ser etiquetados comúnmente. Este etiquetado común consiste en identificar que nodos de que grafos representan el mismo tipo de información en el conjunto de entrenamiento. Una vez este etiquetaje común esta hecho, los atributos locales pueden ser combinados i el prototipo construido. Hasta ahora los algoritmos del estado del arte para calcular este etiquetaje común mancan de efectividad o bases teóricas. En esta tesis, describimos formalmente el problema del etiquetaje global i mostramos una taxonomía de los tipos de algoritmos existentes. Además, proponemos seis nuevos algoritmos para calcular soluciones aproximadas al problema del etiquetaje común. La eficiencia de los algoritmos propuestos es evaluada en diversas bases de datos reales i sintéticas. En la mayoría de experimentos realizados los algoritmos propuestos dan mejores resultados que los existentes en el estado del arte.In pattern recognition, the use of graphs is, to a great extend, appropriate and advantageous. Usually, vertices of the graph represent local parts of an object while edges represent relations between these local parts. However, its advantages come together with a sever drawback, the distance between two graph cannot be optimally computed in polynomial time. Taking into account this special characteristic the use of graph prototypes becomes ubiquitous. The applicability of graphs prototypes is extensive, being the most common applications clustering, classification, object characterization and graph databases to name some. However, the objective of a graph prototype is equivalent to all applications, the representation of a set of graph. To synthesize a prototype all elements of the set must be mutually labeled. This mutual labeling consists in identifying which nodes of which graphs represent the same information in the training set. Once this mutual labeling is done the set can be characterized and combined to create a graph prototype. We call this initial labeling a common labeling. Up to now, all state of the art algorithms to compute a common labeling lack on either performance or theoretical basis. In this thesis, we formally describe the common labeling problem and we give a clear taxonomy of the types of algorithms. Six new algorithms that rely on different techniques are described to compute a suboptimal solution to the common labeling problem. The performance of the proposed algorithms is evaluated using an artificial and several real datasets. In addition, the algorithms have been evaluated on several real applications. These applications include graph databases and group-wise image registration. In most of the tests and applications evaluated the presented algorithms have showed a great improvement in comparison to state of the art applications.
43
Wenk, Carola. "Shape matching in higher dimensions." [S.l.] : [s.n.], 2003. http://www.diss.fu-berlin.de/2003/151/index.html.
44
Pais, Joana. "Incentives in Random Matching Markets." Doctoral thesis, Universitat Autònoma de Barcelona, 2005. http://hdl.handle.net/10803/4062.
Abstract:
El objetivo de esta tesis es estudiar el funcionamiento de los mercados de trabajo dónde los trabajadores son asignados a las empresas por procesos aleatorios usando modelos de asignación bilateral. En estos modelos, los agentes pertenecen a uno de dos conjuntos disjuntos -empresas y trabajadores- y cada agente tiene preferencias ordinales sobre el otro lado del mercado. El problema se reduce a una asignación de los miembros de estos dos conjuntos el uno al otro.En el segundo capítulo, titulado "On Random Matching Markets: Properties and Equilibria," se describe un algoritmo que empieza desde una asignación cualquiera y continua creando, a cada paso, una asignación provisional. En cada momento del tiempo, una empresa es elegida al azar y se considera el mejor trabajador en su lista de preferencias. Si este trabajador ya está asignado a una empresa mejor, la asignación no se altera. En caso contrario, el trabajador y la empresa quedan temporalmente juntos hasta que el trabajador reciba una propuesta de trabajo mejor. Seguidamente, se exploran algunas propiedades del algoritmo; por ejemplo, el algoritmo generaliza el famoso algoritmo de "deferred-acceptance" de Gale y Shapley. Luego se analizan los incentivos que los agentes enfrentan en el juego de revelación inducido por el algoritmo. El hecho de que las empresas son seleccionadas al azar introduce incertidumbre en el resultado final. Una vez que las preferencias de los agentes son ordinales, se utiliza un concepto de equilibrio ordinal, basado en la dominancia estocastica de primer orden.
En el tercer capítulo, "Incentives in Decentralized Random Matching Markets," se considera un juego secuencial dónde los agentes actúan de acuerdo con las reglas generales del algoritmo. En este capítulo, las estrategias de los agentes pueden tomar una forma cualquiera y no tienen que coincidir con una lista de preferencias. El primer jugador es la Naturaleza, que elige una secuencia de empresas , que representa la incertidumbre existente en un mercado descentralizado. Luego, las empresas son elegidas de acuerdo con la sequencia y les es dada la oportunidad de hacer una propuesta. Ya que el juego es dinamico, se analizan los equilibrios de Nash ordinales perfectos en subjuegos.
En "Random Stable Mechanisms in the College Admissions Problem," se considera el juego inducido por un mecanismo aleatorio estable. En este capítulo, se caracterizan los equilibrios de Nash ordinales. En particular, puede obtenerse una asignación en un equilibrio dónde las empresas revelan sus verdaderas preferencias si y sólo si la asignación es estable con respecto a las verdaderas preferencias.
Por fin, en el último capítulo, se caracterizan los equilibrios perfectos ordinales en el juego inducido por un mecanismo aleatorio estable.
The purpose of this thesis is to explore the functioning of labor markets where workers are assigned to firms by means of random processes using two-sided matching models. In these models, agents belong to one of two disjoint sets -firms and workers- and each agent has ordinal preferences over the other side of the market. Matching reduces to assigning the members of these two sets to one another.
In the second chapter, entitled "On Random Matching Markets: Properties and Equilibria," I describe an algorithm that starts with any matching situation and proceeds by creating, at each step, a provisional matching. At each moment in time, a firm is randomly chosen and the best worker on its list of preferences is considered. If this worker is already holding a firm he prefers, the matching goes unchanged. Otherwise, they are (temporarily) matched, pending the possible draw of even better firms willing to match this worker. Some features of this algorithm are explored; namely, it encompasses other algorithms in the literature, as Gale and Shapley's famous deferred-acceptance algorithm. I then analyze the incentives facing agents in the revelation game induced by the proposed algorithm. The random order in which firms are selected when the algorithm is run introduces some uncertainty in the output reached. Since agents' preferences are ordinal in nature, I use ordinal Nash equilibria, based on first-order stochastic dominance.
In the third chapter, "Incentives in Decentralized Random Matching Markets," I take a step further by considering a sequential game where agents act according to the general rules of the algorithm. The original feature is that available strategies exhaust all possible forms of behavior: agents act in what they perceive to be their own best interest throughout the game, not necessarily according to a list of possible matches. The game starts with a move by Nature that determines the order of play, reflecting the inherently uncertain features of a decentralized market. Then, firms are selected according to the drawn order and given the opportunity to offer their positions. In order to account for the dynamic nature of the game, I characterize subgame perfect ordinal Nash equilibria.
Following a different approach, in "Random Stable Mechanisms in the College Admissions Problem," I consider the game induced by a random stable matching mechanism. In this paper, I characterize ordinal Nash equilibria, providing simultaneously some results that extend to deterministic mechanisms. In particular, a matching can be obtained as the outcome of a play of the game where firms reveal their true preferences if and only if it is stable with respect to the true preferences.
In closing, in the last chapter I characterize perfect equilibria in the game induced by a random stable mechanism.
45
Lennartsson, Mattias. "Object Recognition with Cluster Matching." Thesis, Linköping University, Department of Electrical Engineering, 2009. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-51494.
Abstract:
Within this thesis an algorithm for object recognition called Cluster Matching has been developed, implemented and evaluated. The image information is sampled at arbitrary sample points, instead of interest points, and local image features are extracted. These sample points are used as a compact representation of the image data and can quickly be searched for prior known objects. The algorithm is evaluated on a test set of images and the result is surprisingly reliable and time efficient.
46
Voigt, Konrad. "Structural Graph-based Metamodel Matching." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-81671.
Abstract:
Data integration has been, and still is, a challenge for applications processing multiple heterogeneous data sources. Across the domains of schemas, ontologies, and metamodels, this imposes the need for mapping specifications, i.e. the task of discovering semantic correspondences between elements. Support for the development of such mappings has been researched, producing matching systems that automatically propose mapping suggestions.
However, especially in the context of metamodel matching the result quality of state of the art matching techniques leaves room for improvement. Although the traditional approach of pair-wise element comparison works on smaller data sets, its quadratic complexity leads to poor runtime and memory performance and eventually to the inability to match, when applied on real-world data.
The work presented in this thesis seeks to address these shortcomings. Thereby, we take advantage of the graph structure of metamodels. Consequently, we derive a planar graph edit distance as metamodel similarity metric and mining-based matching to make use of redundant information. We also propose a planar graph-based partitioning to cope with large-scale matching. These techniques are then evaluated using real-world mappings from SAP business integration scenarios and the MDA community. The results demonstrate improvement in quality and managed runtime and memory consumption for large-scale metamodel matching.
47
Webb, Kerri. "Matrix Formulations of Matching Problems." Thesis, University of Waterloo, 2000. http://hdl.handle.net/10012/1119.
Abstract:
Finding the maximum size of a matching in an undirected graph and finding the maximum size of branching in a directed graph can be formulated as matrix rank problems. The Tutte matrix, introduced by Tutte as a representation of an undirected graph, has rank equal to the maximum number of vertices covered by a matching in the associated graph. The branching matrix, a representation of a directed graph, has rank equal to the maximum number of vertices covered by a branching in the associated graph. A mixed graph has both undirected and directed edges, and the matching forest problem for mixed graphs, introduced by Giles, is a generalization of the matching problem and the branching problem. A mixed graph can be represented by the matching forest matrix, and the rank of the matching forest matrix is related to the size of a matching forest in the associated mixed graph. The Tutte matrix and the branching matrix have indeterminate entries, and we describe algorithms that evaluate the indeterminates as rationals in such a way that the rank of the evaluated matrix is equal to the rank of the indeterminate matrix. Matroids in the context of graphs are discussed, and matroid formulations for the matching, branching, and matching forest problems are given.
48
Dragisic, Zlatan. "Semantic Matching for Stream Reasoning." Thesis, Linköpings universitet, KPLAB - Laboratoriet för kunskapsbearbetning, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-71669.
Abstract:
Autonomous system needs to do a great deal of reasoning during execution in order to provide timely reactions to changes in their environment. Data needed for this reasoning process is often provided through a number of sensors. One approach for this kind of reasoning is evaluation of temporal logical formulas through progression. To evaluate these formulas it is necessary to provide relevant data for each symbol in a formula. Mapping relevant data to symbols in a formula could be done manually, however as systems become more complex it is harder for a designer to explicitly state and maintain thismapping. Therefore, automatic support for mapping data from sensors to symbols would make system more flexible and easier to maintain. DyKnow is a knowledge processing middleware which provides the support for processing data on different levels of abstractions. The output from the processing components in DyKnow is in the form of streams of information. In the case of DyKnow, reasoning over incrementally available data is done by progressing metric temporal logical formulas. A logical formula contains a number of symbols whose values over time must be collected and synchronized in order to determine the truth value of the formula. Mapping symbols in formula to relevant streams is done manually in DyKnow. The purpose of this matching is for each variable to find one or more streams whose content matches the intended meaning of the variable. This thesis analyses and provides a solution to the process of semantic matching. The analysis is mostly focused on how the existing semantic technologies such as ontologies can be used in this process. The thesis also analyses how this process can be used for matching symbols in a formula to content of streams on distributed and heterogeneous platforms. Finally, the thesis presents an implementation in the Robot Operating System (ROS). The implementation is tested in two case studies which cover a scenario where there is only a single platform in a system and a scenario where there are multiple distributed heterogeneous platforms in a system. The conclusions are that the semantic matching represents an important step towards fully automatized semantic-based stream reasoning. Our solution also shows that semantic technologies are suitable for establishing machine-readable domain models. The use of these technologies made the semantic matching domain and platform independent as all domain and platform specific knowledge is specified in ontologies. Moreover, semantic technologies provide support for integration of data from heterogeneous sources which makes it possible for platforms to use streams from distributed sources.
49
Shepherd, Tânia Maria Granja. "Matching relations in narrative discourse." reponame:Repositório Institucional da UFPR, 2012. http://hdl.handle.net/1884/27867.
50
Abrahamson, Jeff Shokoufandeh Ali. "Optimal matching and deterministic sampling /." Philadelphia, Pa. : Drexel University, 2007. http://hdl.handle.net/1860/2526.