Geometric Generalizations of the Power of Two Choices

A well-known paradigm for load balancing in distributed systems is the``power of two choices,''whereby an item is stored at the less loaded of two (or more) random alternative servers. We investigate the power of two choices in natural settings for distributed computing where items and servers reside in a geometric space and each item is associated with the server that is its nearest neighbor. This is in fact the backdrop for distributed hash tables such as Chord, where the geometric space is determined by clockwise distance on a one-dimensional ring. Theoretically, we consider the following load balancing problem. Suppose that servers are initially hashed uniformly at random to points in the space. Sequentially, each item then considers d candidate insertion points also chosen uniformly at random from the space,and selects the insertion point whose associated server has the least load. For the one-dimensional ring, and for Euclidean distance on the two-dimensional torus, we demonstrate that when n data items are hashed to n servers,the maximum load at any server is log log n / log d + O(1) with high probability. While our results match the well-known bounds in the standard setting in which each server is selected equiprobably, our applications do not have this feature, since the sizes of the nearest-neighbor regions around servers are non-uniform. Therefore, the novelty in our methods lies in developing appropriate tail bounds on the distribution of nearest-neighbor region sizes and in adapting previous arguments to this more general setting. In addition, we provide simulation results demonstrating the load balance that results as the system size scales into the millions.

Database Indexing Methods for 3D Hand Pose Estimation

Estimation of 3D hand pose is useful in many gesture recognition applications, ranging from human-computer interaction to automated recognition of sign languages. In this paper, 3D hand pose estimation is treated as a database indexing problem. Given an input image of a hand, the most similar images in a large database of hand images are retrieved. The hand pose parameters of the retrieved images are used as estimates for the hand pose in the input image. Lipschitz embeddings of edge images into a Euclidean space are used to improve the efficiency of database retrieval. In order to achieve interactive retrieval times, similarity queries are initially performed in this Euclidean space. The paper describes ongoing work that focuses on how to best choose reference images, in order to improve retrieval accuracy.

BoostMap: A Method for Efficient Approximate Similarity Rankings

This paper introduces BoostMap, a method that can significantly reduce retrieval time in image and video database systems that employ computationally expensive distance measures, metric or non-metric. Database and query objects are embedded into a Euclidean space, in which similarities can be rapidly measured using a weighted Manhattan distance. Embedding construction is formulated as a machine learning task, where AdaBoost is used to combine many simple, 1D embeddings into a multidimensional embedding that preserves a significant amount of the proximity structure in the original space. Performance is evaluated in a hand pose estimation system, and a dynamic gesture recognition system, where the proposed method is used to retrieve approximate nearest neighbors under expensive image and video similarity measures. In both systems, BoostMap significantly increases efficiency, with minimal losses in accuracy. Moreover, the experiments indicate that BoostMap compares favorably with existing embedding methods that have been employed in computer vision and database applications, i.e., FastMap and Bourgain embeddings.

On trip planning queries in spatial databases

In this paper we discuss a new type of query in Spatial Databases, called Trip Planning Query (TPQ). Given a set of points P in space, where each point belongs to a category, and given two points s and e, TPQ asks for the best trip that starts at s, passes through exactly one point from each category, and ends at e. An example of a TPQ is when a user wants to visit a set of different places and at the same time minimize the total travelling cost, e.g. what is the shortest travelling plan for me to visit an automobile shop, a CVS pharmacy outlet, and a Best Buy shop along my trip from A to B? The trip planning query is an extension of the well-known TSP problem and therefore is NP-hard. The difficulty of this query lies in the existence of multiple choices for each category. In this paper, we first study fast approximation algorithms for the trip planning query in a metric space, assuming that the data set fits in main memory, and give the theory analysis of their approximation bounds. Then, the trip planning query is examined for data sets that do not fit in main memory and must be stored on disk. For the disk-resident data, we consider two cases. In one case, we assume that the points are located in Euclidean space and indexed with an Rtree. In the other case, we consider the problem of points that lie on the edges of a spatial network (e.g. road network) and the distance between two points is defined using the shortest distance over the network. Finally, we give an experimental evaluation of the proposed algorithms using synthetic data sets generated on real road networks.

Verification with Natural Contexts: Soundness of Safe Compositional Network Sketches

In research areas involving mathematical rigor, there are numerous benefits to adopting a formal representation of models and arguments: reusability, automatic evaluation of examples, and verification of consistency and correctness. However, accessibility has not been a priority in the design of formal verification tools that can provide these benefits. In earlier work [30] we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. In this report we evaluate our proposed design criteria by utilizing within the context of novel research a formal reasoning system that is designed according to these criteria. In particular, we consider how the design and capabilities of the formal reasoning system that we employ influence, aid, or hinder our ability to accomplish a formal reasoning task – the assembly of a machine-verifiable proof pertaining to the NetSketch formalism. NetSketch is a tool for the specification of constrained-flow applications and the certification of desirable safety properties imposed thereon. NetSketch is conceived to assist system integrators in two types of activities: modeling and design. It provides capabilities for compositional analysis based on a strongly-typed domain-specific language (DSL) for describing and reasoning about constrained-flow networks and invariants that need to be enforced thereupon. In a companion paper [13] we overview NetSketch, highlight its salient features, and illustrate how it could be used in actual applications. In this paper, we define using a machine-readable syntax major parts of the formal system underlying the operation of NetSketch, along with its semantics and a corresponding notion of validity. We then provide a proof of soundness for the formalism that can be partially verified using a lightweight formal reasoning system that simulates natural contexts. A traditional presentation of these definitions and arguments can be found in the full report on the NetSketch formalism [12].

Lightweight Formal Verification in Classroom Instruction of Reasoning about Functional Code

In college courses dealing with material that requires mathematical rigor, the adoption of a machine-readable representation for formal arguments can be advantageous. Students can focus on a specific collection of constructs that are represented consistently. Examples and counterexamples can be evaluated. Assignments can be assembled and checked with the help of an automated formal reasoning system. However, usability and accessibility do not have a high priority and are not addressed sufficiently well in the design of many existing machine-readable representations and corresponding formal reasoning systems. In earlier work [Lap09], we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. We report on our attempt to evaluate our proposed design criteria by deploying within the classroom a lightweight formal verification system designed according to these criteria. The lightweight formal verification system was used within the instruction of a common application of formal reasoning: proving by induction formal propositions about functional code. We present all of the formal reasoning examples and assignments considered during this deployment, most of which are drawn directly from an introductory text on functional programming. We demonstrate how the design of the system improves the effectiveness and understandability of the examples, and how it aids in the instruction of basic formal reasoning techniques. We make brief remarks about the practical and administrative implications of the system’s design from the perspectives of the student, the instructor, and the grader.

Efficient Support for Common Relations in Lightweight Formal Reasoning Systems

In work that involves mathematical rigor, there are numerous benefits to adopting a representation of models and arguments that can be supplied to a formal reasoning or verification system: reusability, automatic evaluation of examples, and verification of consistency and correctness. However, accessibility has not been a priority in the design of formal verification tools that can provide these benefits. In earlier work [Lap09a], we attempt to address this broad problem by proposing several specific design criteria organized around the notion of a natural context: the sphere of awareness a working human user maintains of the relevant constructs, arguments, experiences, and background materials necessary to accomplish the task at hand. This work expands one aspect of the earlier work by considering more extensively an essential capability for any formal reasoning system whose design is oriented around simulating the natural context: native support for a collection of mathematical relations that deal with common constructs in arithmetic and set theory. We provide a formal definition for a context of relations that can be used to both validate and assist formal reasoning activities. We provide a proof that any algorithm that implements this formal structure faithfully will necessary converge. Finally, we consider the efficiency of an implementation of this formal structure that leverages modular implementations of well-known data structures: balanced search trees and transitive closures of hypergraphs.

Efficient Nearest Neighbor Classification Using a Cascade of Approximate Similarity Measures

Nearest neighbor classification using shape context can yield highly accurate results in a number of recognition problems. Unfortunately, the approach can be too slow for practical applications, and thus approximation strategies are needed to make shape context practical. This paper proposes a method for efficient and accurate nearest neighbor classification in non-Euclidean spaces, such as the space induced by the shape context measure. First, a method is introduced for constructing a Euclidean embedding that is optimized for nearest neighbor classification accuracy. Using that embedding, multiple approximations of the underlying non-Euclidean similarity measure are obtained, at different levels of accuracy and efficiency. The approximations are automatically combined to form a cascade classifier, which applies the slower approximations only to the hardest cases. Unlike typical cascade-of-classifiers approaches, that are applied to binary classification problems, our method constructs a cascade for a multiclass problem. Experiments with a standard shape data set indicate that a two-to-three order of magnitude speed up is gained over the standard shape context classifier, with minimal losses in classification accuracy.

Learning Embeddings for Indexing, Retrieval, and Classification, with Applications to Object and Shape Recognition in Image Databases

Nearest neighbor retrieval is the task of identifying, given a database of objects and a query object, the objects in the database that are the most similar to the query. Retrieving nearest neighbors is a necessary component of many practical applications, in fields as diverse as computer vision, pattern recognition, multimedia databases, bioinformatics, and computer networks. At the same time, finding nearest neighbors accurately and efficiently can be challenging, especially when the database contains a large number of objects, and when the underlying distance measure is computationally expensive. This thesis proposes new methods for improving the efficiency and accuracy of nearest neighbor retrieval and classification in spaces with computationally expensive distance measures. The proposed methods are domain-independent, and can be applied in arbitrary spaces, including non-Euclidean and non-metric spaces. In this thesis particular emphasis is given to computer vision applications related to object and shape recognition, where expensive non-Euclidean distance measures are often needed to achieve high accuracy. The first contribution of this thesis is the BoostMap algorithm for embedding arbitrary spaces into a vector space with a computationally efficient distance measure. Using this approach, an approximate set of nearest neighbors can be retrieved efficiently - often orders of magnitude faster than retrieval using the exact distance measure in the original space. The BoostMap algorithm has two key distinguishing features with respect to existing embedding methods. First, embedding construction explicitly maximizes the amount of nearest neighbor information preserved by the embedding. Second, embedding construction is treated as a machine learning problem, in contrast to existing methods that are based on geometric considerations. The second contribution is a method for constructing query-sensitive distance measures for the purposes of nearest neighbor retrieval and classification. In high-dimensional spaces, query-sensitive distance measures allow for automatic selection of the dimensions that are the most informative for each specific query object. It is shown theoretically and experimentally that query-sensitivity increases the modeling power of embeddings, allowing embeddings to capture a larger amount of the nearest neighbor structure of the original space. The third contribution is a method for speeding up nearest neighbor classification by combining multiple embedding-based nearest neighbor classifiers in a cascade. In a cascade, computationally efficient classifiers are used to quickly classify easy cases, and classifiers that are more computationally expensive and also more accurate are only applied to objects that are harder to classify. An interesting property of the proposed cascade method is that, under certain conditions, classification time actually decreases as the size of the database increases, a behavior that is in stark contrast to the behavior of typical nearest neighbor classification systems. The proposed methods are evaluated experimentally in several different applications: hand shape recognition, off-line character recognition, online character recognition, and efficient retrieval of time series. In all datasets, the proposed methods lead to significant improvements in accuracy and efficiency compared to existing state-of-the-art methods. In some datasets, the general-purpose methods introduced in this thesis even outperform domain-specific methods that have been custom-designed for such datasets.

The corporate social responsibility movement and law's empire: Is there a conflict?

At the heart of corporate governance and social responsibility discourse is recognition of the fact that the modern corporation is primarily governed by the profit maximisation imperative coupled with moral and ethical concerns that such a limited imperative drives the actions of large and wealthy corporations which have the ability to act in influential and significant ways, shaping how our social world is experienced. The actions of the corporation and its management will have a wide sphere of impact over all of its stakeholders whether these are employees, shareholders, consumers or the community in which the corporation is located. As globalisation has become central to the way we think it is also clear that ‘community’ has an ever expanding meaning which may include workers and communities living very far away from Corporate HQ. In recent years academic commentators have become increasingly concerned about the emphasis on what can be called short-term profit maximisation and the perception that this extremist interpretation of the profit imperative results in morally and ethically unacceptable outcomes.1 Hence demands for more corporate social responsibility. Following Cadbury’s2 classification of corporate social responsibility into three distinct areas, this paper will argue that once the legally regulated tier is left aside corporate responsibility can become so nebulous as to be relatively meaningless. The argument is not that corporations should not be required to act in socially responsible ways but that unless supported by regulation, which either demands high standards, or at the very least incentivises the attainment of such standards such initiatives are doomed to failure. The paper will illustrate by reference to various chosen cases that law’s discourse has already signposted ways to consider and resolve corporate governance problems in the broader social responsibility context.3 It will also illustrate how corporate responsibility can and must be supported by legal measures. Secondly, this paper will consider the potential conflict between an emphasis on corporate social responsibility and the regulatory approach.4 Finally, this paper will place the current interest in corporate social responsibility within the broader debate on the relationship between law and non-legally enforceable norms and will present some reflections on the norm debate arising from this consideration of the CSR movement.

Language legislation in Ireland and the United Kingdom: Exploring the gaps between theory and practice

The central objective in this thesis is to explore the gaps between the normative justifications advanced for language rights and language legislative protection and the effective realisation of those rights and legislative provisions in practice. This objective is achieved by examining the scope and application of language rights and legislative provisions within language legislation in Ireland and the United Kingdom. Drawing on Canadian jurisprudence advocating for language rights to be recognised as “purposeful”, the thesis considers the extent to which Ireland and the United Kingdom have limited the acceptance of positive obligations as they relate to the provision of language services in the public sphere. In arguing that language rights are distinct in nature, the thesis suggests that in order for language rights to be effectively realised, an approach to language rights and language legislation more generally must be underpinned by a substantive vision of equality, otherwise language rights and legislative provisions merely amount to symbolic recognition and vacuous rhetoric as opposed to being substantive and enabling rights and provisions. Having said that, the thesis also recognises and elucidates the practical difficulties that arise in the realisation of language rights and language legislative provisions and in doing so seeks to stimulate further dialogue about the nature and limits of language rights and language legislation.

Theme and variations: Christianity and regional landscapes in early medieval Ireland

This thesis explores the impact of Christianity on the landscape in Ireland from the conversion period to the coming of the Anglo-Normans. The premise is that ecclesiastical and secular settlement formed a cohesive whole which characterised the societal organisation of early medieval Ireland. The matter of the thesis is to isolate some of the agents of cohesion to see was this homogenous or did it vary in different areas. One of these agents was the ownership of land and the thesis undertakes to identify ecclesiastical landholding and examine the manner of settlement on it. A corollary is to explore the contribution of the genealogical link between kin-group, founding saint and territory to the construction of local identities. This necessitated a narrow focus; thus small study areas were chosen, which approximated to early medieval kingdoms in North Louth, Rathdown, Co Dublin and Ross, Co Cork. A multidisciplinary approach was taken using both archaeological and documentary evidence. The thesis found ecclesiastical sites were at the same density through the study areas, but there were considerable regional variations in related secular settlement. Ecclesiastical estates were identified in the three study areas and common settlement patterns were found in two of them. Settlement in all areas indicated the foundation of minor churches by local groups. Ecclesiastical sites were found to be integral to kin-group identity and status, but the manner in which each group negotiated this, was very different. Finally the thesis examined material evidence for a change from diffused to concentrated power in the political organisation of Irish society, a process entwined with developments of the Viking Age. This centralisation of power and associated re-formation of identity was still often mediated through the ecclesiastical sphere but the thesis demonstrates diversity in the materialising of the mediation.

A cultural study on communication and technology with specific reference to media in China

This dissertation examines the role of communications technology in social change. It examines secondary data on contemporary China arguing that many interpretations of events in China are unsuitable at best and at worst conceptually damages our understanding of social change in China. This is especially the case in media studies under the ‘democratic framework’. It proposes that there is an alternative framework in studying the media and social change. This alternative conceptual framework is termed a zone of interpretative development offering a means by which to discuss events that take place in a mediated environment. Taking a theoretical foundation using the philosophy of Mikhail Bakhtin this dissertation develops a platform with which to understand communication technology from an anthropological perspective. Three media events from contemporary China are examined. The first examines the Democracy Wall event and the implications of using a public sphere framework. The second case examines the phenomenon of the Grass Mud Horse, a symbol that has gained popular purchase as a humorous expression of political dissatisfaction and develops the problems seen in the first case but with some solutions. Using a modification of Lev Vygotskiĭ’s zone of proximal development this symbol is understood as an expression of the collective recognition of a shared experience. In the second example from the popular TV talent show contests in China further expressions of collective experience are introduced. With the evidence from these media events in contemporary China this dissertation proposes that we can understand certain modes of communication as occurring in a zone of interpretative development. This proposed anthropological feature of social change via communication and technology can fruitfully describe meaning-formation in society via the expression and recognition of shared experiences.

Caring for the Celtic cubs: Discursive constructions of mothers and mothering in the Irish childcare debate

Drawing on an understanding of the public sphere as a multiplicity of communicative and discursive spaces this paper examines the constructions of mothers, mothering and motherhood which emerged in recent debates about childcare in Ireland. Preliminary analysis of these discursive constructions suggest that they are often based on rhetoric, informed by stereotypical assumptions and rooted in frames of reference which mitigate against the emergence of alternative ways of understanding the issues of mothering and childcare. It will be argued that the reductionist and divisive nature of the childcare debate which ensued prior to the 2005 budget, stymied childcare policy development at a time when its unprecedented prominence on the political agenda and the strength of public finances could have underpinned a shift in policy approach. The paper concludes with an exploration of the ways in which feminist scholarship can challenge the Irish model of childcare policy, which continues to be premised on an understanding of childcare and the reconciliation of work and family life as the privatised responsibility of individual women.

Formation and characterisation of ordered porous vanadium oxide inverse opal materials for Li-ion batteries

This thesis presents several routes towards achieving artificial opal templates by colloidal self-assembly of polystyrene (PS) or poly(methyl methacrylate) (PMMA) spheres and the use of these template for the fabrication of V2O5 inverse opals as cathode materials for lithium ion battery applications. First, through the manipulation of different experimental factors, several methods of affecting or directing opal growth towards realizing different structures, improving order and/or achieving faster formation on a variety of substrates are presented. The addition of the surfactant sodium dodecyl sulphate (SDS) at a concentration above the critical micelle concentration for SDS to a 5 wt% solution of PMMA spheres before dip-coating is presented as a method of achieving ordered 2D PhC monolayers on hydrophobic Au-coated silicon substrates at fast and slow rates of withdrawal. The effect that the degree of hydrophilicity of glass substrates has on the ordering of PMMA spheres is next investigated for a slow rate of withdrawal under noise agitation. Heating of the colloidal solution is also presented as a means of affecting order and thickness of opal deposits formed using fast rate dip coating. E-beam patterned substrates are shown as a means of altering the thermodynamically favoured FCC ordering of polystyrene spheres (PS) when dip coated at slow rate. Facile routes toward the synthesis of ordered V2O5 inverse opals are presented with direct infiltration of polymer sphere templates using liquid precursor. The use of different opal templates, both 2D and 3D partially ordered templates, is compared and the composition and arrangement of the subsequent IO structures post infiltration and calcination for various procedures is characterised. V2O5 IOs are also synthesised by electrodeposition from an aqueous VOSO4 solution at constant voltage. Electrochemical characterisation of these structures as cathode material for Li-ion batteries is assessed in a half cell arrangement for samples deposited on stainless steel foil substrates. Improved rate capabilities are demonstrated for these materials over bulk V2O5, with the improvement attributed to the shorter Li ion diffusion distances and increased electrolyte infiltration provided by the IO structure.