Given a large set of records in a database and a query record, similarity search aims to find all records sufficiently similar to the query record. To solve this problem, two main aspects need to be considered: First, to perform effective search, the set of relevant records is defined using a similarity measure. Second, an efficient access method is to be found that performs only few database accesses and comparisons using the similarity measure. This thesis solves both aspects with an emphasis on the latter. In the first part of this thesis, a frequency-aware similarity measure is introduced. Compared record pairs are partitioned according to frequencies of attribute values. For each partition, a different similarity measure is created: machine learning techniques combine a set of base similarity measures into an overall similarity measure. After that, a similarity index for string attributes is proposed, the State Set Index (SSI), which is based on a trie (prefix tree) that is interpreted as a nondeterministic finite automaton. For processing range queries, the notion of query plans is introduced in this thesis to describe which similarity indexes to access and which thresholds to apply. The query result should be as complete as possible under some cost threshold. Two query planning variants are introduced: (1) Static planning selects a plan at compile time that is used for all queries. (2) Query-specific planning selects a different plan for each query. For answering top-k queries, the Bulk Sorted Access Algorithm (BSA) is introduced, which retrieves large chunks of records from the similarity indexes using fixed thresholds, and which focuses its efforts on records that are ranked high in more than one attribute and thus promising candidates. The described components form a complete similarity search system. Based on prototypical implementations, this thesis shows comparative evaluation results for all proposed approaches on different real-world data sets, one of which is a large person data set from a German credit rating agency. / Ziel von Ähnlichkeitssuche ist es, in einer Menge von Tupeln in einer Datenbank zu einem gegebenen Anfragetupel all diejenigen Tupel zu finden, die ausreichend ähnlich zum Anfragetupel sind. Um dieses Problem zu lösen, müssen zwei zentrale Aspekte betrachtet werden: Erstens, um eine effektive Suche durchzuführen, muss die Menge der relevanten Tupel mithilfe eines Ähnlichkeitsmaßes definiert werden. Zweitens muss eine effiziente Zugriffsmethode gefunden werden, die nur wenige Datenbankzugriffe und Vergleiche mithilfe des Ähnlichkeitsmaßes durchführt. Diese Arbeit beschäftigt sich mit beiden Aspekten und legt den Fokus auf Effizienz. Im ersten Teil dieser Arbeit wird ein häufigkeitsbasiertes Ähnlichkeitsmaß eingeführt. Verglichene Tupelpaare werden entsprechend der Häufigkeiten ihrer Attributwerte partitioniert. Für jede Partition wird ein unterschiedliches Ähnlichkeitsmaß erstellt: Mithilfe von Verfahren des Maschinellen Lernens werden Basisähnlichkeitsmaßes zu einem Gesamtähnlichkeitsmaß verbunden. Danach wird ein Ähnlichkeitsindex für String-Attribute vorgeschlagen, der State Set Index (SSI), welcher auf einem Trie (Präfixbaum) basiert, der als nichtdeterministischer endlicher Automat interpretiert wird. Zur Verarbeitung von Bereichsanfragen wird in dieser Arbeit die Notation der Anfragepläne eingeführt, um zu beschreiben welche Ähnlichkeitsindexe angefragt und welche Schwellwerte dabei verwendet werden sollen. Das Anfrageergebnis sollte dabei so vollständig wie möglich sein und die Kosten sollten einen gegebenen Schwellwert nicht überschreiten. Es werden zwei Verfahren zur Anfrageplanung vorgeschlagen: (1) Beim statischen Planen wird zur Übersetzungszeit ein Plan ausgewählt, der dann für alle Anfragen verwendet wird. (2) Beim anfragespezifischen Planen wird für jede Anfrage ein unterschiedlicher Plan ausgewählt. Zur Beantwortung von Top-k-Anfragen stellt diese Arbeit den Bulk Sorted Access-Algorithmus (BSA) vor, der große Mengen von Tupeln mithilfe fixer Schwellwerte von den Ähnlichkeitsindexen abfragt und der Tupel bevorzugt, die hohe Ähnlichkeitswerte in mehr als einem Attribut haben und damit vielversprechende Kandidaten sind. Die vorgestellten Komponenten bilden ein vollständiges Ähnlichkeitssuchsystem. Basierend auf einer prototypischen Implementierung zeigt diese Arbeit vergleichende Evaluierungsergebnisse für alle vorgestellten Ansätze auf verschiedenen Realwelt-Datensätzen; einer davon ist ein großer Personendatensatz einer deutschen Wirtschaftsauskunftei.

Skeletal shape representations, in spite of their structural instabilities, have proven themselves as effective representation schemes for recognition and classification of visual shapes. They capture part structure in a compact and natural way and provide insensitivity to visual transformations such as occlusion and articulation of parts. In this thesis, we explore the potential use of disconnected skeleton representation for shape recognition and shape classification. Specifically, we first investigate the importance of contextual information in recognition where we extend the previously proposed disconnected skeleton based shape matching methods in different ways by incorporating category knowledge into matching process. Unlike the view in syntactic matching of shapes, our interpretation differentiates the semantic roles of the shapes in comparison in a way that a query shape is being matched with a database shape whose category is known a priori. The presence of context, i.e. the knowledge about the category of the database shape, influences the similarity computations, and helps us to obtain better matching performance. Next, we build upon our category-influenced matching framework in which both shapes and shape categories are represented with depth-1 skeletal trees, and develop a similarity-based shape classification method where the category trees formed for each shape category provide a reference set for learning the relationships between categories. As our classification method takes into account both within-category and between-category information, we attain high classification performance. Moreover, using the suggested classification scheme in a retrieval task improves both the efficiency and accuracy of matching by eliminating unrelated comparisons.

Cluster-based information retrieval systems often use a similarity measure to compute the association among text documents. In this thesis, we focus on a class of similarity measures named Query-Sensitive Similarity (QSS) measures. Recent studies have shown QSS measures to positively influence the outcome of a clustering procedure. These studies have used QSS measures in conjunction with the ltc term-weighting scheme. Several term-weighting schemes have superseded the ltc term-weighing scheme and demonstrated better retrieval performance relative to the latter. We test whether introducing one of these schemes, INQUERY, will offer any benefit over the ltc scheme when used in the context of QSS measures. The testing procedure uses the Nearest Neighbor (NN) test to quantify the clustering effectiveness of QSS measures and the corresponding term-weighting scheme. The NN tests are applied on certain standard test document collections and the results are tested for statistical significance. On analyzing results of the NN test relative to those obtained for the ltc scheme, we find several instances where the INQUERY scheme improves the clustering effectiveness of QSS measures. To be able to apply the NN test, we designed a software test framework, Ferret, by complementing the features provided by dtSearch, a search engine. The test framework automates the generation of NN coefficients by processing standard test document collection data. We provide an insight into the construction and working of the Ferret test framework.

As a response to trade marks’ enhanced importance within trade, the EU’s interest in the area has increased by proponing a harmonization of the member states’ trade mark pro-tection so far as needed to preserve the EU’s objective of an internal market. The area is therefore regulated by an EU Directive, however allowing some national discretion. The purpose of this study was to investigate if a specific part of the trade mark protec-tion, the assessment-based confusion doctrine, corresponds on a Swedish and EU level. The aim was to locate statutory discrepancies in order to stimulate further review of the practical application of the doctrine from the analytical perspective of legal certainty. A scientifically accepted and traditional legal research method was applied when ex-amining and interpreting the sources of law. In addition, a comparative study was con-ducted between the two investigated legal systems to achieve the overall purpose. When comparing the results from the investigated sources, the legislations present a sta-tutory diversity, opening up for practical discrepancies. So was also the case with the application at the early stage of national implementation of the EU Directive. The tradi-tional national confusion doctrine, prescribing a more legal-technical assessment, did not correspond to the more flexible and contemporary EU view. Consequently, some national courts had to endure criticism for not adjusting to the EU development. Later case law however presents a very positive transition to the EU view of the confu-sion doctrine, suggesting a partial abandonment of the national legal sources of law for the benefit of EU law. Conclusion was however that despite this practical transition to EU law, statutory changes are necessary in order to safeguard the legal certainty in the way of achieving predictability.

The main contribution of this thesis, is to define similarity measures between two images with the main focus on content-based image retrieval (CBIR). Each image is considered as a set of visual elements that can be described with a set of visual descriptions (features). The similarity between images is then defined as the nearness between sets of elements based on a tolerance and a fuzzy tolerance relation. A tolerance relation is used to describe the approximate nature of the visual perception. A fuzzy tolerance relation is adopted to eliminate the need for a sharp threshold and hence model the gradual changes in perception of similarities. Three real valued similarity measures as well as a fuzzy valued similarity measure are proposed. All of the methods are then used in two CBIR experiments and the results are compared with classical measures of distance (namely, Kantorovich, Hausdorff and Mahalanobis). The results are compared with other published research papers. An important advantage of the proposed methods is shown to be their effectiveness in an unsupervised setting with no prior information. Eighteen different features (based on color, texture and edge) are used in all the experiments. A feature selection algorithm is also used to train the system in choosing a suboptimal set of visual features.

Automated map generalization is a necessary technique for the construction of multi-scale vector map databases that are crucial components in spatial data infrastructure of cities, provinces, and countries. Nevertheless, this is still a dream because many algorithms for map feature generalization are not parameter-free and therefore need human’s interference. One of the major reasons is that map generalization is a process of spatial similarity transformation in multi-scale map spaces; however, no theory can be found to support such kind of transformation. This thesis focuses on the theory of spatial similarity relations in multi-scale map spaces, aiming at proposing the approaches and models that can be used to automate some relevant algorithms in map generalization. After a systematic review of existing achievements including the definitions and features of similarity in various communities, a classification system of spatial similarity relations, and the calculation models of similarity relations in the communities of psychology, computer science, music, and geography, as well as a number of raster-based approaches for calculating similarity degrees between images, the thesis achieves the following innovative contributions. First, the fundamental issues of spatial similarity relations are explored, i.e. (1) a classification system is proposed that classifies the objects processed by map generalization algorithms into ten categories; (2) the Set Theory-based definitions of similarity, spatial similarity, and spatial similarity relation in multi-scale map spaces are given; (3) mathematical language-based descriptions of the features of spatial similarity relations in multi-scale map spaces are addressed; (4) the factors that affect human’s judgments of spatial similarity relations are proposed, and their weights are also obtained by psychological experiments; and (5) a classification system for spatial similarity relations in multi-scale map spaces is proposed. Second, the models that can calculate spatial similarity degrees for the ten types of objects in multi-scale map spaces are proposed, and their validity is tested by psychological experiments. If a map (or an individual object, or an object group) and its generalized counterpart are given, the models can be used to calculate the spatial similarity degrees between them. Third, the proposed models are used to solve problems in map generalization: (1) ten formulae are constructed that can calculate spatial similarity degrees by map scale changes in map generalization; (2) an approach based on spatial similarity degree is proposed that can determine when to terminate a map generalization system or an algorithm when it is executed to generalize objects on maps, which may fully automate some relevant algorithms and therefore improve the efficiency of map generalization; and (3) an approach is proposed to calculate the distance tolerance of the Douglas-Peucker Algorithm so that the Douglas-Peucker Algorithm may become fully automatic. Nevertheless, the theory and the approaches proposed in this study possess two limitations and needs further exploration. • More experiments should be done to improve the accuracy and adaptability of the proposed models and formulae. The new experiments should select more typical maps and map objects as samples, and find more subjects with different cultural backgrounds. • Whether it is feasible to integrate the ten models/formulae for calculating spatial similarity degrees into an identical model/formula needs further investigation. In addition, it is important to find out the other algorithms, like the Douglas-Peucker Algorithm, that are not parameter-free and closely related to spatial similarity relation, and explore the approaches to calculating the parameters used in these algorithms with the help of the models and formulae proposed in this thesis.

Every single day, lots of users actively participate in social media sites (e.g., Facebook, YouTube, Last.fm, Flicker, etc.) upload photos, videos, share bookmarks, write blogs and annotate/comment on content provided by others. With the recent proliferation of social media sites, users are overwhelmed by the huge amount of available content. Therefore, organizing and retrieving appropriate multimedia content is becoming an increasingly important and challenging task. This challenging task led a number of research communities to concentrate on social tagging systems (also known as folksonomy) that allow users to freely annotate their media items (e.g., music, images, or video) with any sort of arbitrary words, referred to as tags. Tags assist users to organize their own content, as well as to find relevant content shared by other users. In this thesis, we first analyze how useful a folksonomy is for improving personalized services such as tag recommendation, tag-based search and item annotation. We then propose two new algorithms for social media retrieval and tag recommendation respectively. The first algorithm computes the latent preferences of tags for users from other similar tags, as well as latent annotations of tags for items from other similar items. We then seamlessly map the tags onto items, depending on an individual user’s query, to find the most desirable content relevant to the user’s needs. The second algorithm improves tag-recommendation and item annotation by adapting the Katz measure, a path-ensemble based proximity measure, for the use in social tagging systems. In this algorithm we model folksonomy as a weighted, undirected tripartite graph. We then apply the Katz measure to this graph, and exploit it to provide personalized tag recommendation for individual users. We evaluate our algorithms on two real-world folksonomies collected from Last.fm and CiteULike. The experimental results demonstrate that the proposed algorithms improve the search and the recommendation performance, and obtain significant gains in cold start situations where relatively little information is known about a user or an item

The main contribution of this thesis, is to define similarity measures between two images with the main focus on content-based image retrieval (CBIR). Each image is considered as a set of visual elements that can be described with a set of visual descriptions (features). The similarity between images is then defined as the nearness between sets of elements based on a tolerance and a fuzzy tolerance relation. A tolerance relation is used to describe the approximate nature of the visual perception. A fuzzy tolerance relation is adopted to eliminate the need for a sharp threshold and hence model the gradual changes in perception of similarities. Three real valued similarity measures as well as a fuzzy valued similarity measure are proposed. All of the methods are then used in two CBIR experiments and the results are compared with classical measures of distance (namely, Kantorovich, Hausdorff and Mahalanobis). The results are compared with other published research papers. An important advantage of the proposed methods is shown to be their effectiveness in an unsupervised setting with no prior information. Eighteen different features (based on color, texture and edge) are used in all the experiments. A feature selection algorithm is also used to train the system in choosing a suboptimal set of visual features.

Submitted by Livia Mello (liviacmello@yahoo.com.br) on 2016-10-11T14:05:01Z No. of bitstreams: 1 DissGIF.pdf: 2443815 bytes, checksum: 100e28390f0b9b6780e2b2ce9aedfe39 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T12:14:37Z (GMT) No. of bitstreams: 1 DissGIF.pdf: 2443815 bytes, checksum: 100e28390f0b9b6780e2b2ce9aedfe39 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-10-21T12:14:43Z (GMT) No. of bitstreams: 1 DissGIF.pdf: 2443815 bytes, checksum: 100e28390f0b9b6780e2b2ce9aedfe39 (MD5) / Made available in DSpace on 2016-10-21T12:14:51Z (GMT). No. of bitstreams: 1 DissGIF.pdf: 2443815 bytes, checksum: 100e28390f0b9b6780e2b2ce9aedfe39 (MD5) Previous issue date: 2016-09-17 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / This paper presents an educational sequence for the Geometry classes, which explores the concept of similarity, focusing on the variation of the similarity ratio between linear measurement, areas measurements and volume of some polyhedrons. The problematic situation in this case involves a comparison between the prices of different popcorn packaging sizes in Bauru ́s movie theaters and its area. / Este trabalho apresenta uma sequência didática para aulas de Geometria abordando o conceito de semelhança com foco na variação da razão de semelhança entre medidas lineares e medidas de áreas e de volumes de alguns poliedros, tendo como situação problema a comparação de preços de diversos tamanhos de embalagens de pipocas vendidas em salas de cinema da região de Bauru.

Every single day, lots of users actively participate in social media sites (e.g., Facebook, YouTube, Last.fm, Flicker, etc.) upload photos, videos, share bookmarks, write blogs and annotate/comment on content provided by others. With the recent proliferation of social media sites, users are overwhelmed by the huge amount of available content. Therefore, organizing and retrieving appropriate multimedia content is becoming an increasingly important and challenging task. This challenging task led a number of research communities to concentrate on social tagging systems (also known as folksonomy) that allow users to freely annotate their media items (e.g., music, images, or video) with any sort of arbitrary words, referred to as tags. Tags assist users to organize their own content, as well as to find relevant content shared by other users. In this thesis, we first analyze how useful a folksonomy is for improving personalized services such as tag recommendation, tag-based search and item annotation. We then propose two new algorithms for social media retrieval and tag recommendation respectively. The first algorithm computes the latent preferences of tags for users from other similar tags, as well as latent annotations of tags for items from other similar items. We then seamlessly map the tags onto items, depending on an individual user’s query, to find the most desirable content relevant to the user’s needs. The second algorithm improves tag-recommendation and item annotation by adapting the Katz measure, a path-ensemble based proximity measure, for the use in social tagging systems. In this algorithm we model folksonomy as a weighted, undirected tripartite graph. We then apply the Katz measure to this graph, and exploit it to provide personalized tag recommendation for individual users. We evaluate our algorithms on two real-world folksonomies collected from Last.fm and CiteULike. The experimental results demonstrate that the proposed algorithms improve the search and the recommendation performance, and obtain significant gains in cold start situations where relatively little information is known about a user or an item