Thesis (M.Eng.(Electronic Engineering))--University of Pretoria, 1999. / Summaries in Afrikaans and English. Includes bibliographical references.

Thesis (M.S.)--Rochester Institute of Technology, 2009. / Typescript. Includes bibliographical references.

Social networks have been used to understand how information flows through an organization as well as identifying individuals that appear to have control over this information flow. Such individuals are identified as being central nodes in a graph representation of the social network and have high "betweenness" values. Rather than looking at graphs derived from email, on-line forums, or telephone connections, we consider sequences of bipartite graphs that represent face-to-face meetings between individuals, and define a new metric to identify the information elite individuals. We show that, in our simulations, individuals that attend many meetings with many different people do not always have high betweenness values, even though they seem to be the ones that control the information flow. / Singapore-MIT Alliance (SMA)

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

Coherent and consistent tracking of provenance data and in particular update history information is a crucial building block for any serious information system architecture. Version Control Systems can be a part of such an architecture enabling users to query and manipulate versioning information as well as content revisions. In this paper, we introduce an RDF versioning approach as a foundation for a full featured RDF Version Control System. We argue that such a system needs support for all concepts of the RDF specification including support for RDF datasets and blank nodes. Furthermore, we placed special emphasis on the protection against unperceived history manipulation by hashing the resulting patches. In addition to the conceptual analysis and an RDF vocabulary for representing versioning information, we present a mature implementation which captures versioning information for changes to arbitrary RDF datasets.

Vorlesungsinhalte: Mehrwegebäume (B-Bäume, B*-Bäume) inkl. digitalen Suchbäumen, Hashing, Graphenalgorithmen sowie Suche in Texten.

1. Einführung - Komplexität von Algorithmen - Bestimmung der Zeitkomplexität - Das Prinzip 'Teile und Herrsche' 2. Einfache Suchverfahren (Arrays) 3. Verkette Listen, Stacks und Schlangen 4. Sortierverfahren - Elementare Verfahren - Shell-Sort, Heap-Sort, Quick-Sort - Externe Sortierverfahren 5. Allgemeine Bäume und Binärbäume - Orientierte und geordnete Bäume - Binärbäume (Darstellung, Traversierung) 6. Binäre Suchbäume 7. Mehrwegbäume

We have found an operation between permutations in the symmetric group Sn upon which we have experimentally derived results that can be linked to desirable properties in cryptography, mainly in the domain of one-way functions. From it, we have implemented a beta version of an algorithm for a hashing function by exploiting the operation’s low computational cost for speed and its properties for security. Its design makes it resistant to length extension attacks and the encoding of blocks into permutations suggests that any differential cryptanalysis technique that is based on bit conditions should be useless against it. More precisely, when measuring the evolution of differences in the compression function, bit-based distances such as the exclusive-or distance should be replaced by another type of distance, still to be determined in future research. In this work we will present the algorithm and introduce a new framework of cryptanalysis for collision and preimage attacks in order to somehow measure its security. Once this is done, we will run comparison tests against MD5 and SHA256 in order to externally evaluate our algorithm in terms of speed, weaknesses and strength.

L’objectif principal de cette thèse est la découverte d’objets visuels fréquents dans de grandes collections multimédias (images ou vidéos). Comme dans de nombreux domaines (finance, génétique, . . .), il s’agit d’extraire une connaissance de manière automatique ou semi-automatique en utilisant la fréquence d’apparition d’un objet au sein d’un corpus comme critère de pertinence. Une première contribution de la thèse est de fournir un formalisme aux problèmes de découverte et de fouille d’instances d’objets visuels fréquents. La deuxième contribution de la thèse est une méthode générique de résolution de ces deux types de problème reposant d’une part sur un processus itératif d’échantillonnage d’objets candidats et d’autre part sur une méthode efficace d’appariement d’objets rigides à large échelle. La troisième contribution de la thèse s’attache à construire une fonction de vraisemblance s’approchant au mieux de la distribution parfaite, tout en restant scalable et efficace. Les expérimentations montrent que contrairement aux méthodes de l’état de l’artnotre approche permet de découvrir efficacement des objets de très petite taille dans des millions d’images. Pour finir, plusieurs scénarios d’exploitation des graphes visuels produits par notre méthode sont proposées et expérimentés. Ceci inclut la détection d’évènements médiatiques transmédias et la suggestion de requêtes visuelles. / The main goal of this thesis is to discover frequent visual objects in large multimedia collections. As in many areas (finance, genetics, . . .), it consists in extracting a knowledge, using the occurence frequency of an object in a collection as a relevance criterion. A first contribution is to provide a formalism to the problems of mining and discovery of frequent visual objects. The second contribution is a generic method to solve these two problems, based on an iterative sampling process, and on an efficient and scalable rigid objects matching. The third contribution of this work focuses on building a likelihood function close to the perfect distribution. Experiments show that contrary to state-of-the-art methods, our approach allows to discover efficiently very small objects in several millions images. Finally, several applications are presented, including trademark logos discovery, transmedia events detection or visual-based query suggestion.

Background: Data analysis for biomedical research often requires a record linkage step to identify records from multiple data sources referring to the same person. Due to the lack of unique personal identifiers across these sources, record linkage relies on the similarity of personal data such as first and last names or birth dates. However, the exchange of such identifying data with a third party, as is the case in record linkage, is generally subject to strict privacy requirements. This problem is addressed by privacy-preserving record linkage (PPRL) and pseudonymization services. Mainzelliste is an open-source record linkage and pseudonymization service used to carry out PPRL processes in real-world use cases. Methods: We evaluate the linkage quality and performance of the linkage process using several real and near-real datasets with different properties w.r.t. size and error-rate of matching records. We conduct a comparison between (plaintext) record linkage and PPRL based on encoded records (Bloom filters). Furthermore, since the Mainzelliste software offers no blocking mechanism, we extend it by phonetic blocking as well as novel blocking schemes based on locality-sensitive hashing (LSH) to improve runtime for both standard and privacy-preserving record linkage. Results: The Mainzelliste achieves high linkage quality for PPRL using field-level Bloom filters due to the use of an error-tolerant matching algorithm that can handle variances in names, in particular missing or transposed name compounds. However, due to the absence of blocking, the runtimes are unacceptable for real use cases with larger datasets. The newly implemented blocking approaches improve runtimes by orders of magnitude while retaining high linkage quality. Conclusion: We conduct the first comprehensive evaluation of the record linkage facilities of the Mainzelliste software and extend it with blocking methods to improve its runtime. We observed a very high linkage quality for both plaintext as well as encoded data even in the presence of errors. The provided blocking methods provide order of magnitude improvements regarding runtime performance thus facilitating the use in research projects with large datasets and many participants.