Indexing Distances in Large Graphs and Applications in Search Tasks

This thesis elaborates on the problem of preprocessing a large graph so that single-pair shortest-path queries can be answered quickly at runtime. Computing shortest paths is a well studied problem, but exact algorithms do not scale well to real-world huge graphs in applications that require very short response time. The focus is on approximate methods for distance estimation, in particular in landmarks-based distance indexing. This approach involves choosing some nodes as landmarks and computing (offline), for each node in the graph its embedding, i.e., the vector of its distances from all the landmarks. At runtime, when the distance between a pair of nodes is queried, it can be quickly estimated by combining the embeddings of the two nodes. Choosing optimal landmarks is shown to be hard and thus heuristic solutions are employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the techniques presented in this thesis is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach which considers selecting landmarks at random. Finally, they are applied in two important problems arising naturally in large-scale graphs, namely social search and community detection.

Fast Shortest Path Distance Estimation in Large Networks

We study the problem of preprocessing a large graph so that point-to-point shortest-path queries can be answered very fast. Computing shortest paths is a well studied problem, but exact algorithms do not scale to huge graphs encountered on the web, social networks, and other applications. In this paper we focus on approximate methods for distance estimation, in particular using landmark-based distance indexing. This approach involves selecting a subset of nodes as landmarks and computing (offline) the distances from each node in the graph to those landmarks. At runtime, when the distance between a pair of nodes is needed, we can estimate it quickly by combining the precomputed distances of the two nodes to the landmarks. We prove that selecting the optimal set of landmarks is an NP-hard problem, and thus heuristic solutions need to be employed. Given a budget of memory for the index, which translates directly into a budget of landmarks, different landmark selection strategies can yield dramatically different results in terms of accuracy. A number of simple methods that scale well to large graphs are therefore developed and experimentally compared. The simplest methods choose central nodes of the graph, while the more elaborate ones select central nodes that are also far away from one another. The efficiency of the suggested techniques is tested experimentally using five different real world graphs with millions of edges; for a given accuracy, they require as much as 250 times less space than the current approach in the literature which considers selecting landmarks at random. Finally, we study applications of our method in two problems arising naturally in large-scale networks, namely, social search and community detection.

Articulated Pose Estimation in a Learned Smooth Space of Feasible Solutions

A learning based framework is proposed for estimating human body pose from a single image. Given a differentiable function that maps from pose space to image feature space, the goal is to invert the process: estimate the pose given only image features. The inversion is an ill-posed problem as the inverse mapping is a one to many process. Hence multiple solutions exist, and it is desirable to restrict the solution space to a smaller subset of feasible solutions. For example, not all human body poses are feasible due to anthropometric constraints. Since the space of feasible solutions may not admit a closed form description, the proposed framework seeks to exploit machine learning techniques to learn an approximation that is smoothly parameterized over such a space. One such technique is Gaussian Process Latent Variable Modelling. Scaled conjugate gradient is then used find the best matching pose in the space of feasible solutions when given an input image. The formulation allows easy incorporation of various constraints, e.g. temporal consistency and anthropometric constraints. The performance of the proposed approach is evaluated in the task of upper-body pose estimation from silhouettes and compared with the Specialized Mapping Architecture. The estimation accuracy of the Specialized Mapping Architecture is at least one standard deviation worse than the proposed approach in the experiments with synthetic data. In experiments with real video of humans performing gestures, the proposed approach produces qualitatively better estimation results.

Spatiotemporal Gesture Segmentation

Spotting patterns of interest in an input signal is a very useful task in many different fields including medicine, bioinformatics, economics, speech recognition and computer vision. Example instances of this problem include spotting an object of interest in an image (e.g., a tumor), a pattern of interest in a time-varying signal (e.g., audio analysis), or an object of interest moving in a specific way (e.g., a human's body gesture). Traditional spotting methods, which are based on Dynamic Time Warping or hidden Markov models, use some variant of dynamic programming to register the pattern and the input while accounting for temporal variation between them. At the same time, those methods often suffer from several shortcomings: they may give meaningless solutions when input observations are unreliable or ambiguous, they require a high complexity search across the whole input signal, and they may give incorrect solutions if some patterns appear as smaller parts within other patterns. In this thesis, we develop a framework that addresses these three problems, and evaluate the framework's performance in spotting and recognizing hand gestures in video. The first contribution is a spatiotemporal matching algorithm that extends the dynamic programming formulation to accommodate multiple candidate hand detections in every video frame. The algorithm finds the best alignment between the gesture model and the input, and simultaneously locates the best candidate hand detection in every frame. This allows for a gesture to be recognized even when the hand location is highly ambiguous. The second contribution is a pruning method that uses model-specific classifiers to reject dynamic programming hypotheses with a poor match between the input and model. Pruning improves the efficiency of the spatiotemporal matching algorithm, and in some cases may improve the recognition accuracy. The pruning classifiers are learned from training data, and cross-validation is used to reduce the chance of overpruning. The third contribution is a subgesture reasoning process that models the fact that some gesture models can falsely match parts of other, longer gestures. By integrating subgesture reasoning the spotting algorithm can avoid the premature detection of a subgesture when the longer gesture is actually being performed. Subgesture relations between pairs of gestures are automatically learned from training data. The performance of the approach is evaluated on two challenging video datasets: hand-signed digits gestured by users wearing short sleeved shirts, in front of a cluttered background, and American Sign Language (ASL) utterances gestured by ASL native signers. The experiments demonstrate that the proposed method is more accurate and efficient than competing approaches. The proposed approach can be generally applied to alignment or search problems with multiple input observations, that use dynamic programming to find a solution.

A novel and miniaturized 433/868MHz multi-band wireless sensor platform for body sensor network applications

Body Sensor Network (BSN) technology is seeing a rapid emergence in application areas such as health, fitness and sports monitoring. Current BSN wireless sensors typically operate on a single frequency band (e.g. utilizing the IEEE 802.15.4 standard that operates at 2.45GHz) employing a single radio transceiver for wireless communications. This allows a simple wireless architecture to be realized with low cost and power consumption. However, network congestion/failure can create potential issues in terms of reliability of data transfer, quality-of-service (QOS) and data throughput for the sensor. These issues can be especially critical in healthcare monitoring applications where data availability and integrity is crucial. The addition of more than one radio has the potential to address some of the above issues. For example, multi-radio implementations can allow access to more than one network, providing increased coverage and data processing as well as improved interoperability between networks. A small number of multi-radio wireless sensor solutions exist at present but require the use of more than one radio transceiver devices to achieve multi-band operation. This paper presents the design of a novel prototype multi-radio hardware platform that uses a single radio transceiver. The proposed design allows multi-band operation in the 433/868MHz ISM bands and this, together with its low complexity and small form factor, make it suitable for a wide range of BSN applications.

Pretty good governance: balancing policy drivers and stakeholder interests in developing fisheries ecosystem plans

The central research question that this thesis addresses is whether there is a significant gap between fishery stakeholder values and the principles and policy goals implicit in an Ecosystem Approach to Fisheries Management (EAFM). The implications of such a gap for fisheries governance are explored. Furthermore an assessment is made of what may be practically achievable in the implementation of an EAFM in fisheries in general and in a case study fishery in particular. The research was mainly focused on a particular case study, the Celtic Sea Herring fishery and its management committee, the Celtic Sea Herring Management Advisory Committee (CSHMAC). The Celtic Sea Herring fishery exhibits many aspects of an EAFM and the fish stock has successfully recovered to healthy levels in the past 5 years. However there are increasing levels of governance related conflict within the fishery which threaten the future sustainability of the stock. Previous research on EAFM governance has tended to focus either on higher levels of EAFM governance or on individual behaviour but very little research has attempted to link the two spheres or explore the relationship between them. Two main themes within this study aimed to address this gap. The first was what role governance could play in facilitating EAFM implementation. The second theme concerned the degree of convergence between high-level EAFM goals and stakeholder values. The first method applied was governance benchmarking to analyse systemic risks to EAFM implementation. This found that there are no real EU or national level policies which provide stakeholders or managers with clear targets for EAFM implementation. The second method applied was the use of cognitive mapping to explore stakeholders understandings of the main ecological, economic and institutional driving forces in the Celtic Sea Herring fishery. The main finding from this was that a long-term outlook can and has been incentivised through a combination of policy drivers and participatory management. However the fundamental principle of EAFM, accounting for ecosystem linkages rather than target stocks was not reflected in stakeholders cognitive maps. This was confirmed in a prioritisation of stakeholders management priorities using Analytic Hierarchy Process which found that the overriding concern is for protection of target stock status but that wider ecosystem health was not a priority for most management participants. The conclusion reached is that moving to sustainable fisheries may be a more complex process than envisioned in much of the literature and may consist of two phases. The first phase is a transition to a long-term but still target stock focused approach. This achievable transition is mainly a strategic change, which can be incentivised by policies and supported by stakeholders. In the Celtic Sea Herring fishery, and an increasing number of global and European fisheries, such transitions have contributed to successful stock recoveries. The second phase however, implementation of an ecosystem approach, may present a greater challenge in terms of governability, as this research highlights some fundamental conflicts between stakeholder perceptions and values and those inherent in an EAFM. This phase may involve the setting aside of fish for non-valued ecosystem elements and will require either a pronounced mind-set and value change or some strong top-down policy incentives in order to succeed. Fisheries governance frameworks will need to carefully explore the most effective balance between such endogenous and exogenous solutions. This finding of low prioritisation of wider ecosystem elements has implications for rights based management within an ecosystem approach, regardless of whether those rights are individual or collective.

Control circuits for avalanche photodiodes

Avalanche Photodiodes (APDs) have been used in a wide range of low light sensing applications such as DNA sequencing, quantum key distribution, LIDAR and medical imaging. To operate the APDs, control circuits are required to achieve the desired performance characteristics. This thesis presents the work on development of three control circuits including a bias circuit, an active quench and reset circuit and a gain control circuit all of which are used for control and performance enhancement of the APDs. The bias circuit designed is used to bias planar APDs for operation in both linear and Geiger modes. The circuit is based on a dual charge pumps configuration and operates from a 5 V supply. It is capable of providing milliamp load currents for shallow-junction planar APDs that operate up to 40 V. With novel voltage regulators, the bias voltage provided by the circuit can be accurately controlled and easily adjusted by the end user. The circuit is highly integrable and provides an attractive solution for applications requiring a compact integrated APD device. The active quench and reset circuit is designed for APDs that operate in Geiger-mode and are required for photon counting. The circuit enables linear changes in the hold-off time of the Geiger-mode APD (GM-APD) from several nanoseconds to microseconds with a stable setting step of 6.5 ns. This facilitates setting the optimal `afterpulse-free' hold-off time for any GM-APD via user-controlled digital inputs. In addition this circuit doesn’t require an additional monostable or pulse generator to reset the detector, thus simplifying the circuit. Compared to existing solutions, this circuit provides more accurate and simpler control of the hold-off time while maintaining a comparable maximum count-rate of 35.2 Mcounts/s. The third circuit designed is a gain control circuit. This circuit is based on the idea of using two matched APDs to set and stabilize the gain. The circuit can provide high bias voltage for operating the planar APD, precisely set the APD’s gain (with the errors of less than 3%) and compensate for the changes in the temperature to maintain a more stable gain. The circuit operates without the need for external temperature sensing and control electronics thus lowering the system cost and complexity. It also provides a simpler and more compact solution compared to previous designs. The three circuits designed in this project were developed independently of each other and are used for improving different performance characteristics of the APD. Further research on the combination of the three circuits will produce a more compact APD-based solution for a wide range of applications.

Photonic integrated circuits for the generation of coherent optical signals

The demand for optical bandwidth continues to increase year on year and is being driven primarily by entertainment services and video streaming to the home. Current photonic systems are coping with this demand by increasing data rates through faster modulation techniques, spectrally efficient transmission systems and by increasing the number of modulated optical channels per fibre strand. Such photonic systems are large and power hungry due to the high number of discrete components required in their operation. Photonic integration offers excellent potential for combining otherwise discrete system components together on a single device to provide robust, power efficient and cost effective solutions. In particular, the design of optical modulators has been an area of immense interest in recent times. Not only has research been aimed at developing modulators with faster data rates, but there has also a push towards making modulators as compact as possible. Mach-Zehnder modulators (MZM) have proven to be highly successful in many optical communication applications. However, due to the relatively weak electro-optic effect on which they are based, they remain large with typical device lengths of 4 to 7 mm while requiring a travelling wave structure for high-speed operation. Nested MZMs have been extensively used in the generation of advanced modulation formats, where multi-symbol transmission can be used to increase data rates at a given modulation frequency. Such nested structures have high losses and require both complex fabrication and packaging. In recent times, it has been shown that Electro-absorption modulators (EAMs) can be used in a specific arrangement to generate Quadrature Phase Shift Keying (QPSK) modulation. EAM based QPSK modulators have increased potential for integration and can be made significantly more compact than MZM based modulators. Such modulator designs suffer from losses in excess of 40 dB, which limits their use in practical applications. The work in this thesis has focused on how these losses can be reduced by using photonic integration. In particular, the integration of multiple lasers with the modulator structure was considered as an excellent means of reducing fibre coupling losses while maximising the optical power on chip. A significant difficultly when using multiple integrated lasers in such an arrangement was to ensure coherence between the integrated lasers. The work investigated in this thesis demonstrates for the first time how optical injection locking between discrete lasers on a single photonic integrated circuit (PIC) can be used in the generation of coherent optical signals. This was done by first considering the monolithic integration of lasers and optical couplers to form an on chip optical power splitter, before then examining the behaviour of a mutually coupled system of integrated lasers. By operating the system in a highly asymmetric coupling regime, a stable phase locking region was found between the integrated lasers. It was then shown that in this stable phase locked region the optical outputs of each laser were coherent with each other and phase locked to a common master laser.

Improved kinematic sensing for motion control applications

New compensation methods are presented that can greatly reduce the slit errors (i.e. transition location errors) and interval errors induced due to non-idealities in optical incremental encoders (square-wave). An M/T-type, constant sample-time digital tachometer (CSDT) is selected for measuring the velocity of the sensor drives. Using this data, three encoder compensation techniques (two pseudoinverse based methods and an iterative method) are presented that improve velocity measurement accuracy. The methods do not require precise knowledge of shaft velocity. During the initial learning stage of the compensation algorithm (possibly performed in-situ), slit errors/interval errors are calculated through pseudoinversebased solutions of simple approximate linear equations, which can provide fast solutions, or an iterative method that requires very little memory storage. Subsequent operation of the motion system utilizes adjusted slit positions for more accurate velocity calculation. In the theoretical analysis of the compensation of encoder errors, encoder error sources such as random electrical noise and error in estimated reference velocity are considered. Initially, the proposed learning compensation techniques are validated by implementing the algorithms in MATLAB software, showing a 95% to 99% improvement in velocity measurement. However, it is also observed that the efficiency of the algorithm decreases with the higher presence of non-repetitive random noise and/or with the errors in reference velocity calculations. The performance improvement in velocity measurement is also demonstrated experimentally using motor-drive systems, each of which includes a field-programmable gate array (FPGA) for CSDT counting/timing purposes, and a digital-signal-processor (DSP). Results from open-loop velocity measurement and closed-loop servocontrol applications, on three optical incremental square-wave encoders and two motor drives, are compiled. While implementing these algorithms experimentally on different drives (with and without a flywheel) and on encoders of different resolutions, slit error reductions of 60% to 86% are obtained (typically approximately 80%).

Multiple Dynamic Processes Contribute to the Complex Steady Shear Behavior of Cross-Linked Supramolecular Networks of Semidilute Entangled Polymer Solutions.

Molecular theories of shear thickening and shear thinning in associative polymer networks are typically united in that they involve a single kinetic parameter that describes the network -- a relaxation time that is related to the lifetime of the associative bonds. Here we report the steady-shear behavior of two structurally identical metallo-supramolecular polymer networks, for which single-relaxation parameter models break down in dramatic fashion. The networks are formed by the addition of reversible cross-linkers to semidilute entangled solutions of PVP in DMSO, and they differ only in the lifetime of the reversible cross-links. Shear thickening is observed for cross-linkers that have a slower dissociation rate (17 s(-1)), while shear thinning is observed for samples that have a faster dissociation rate (ca. 1400 s(-1)). The difference in the steady shear behavior of the unentangled vs. entangled regime reveals an unexpected, additional competing relaxation, ascribed to topological disentanglement in the semidilute entangled regime that contributes to the rheological properties.

Magnetic resonance water proton relaxation in protein solutions and tissue: T(1rho) dispersion characterization.

BACKGROUND: Image contrast in clinical MRI is often determined by differences in tissue water proton relaxation behavior. However, many aspects of water proton relaxation in complex biological media, such as protein solutions and tissue are not well understood, perhaps due to the limited empirical data. PRINCIPAL FINDINGS: Water proton T(1), T(2), and T(1rho) of protein solutions and tissue were measured systematically under multiple conditions. Crosslinking or aggregation of protein decreased T(2) and T(1rho), but did not change high-field T(1). T(1rho) dispersion profiles were similar for crosslinked protein solutions, myocardial tissue, and cartilage, and exhibited power law behavior with T(1rho)(0) values that closely approximated T(2). The T(1rho) dispersion of mobile protein solutions was flat above 5 kHz, but showed a steep curve below 5 kHz that was sensitive to changes in pH. The T(1rho) dispersion of crosslinked BSA and cartilage in DMSO solvent closely resembled that of water solvent above 5 kHz but showed decreased dispersion below 5 kHz. CONCLUSIONS: Proton exchange is a minor pathway for tissue T(1) and T(1rho) relaxation above 5 kHz. Potential models for relaxation are discussed, however the same molecular mechanism appears to be responsible across 5 decades of frequencies from T(1rho) to T(1).

Antibiotic resistance-the need for global solutions.

The causes of antibiotic resistance are complex and include human behaviour at many levels of society; the consequences affect everybody in the world. Similarities with climate change are evident. Many efforts have been made to describe the many different facets of antibiotic resistance and the interventions needed to meet the challenge. However, coordinated action is largely absent, especially at the political level, both nationally and internationally. Antibiotics paved the way for unprecedented medical and societal developments, and are today indispensible in all health systems. Achievements in modern medicine, such as major surgery, organ transplantation, treatment of preterm babies, and cancer chemotherapy, which we today take for granted, would not be possible without access to effective treatment for bacterial infections. Within just a few years, we might be faced with dire setbacks, medically, socially, and economically, unless real and unprecedented global coordinated actions are immediately taken. Here, we describe the global situation of antibiotic resistance, its major causes and consequences, and identify key areas in which action is urgently needed.

Real-Time and Data-Driven Operation Optimization and Knowledge Discovery for an Enterprise Information System

An enterprise information system (EIS) is an integrated data-applications platform characterized by diverse, heterogeneous, and distributed data sources. For many enterprises, a number of business processes still depend heavily on static rule-based methods and extensive human expertise. Enterprises are faced with the need for optimizing operation scheduling, improving resource utilization, discovering useful knowledge, and making data-driven decisions.

This thesis research is focused on real-time optimization and knowledge discovery that addresses workflow optimization, resource allocation, as well as data-driven predictions of process-execution times, order fulfillment, and enterprise service-level performance. In contrast to prior work on data analytics techniques for enterprise performance optimization, the emphasis here is on realizing scalable and real-time enterprise intelligence based on a combination of heterogeneous system simulation, combinatorial optimization, machine-learning algorithms, and statistical methods.

On-demand digital-print service is a representative enterprise requiring a powerful EIS.We use real-life data from Reischling Press, Inc. (RPI), a digit-print-service provider (PSP), to evaluate our optimization algorithms.

In order to handle the increase in volume and diversity of demands, we first present a high-performance, scalable, and real-time production scheduling algorithm for production automation based on an incremental genetic algorithm (IGA). The objective of this algorithm is to optimize the order dispatching sequence and balance resource utilization. Compared to prior work, this solution is scalable for a high volume of orders and it provides fast scheduling solutions for orders that require complex fulfillment procedures. Experimental results highlight its potential benefit in reducing production inefficiencies and enhancing the productivity of an enterprise.

We next discuss analysis and prediction of different attributes involved in hierarchical components of an enterprise. We start from a study of the fundamental processes related to real-time prediction. Our process-execution time and process status prediction models integrate statistical methods with machine-learning algorithms. In addition to improved prediction accuracy compared to stand-alone machine-learning algorithms, it also performs a probabilistic estimation of the predicted status. An order generally consists of multiple series and parallel processes. We next introduce an order-fulfillment prediction model that combines advantages of multiple classification models by incorporating flexible decision-integration mechanisms. Experimental results show that adopting due dates recommended by the model can significantly reduce enterprise late-delivery ratio. Finally, we investigate service-level attributes that reflect the overall performance of an enterprise. We analyze and decompose time-series data into different components according to their hierarchical periodic nature, perform correlation analysis,

and develop univariate prediction models for each component as well as multivariate models for correlated components. Predictions for the original time series are aggregated from the predictions of its components. In addition to a significant increase in mid-term prediction accuracy, this distributed modeling strategy also improves short-term time-series prediction accuracy.

In summary, this thesis research has led to a set of characterization, optimization, and prediction tools for an EIS to derive insightful knowledge from data and use them as guidance for production management. It is expected to provide solutions for enterprises to increase reconfigurability, accomplish more automated procedures, and obtain data-driven recommendations or effective decisions.

Clinical Research Environment in India: Challenges and Proposed Solutions.

India has compelling need and keen aspirations for indigenous clinical research. Notwithstanding this need and previously reported growth the expected expansion of Indian clinical research has not materialized. We reviewed the scientific literature, lay press reports, and ClinicalTrials.gov data for information and commentary on projections, progress, and impediments associated with clinical trials in India. We also propose targeted solutions to identified challenges. The Indian clinical trial sector grew by (+) 20.3% CAGR (compound annual growth rate) between 2005 and 2010 and contracted by (-) 14.6% CAGR between 2010 and 2013. Phase-1 trials grew by (+) 43.5% CAGR from 2005-2013, phase-2 trials grew by (+) 19.8% CAGR from 2005-2009 and contracted by (-) 12.6% CAGR from 2009-2013, and phase-3 trials grew by (+) 13.0% CAGR from 2005-2010 and contracted by (-) 28.8% CAGR from 2010-2013. This was associated with a slowing of the regulatory approval process, increased media coverage and activist engagement, and accelerated development of regulatory guidelines and recuperative initiatives. We propose the following as potential targets for restorative interventions: Regulatory overhaul (leadership and enforcement of regulations, resolution of ambiguity in regulations, staffing, training, guidelines, and ethical principles [e.g., compensation]).Education and training of research professionals, clinicians, and regulators.Public awareness and empowerment. After a peak in 2009-2010, the clinical research sector in India appears to be experiencing a contraction. There are indications of challenges in regulatory enforcement of guidelines; training of clinical research professionals; and awareness, participation, partnership, and the general image amongst the non-professional media and public. Preventative and corrective principles and interventions are outlined with the goal of realizing the clinical research potential in India.

H.M.'s personal crossword puzzles: understanding memory and language.

The amnesic patient H.M. has been solving crossword puzzles nearly all his life. Here, we analysed the linguistic content of 277 of H.M.'s crossword-puzzle solutions. H.M. did not have any unusual difficulties with the orthographic and grammatical components inherent to the puzzles. He exhibited few spelling errors, responded with appropriate parts of speech, and provided answers that were, at times, more convincing to observers than those supplied by the answer keys. These results suggest that H.M.'s lexical word-retrieval skills remain fluid despite his profound anterograde amnesia. Once acquired, the maintenance of written language comprehension and production does not seem to require intact medial temporal lobe structures.