Algorithms for Geometric Matching, Clustering, and Covering

With the popularization of GPS-enabled devices such as mobile phones, location data are becoming available at an unprecedented scale. The locations may be collected from many different sources such as vehicles moving around a city, user check-ins in social networks, and geo-tagged micro-blogging photos or messages. Besides the longitude and latitude, each location record may also have a timestamp and additional information such as the name of the location. Time-ordered sequences of these locations form trajectories, which together contain useful high-level information about people's movement patterns.

The first part of this thesis focuses on a few geometric problems motivated by the matching and clustering of trajectories. We first give a new algorithm for computing a matching between a pair of curves under existing models such as dynamic time warping (DTW). The algorithm is more efficient than standard dynamic programming algorithms both theoretically and practically. We then propose a new matching model for trajectories that avoids the drawbacks of existing models. For trajectory clustering, we present an algorithm that computes clusters of subtrajectories, which correspond to common movement patterns. We also consider trajectories of check-ins, and propose a statistical generative model, which identifies check-in clusters as well as the transition patterns between the clusters.

The second part of the thesis considers the problem of covering shortest paths in a road network, motivated by an EV charging station placement problem. More specifically, a subset of vertices in the road network are selected to place charging stations so that every shortest path contains enough charging stations and can be traveled by an EV without draining the battery. We first introduce a general technique for the geometric set cover problem. This technique leads to near-linear-time approximation algorithms, which are the state-of-the-art algorithms for this problem in either running time or approximation ratio. We then use this technique to develop a near-linear-time algorithm for this

shortest-path cover problem.

A Philosophy of Operatic Storytelling

This dissertation presents the first theoretical model for understanding narration and point of view in opera, examining repertoire from Richard Wagner to Benjamin Britten. Prior music scholarship on musical narratives and narrativity has drawn primarily on continental literary theory and philosophy of the 1960s to the middle of the 1980s. This study, by contrast, engages with current debates in the analytic branch of aesthetic philosophy. One reason why the concept of point of view has not been more extensively explored in opera studies is the widespread belief that operas are not narratives. This study questions key premises on which this assumption rests. In so doing, it presents a new definition of narrative. Arguably, a narrative is an utterance intended to communicate a story, where "story" is understood to involve the representation of a particular agent or agents exercising their agency. This study explores the role of narrators in opera, introducing the first taxonomy of explicit fictional operatic narrators. Through a close analysis of Britten and Myfanwy Piper's Owen Wingrave, it offers an explanation of music's power to orient spectators to the points of view of opera characters by providing audiences with access to characters' perceptual experiences and cognitive, affective, and psychological states. My analysis also helps account for how our subjective access to fictional characters may engender sympathy for them. The second half of the dissertation focuses on opera in performance. Current thinking in music scholarship predominantly holds that fidelity is an outmoded concern. I argue that performing a work-for-performance is a matter of intentionally modelling one's performance on the work-for-performance's features and achieving a moderate degree of fidelity or matching between the two. Finally, this study investigates how the creative decisions of the performers and director impact the point of view from which an opera is told.

Reconfigurable Matching Networks for RF Amplifiers

This article presents applications of reconfigurable matching networks for RF amplifier design. Two possible solutions are given, one where the switching element is a PIN diode, and the other is based on graphene. Due to the fact that its conductivity depends on applied bias voltage, the graphene-based circuits can be used in microwave circuits as controllable elements. The structure of the proposed switch is very simple and it is particularly convenient for microstrip-based circuits. Because of that, a design of reconfigurable amplifier with the graphene-based switch is presented together with the one which has the PIN diode switch. Both amplifiers have the same specifications, and the one with the PIN diode switch is fabricated. The amplifier utilizing the PIN switch was used as a reference to make a comparison the two types of switches. Results of both amplifiers are very similar which indicates possible future applications of the graphene-based switch.

Language, Logos, and Social Ontology: Naturalist and Post-Naturalist Narratives of Human Rationality and Social Reality

I distinguish two ways that philosophers have approached and explained the reality and status of human social institutions. I call these approaches “naturalist” and “post-naturalist”. Common to both approaches is an understanding that the status of mind and its relation to the world or “nature” has implications on a conception of the status of institutional reality. Naturalists hold that mind is explicable within a scientific frame that conceives of mind as a fundamentally material process. By proxy, social reality is also materially explicable. Post-naturalists critique this view, holding instead that naturalism is parasitic on contemporary science—it therefore is non-compulsory and distorts how we ought to understand mind and social reality. A comparison of naturalism and post-naturalism will comprise the content of the first chapter. The second chapter turns to tracing out the dimensions of a post-naturalist narrative of mind and social reality. Post-naturalists conceive of mind and its activity of thought as sui generis, and it transpires from this that social institutions are better understood as a rational mind’s mode of the expression in the world. Post-naturalism conceives of social reality as a necessary dimension of thought. Thought requires a second person and thereby a tradition or context of norms that come to both structure its expression and become the products of expression. This is in contrast to the idea that social reality is a production of minds, and thereby derivative. Social reality, self-conscious thought, and thought of the second person are therefore three dimensions of a greater unity.

Recommending peers for learning: Matching on dissimilarity in interpretations to provoke breakdown

People recommenders are a widespread feature of social networking sites and educational social learning platforms alike. However, when these systems are used to extend learners’ Personal Learning Networks, they often fall short of providing recommendations of learning value to their users. This paper proposes a design of a people recommender based on content-based user profiles, and a matching method based on dissimilarity therein. It presents the results of an experiment conducted with curators of the content curation site Scoop.it!, where curators rated personalized recommendations for contacts. The study showed that matching dissimilarity of interpretations of shared interests is more successful in providing positive experiences of breakdown for the curator than is matching on similarity. The main conclusion of this paper is that people recommenders should aim to trigger constructive experiences of breakdown for their users, as the prospect and potential of such experiences encourage learners to connect to their recommended peers.

Flexibele Leerroutes voor Propedeusestudenten: Grounded Theory Onderzoek naar het Identificeren van Studentkenmerken in de Matching, ten behoeve van een Vraaggerichte, Gepersonaliseerde Leerroute in de Propedeuse Social Work

De Groot, D. (2016). Flexibele Leerroutes voor Propedeusestudenten: Grounded Theory Onderzoek naar het Identificeren van Studentkenmerken in de Matching, ten behoeve van een Vraaggerichte, Gepersonaliseerde Leerroute in de Propedeuse Social Work. Juli, 26, 2016, Heerlen, Nederland: Open Universiteit.

Combining Taxonomies using Word2vec

Taxonomies have gained a broad usage in a variety of fields due to their extensibility, as well as their use for classification and knowledge organization. Of particular interest is the digital document management domain in which their hierarchical structure can be effectively employed in order to organize documents into content-specific categories. Common or standard taxonomies (e.g., the ACM Computing Classification System) contain concepts that are too general for conceptualizing specific knowledge domains. In this paper we introduce a novel automated approach that combines sub-trees from general taxonomies with specialized seed taxonomies by using specific Natural Language Processing techniques. We provide an extensible and generalizable model for combining taxonomies in the practical context of two very large European research projects. Because the manual combination of taxonomies by domain experts is a highly time consuming task, our model measures the semantic relatedness between concept labels in CBOW or skip-gram Word2vec vector spaces. A preliminary quantitative evaluation of the resulting taxonomies is performed after applying a greedy algorithm with incremental thresholds used for matching and combining topic labels.

The Pennsylvania Adoption Exchange Improves Its Matching Process

The Pennsylvania Adoption Exchange (PAE) helps case workers who represent children in state custody by recommending prospective families for adoption. We describe PAE's operational challenges using case worker surveys and analyze child outcomes through a regression analysis of data collected over multiple years. A match recommendation spreadsheet tool implemented by PAE incorporates insights from this analysis and allows PAE managers to better utilize available information. Using a discrete-event simulation of PAE, we justify the value of a statewide adoption network and demonstrate the importance of better information about family preferences for increasing the percentage of children who are successfully adopted. Finally, we detail a series of simple improvements that PAE achieved through collecting more valuable information and aligning incentives for families to provide useful preference information.

Leveraging Multiple Features for Image Retrieval and Matching

The goal of image retrieval and matching is to find and locate object instances in images from a large-scale image database. While visual features are abundant, how to combine them to improve performance by individual features remains a challenging task. In this work, we focus on leveraging multiple features for accurate and efficient image retrieval and matching. We first propose two graph-based approaches to rerank initially retrieved images for generic image retrieval. In the graph, vertices are images while edges are similarities between image pairs. Our first approach employs a mixture Markov model based on a random walk model on multiple graphs to fuse graphs. We introduce a probabilistic model to compute the importance of each feature for graph fusion under a naive Bayesian formulation, which requires statistics of similarities from a manually labeled dataset containing irrelevant images. To reduce human labeling, we further propose a fully unsupervised reranking algorithm based on a submodular objective function that can be efficiently optimized by greedy algorithm. By maximizing an information gain term over the graph, our submodular function favors a subset of database images that are similar to query images and resemble each other. The function also exploits the rank relationships of images from multiple ranked lists obtained by different features. We then study a more well-defined application, person re-identification, where the database contains labeled images of human bodies captured by multiple cameras. Re-identifications from multiple cameras are regarded as related tasks to exploit shared information. We apply a novel multi-task learning algorithm using both low level features and attributes. A low rank attribute embedding is joint learned within the multi-task learning formulation to embed original binary attributes to a continuous attribute space, where incorrect and incomplete attributes are rectified and recovered. To locate objects in images, we design an object detector based on object proposals and deep convolutional neural networks (CNN) in view of the emergence of deep networks. We improve a Fast RCNN framework and investigate two new strategies to detect objects accurately and efficiently: scale-dependent pooling (SDP) and cascaded rejection classifiers (CRC). The SDP improves detection accuracy by exploiting appropriate convolutional features depending on the scale of input object proposals. The CRC effectively utilizes convolutional features and greatly eliminates negative proposals in a cascaded manner, while maintaining a high recall for true objects. The two strategies together improve the detection accuracy and reduce the computational cost.

Applied web traffic analysis for numerical encoding of SQL Injection attack features.

SQL Injection Attack (SQLIA) remains a technique used by a computer network intruder to pilfer an organisation’s confidential data. This is done by an intruder re-crafting web form’s input and query strings used in web requests with malicious intent to compromise the security of an organisation’s confidential data stored at the back-end database. The database is the most valuable data source, and thus, intruders are unrelenting in constantly evolving new techniques to bypass the signature’s solutions currently provided in Web Application Firewalls (WAF) to mitigate SQLIA. There is therefore a need for an automated scalable methodology in the pre-processing of SQLIA features fit for a supervised learning model. However, obtaining a ready-made scalable dataset that is feature engineered with numerical attributes dataset items to train Artificial Neural Network (ANN) and Machine Leaning (ML) models is a known issue in applying artificial intelligence to effectively address ever evolving novel SQLIA signatures. This proposed approach applies numerical attributes encoding ontology to encode features (both legitimate web requests and SQLIA) to numerical data items as to extract scalable dataset for input to a supervised learning model in moving towards a ML SQLIA detection and prevention model. In numerical attributes encoding of features, the proposed model explores a hybrid of static and dynamic pattern matching by implementing a Non-Deterministic Finite Automaton (NFA). This combined with proxy and SQL parser Application Programming Interface (API) to intercept and parse web requests in transition to the back-end database. In developing a solution to address SQLIA, this model allows processed web requests at the proxy deemed to contain injected query string to be excluded from reaching the target back-end database. This paper is intended for evaluating the performance metrics of a dataset obtained by numerical encoding of features ontology in Microsoft Azure Machine Learning (MAML) studio using Two-Class Support Vector Machines (TCSVM) binary classifier. This methodology then forms the subject of the empirical evaluation.

Validation of AltiKa Matching Pursuit Rain Flag

The major drawback of Ka band, operating frequency of the AltiKa altimeter on board SARAL, is its sensitivity to atmospheric liquid water. Even light rain or heavy clouds can strongly attenuate the signal and distort the signal leading to erroneous geophysical parameters estimates. A good detection of the samples affected by atmospheric liquid water is crucial. As AltiKa operates at a single frequency, a new technique based on the detection by a Matching Pursuit algorithm of short scale variations of the slope of the echo waveform plateau has been developed and implemented prelaunch in the ground segment. As the parameterization of the detection algorithm was defined using Jason-1 data, the parameters were re-estimated during the cal-val phase, during which the algorithm was also updated. The measured sensor signal-to-noise ratio is significantly better than planned, the data loss due to attenuation by rain is significantly smaller than expected (<0.1%). For cycles 2 to 9, the flag detects about 9% of 1Hz data, 5.5% as rainy and 3.5 % as backscatter bloom (or sigma0 bloom). The results of the flagging process are compared to independent rain data from microwave radiometers to evaluate its performances in term of detection and false alarms.

Response toolkit to provide an active response against intrusions using Ontology-Based IRS

Los sistemas de respuesta activa tienen por objetivo ejecutar una respuesta en contra de una intrusión de forma automática. Sin embargo, ejecutar una respuesta automáticamente no es una tarea trivial ya que el costo de ejecutar una respuesta podría ser más grande que el efecto que cause la intrusión propiamente dicha. También, el sistema debe contar con un amplio conjunto de acciones de respuesta y un algoritmo que seleccione la respuesta óptima. Este artículo propone un toolkit de respuestas que será integrado a un IRS basado en Ontologías para permitir la ejecución automática de la mejor respuesta cuando una intrusión es detectada. Se presenta un conjunto de respuestas basadas en host y basadas en red que pueden ser ejecutadas por el IRS, dicha ejecución es llevada a cabo mediante agentes basados en plugins que han sido distribuidos en la red. Finalmente, se realiza la verificación del sistema propuesto, tomando como caso de uso un ataque de defacement obteniéndose resultados satisfactorios.

An ontology for risk management of digital collections

Maintaining accessibility to and understanding of digital information over time is a complex challenge that often requires contributions and interventions from a variety of individuals and organizations. The processes of preservation planning and evaluation are fundamentally implicit and share similar complexity. Both demand comprehensive knowledge and understanding of every aspect of to-be-preserved content and the contexts within which preservation is undertaken. Consequently, means are required for the identification, documentation and association of those properties of data, representation and management mechanisms that in combination lend value, facilitate interaction and influence the preservation process. These properties may be almost limitless in terms of diversity, but are integral to the establishment of classes of risk exposure, and the planning and deployment of appropriate preservation strategies. We explore several research objectives within the course of this thesis. Our main objective is the conception of an ontology for risk management of digital collections. Incorporated within this are our aims to survey the contexts within which preservation has been undertaken successfully, the development of an appropriate methodology for risk management, the evaluation of existing preservation evaluation approaches and metrics, the structuring of best practice knowledge and lastly the demonstration of a range of tools that utilise our findings. We describe a mixed methodology that uses interview and survey, extensive content analysis, practical case study and iterative software and ontology development. We build on a robust foundation, the development of the Digital Repository Audit Method Based on Risk Assessment. We summarise the extent of the challenge facing the digital preservation community (and by extension users and creators of digital materials from many disciplines and operational contexts) and present the case for a comprehensive and extensible knowledge base of best practice. These challenges are manifested in the scale of data growth, the increasing complexity and the increasing onus on communities with no formal training to offer assurances of data management and sustainability. These collectively imply a challenge that demands an intuitive and adaptable means of evaluating digital preservation efforts. The need for individuals and organisations to validate the legitimacy of their own efforts is particularly prioritised. We introduce our approach, based on risk management. Risk is an expression of the likelihood of a negative outcome, and an expression of the impact of such an occurrence. We describe how risk management may be considered synonymous with preservation activity, a persistent effort to negate the dangers posed to information availability, usability and sustainability. Risk can be characterised according to associated goals, activities, responsibilities and policies in terms of both their manifestation and mitigation. They have the capacity to be deconstructed into their atomic units and responsibility for their resolution delegated appropriately. We continue to describe how the manifestation of risks typically spans an entire organisational environment, and as the focus of our analysis risk safeguards against omissions that may occur when pursuing functional, departmental or role-based assessment. We discuss the importance of relating risk-factors, through the risks themselves or associated system elements. To do so will yield the preservation best-practice knowledge base that is conspicuously lacking within the international digital preservation community. We present as research outcomes an encapsulation of preservation practice (and explicitly defined best practice) as a series of case studies, in turn distilled into atomic, related information elements. We conduct our analyses in the formal evaluation of memory institutions in the UK, US and continental Europe. Furthermore we showcase a series of applications that use the fruits of this research as their intellectual foundation. Finally we document our results in a range of technical reports and conference and journal articles. We present evidence of preservation approaches and infrastructures from a series of case studies conducted in a range of international preservation environments. We then aggregate this into a linked data structure entitled PORRO, an ontology relating preservation repository, object and risk characteristics, intended to support preservation decision making and evaluation. The methodology leading to this ontology is outlined, and lessons are exposed by revisiting legacy studies and exposing the resource and associated applications to evaluation by the digital preservation community.

Motion compensation with minimal residue dispersion matching criteria

Dissertação (mestrado)—Universidade de Brasília, Faculdade de Tecnoloigia, 2016.