Abstract

Computational Geometry emerged as an independent field in computer science in the last three decades. It deals with the design and analysis of data structures and algorithms for problems involving geometric objects. It has a lot of applications in Geographic Information Systems (GIS), computer graphics, databases, design in VLSI etc. A class of problems called geometric range searching problems deal with intersection of different geometric objects. In a standard geometric range searching problem, a set S of n geometric objects is to be preprocessed such that, given a query region q, efficiently report the objects or count the number of objects in S q, where S q is the space that belongs to both S and q. The range searching problems is a fundamental topic of computational geometry. It has been extensively studied and there exist many efficient solutions. In many applications, it is not sufficient to just report or count all the objects in S q. There is need for aggregation on the objects in S q to present more useful information. One such type of aggregation is geometric aggregation, where the aggregate function is geometric in nature. In this work, we consider the maxima query problem in two-dimensional space. Let S be the static set of n points in R2. A point p = (xp; yp) is said to dominate a point q = (xq; yq) if xp  xq and yp  yq. A point is maximal if it is not dominated by any other point in S. Given an orthogonal range query q, we need to efficiently report or count the maximal points of S q. We propose a linear size data structure for reporting the set of k maximal points among the points that lie in a given 3-sided orthogonal range unbounded on its right in O(log n+k) worst case query time. Using linear space, the data structure can support counting the number of maximal points in a 3-sided query range in O(log n) worst case time. This is the first data structure for counting maxima in a given orthogonal query range in plane. We propose data structures to support 4-sided maxima reporting in O(log n+k) worst case time using O(n log n) space, where k is the size of the output. Counting maxima in a 4-sided orthogonal query rectangle can be supported in O(log n) worst case time, using O(n log n) space. The techniques can be directly applied to solve rectangular visibility problem. We use the pointer machine model of computation.

Abstract

The tremendous innovation in technology in all spheres of life has led to an explosion in the amount of data that has been generated. However labeling this huge amount of data for supervised learning tasks is often quite expensive, time-consuming and require significant manual work. Active learning has emerged as a rapidly growing field of machine learning, which aims at reducing the labelling effort of the oracle (human expert) in acquiring informative training samples in domains where the cost of labeling is high. It has been applied in areas such as document classification, speech recognition, information extraction, etc to train classifiers by labeling minimal amount of data. However, most of the existing active learning strategies are computationally expensive as they select only a single sample for labeling by the oracle in every iteration. In this thesis we propose a framework for efficient batch mode active learning that is based on Reverse Nearest Neighbor queries. We develop an efficient sampling technique for active learning using the notion of influence sets based on Reverse Nearest Neighbor. The proposed sampling technique uses RNN queries to efficiently determine the informativeness of the sample based on a combination of factors such as their utility for the classifier, representativeness and the unique information that they provide. We extend this RNN based sampling technique to develop a framework that can label a batch of samples for efficient active learning. The framework selects a batch of samples such that the overall information gain for the classification model is maximized. This framework is made generic so that the underlying classification model can be changed as per the domain requirements. We also propose an extension to this framework to handle the multi-class classification task effectively. Experiments conducted on the UCI and Reuters datasets show that our sampling framework and its variants are highly competitive in terms of accuracy in comparison with popular active learning techniques. We also develop an interactive application for bookmarks classification as a proof-of-concept of the utility of our batch mode active learning framework in interactive applications. This bookmarking system provides an opportunity for users to interact with the system by labeling the bookmarks to help the system learn about their preferences. The RNN based batch mode active learning framework is used in the backend to generate informative bookmarks for the users to label. Experiments show that labeling informative bookmarks can help the system to achieve good accuracy even with few labeled samples thereby providing a better user experience.

Abstract

Majority of the world’s electricity demand at present is met by thermal power generating stations which purely run on conventional fossil fuels. Utilities are mainly dependent on these sources spending huge revenue to cater for the ever increasing electricity demand. This motivates utilities to schedule their generation according to load demand in the most economical way. Every thermal generating unit is characterized by its distinct incremental heat rate curve which governs the production cost. An optimal allocation of generation among the different power generating units can thus save considerable fuel input and cost. However, a greater amount of fuel cost can potentially be saved by extending this optimization procedure to decide which of these units would participate in the optimal allocation. In other words, it is significant to determine whether the unit must be ON/OFF. Committing thermal generating units among the available ones in this fashion is popular as Unit Commitment (UC). It is a vital economic optimization problem in power systems with the main criteria of meeting the load demand while accounting for all the unit operational constraints at the same time. On the other hand, optimally distributing the generation among the set of units already scheduled/committed for operation is known as Economic Dispatch (ED). Present day load demand is increasing at a pace which expansion in power system has hardly been able to keep up with. The power systems have thus been left stressed. This makes the system insecure and vulnerable. Hence system security also plays a major role in generation planning. Therefore, the problem of UC is not merely to commit adequate generation but distribute it with utmost attention towards system security for achieving smart grid of future. In this thesis, the evolutionary technique of Binary Particle Swarm Optimization (BPSO) is used in solving the UC problem. As for determining the optimal generation dispatch for the minimal cost, a complete Optimal Power Flow (OPF) is run for each hour’s commitment over the UC time horizon. Conventional OPF solves for the optimal dispatch adjusting to all the constraints like fixed bus voltage limits, line power flows, transformer tap positions etc., resulting in a secure solution. Apart from these concerns, it would be very useful to compute the loadability and safety margin of a given system. This is important as it can potentially avoid any system collapse and keep a measure of system security in true sense. The work proposed in this thesis makes attempt to find optimal unit commitment keeping system operation secure by calculating what is known as the global L-index. It is a mathematical tool which computes how far the current operating condition is from the collapse point. Inclusion of such a constraint would naturally ensure that the optimal solution does not violate system voltage security. The major contribution of the proposed work lies in investigating more number of feasible solutions because the replacement of hard limits on the bus voltages by the L-index criterion effectively loosens the search space. Thus, experimentation is carried out by calculating the L-index while relaxing the fixed voltage limits on all or a few buses at the same time. A consistent raise in fuel costs and fast depletion of fossil fuels, growing awareness towards environmental protection has paved the path towards utilization of renewable energy sources for power production. Hence renewable energy sources are used and deployed in power systems with more eagerness today. However, they impose a considerable impact on the system owing to the intermittent nature of availability. The problem of UC becomes more complex with the integration of renewable sources given the dissimilarities in behavioural and functional constraints with respect to conventional thermal generation units which need to be addressed as renewable generation will be integral part of smart grid. This thesis aims at solving a voltage security constrained UC with the inclusion ofrenewable energy sources into the system. In the present work inclusion of one such source like Solar into the system has been considered. A Solar Thermal Power Plant (STPP) of suitable capacity is modelled with Concentrated Solar Power (CSP) technology of parabolic trough type. The standard dimensions of parabolic trough from a commercially installed power plant are considered for modelling. The optimal generation dispatch function (OPF) solution, which is an inherent exercise within the master problem of unit commitment, also accounts for the intermittent output from solar generator present in the same grid. The proposed method is validated by implementing it on the standard IEEE 14 and 30 bus test systems. One of the thermal generating units in standard test system is replaced by a solar thermal unit and the UC schedule is determined for the remaining units. The UC results, illustrated both in

Abstract

The main objective of this research is to contribute to the understanding of the seismic performance of superstructure considering the complex dynamic interaction between superstructure, the pile foundation and the soil. As the dynamic response of the structure and the pile to large extent is inelastic, the primary focus is on studying the behaviour of superstructure by modeling the nonlinearities of soil, modeling the interface between pile and soil. To address this problem, a Finite Element Method is used to model soil structure interaction analysis of pile supported framed structures by programming in MATLAB R2009a using Direct Method. A parametric study is conducted to understand the pile soil behaviour (Soil Foundation Interaction (SFI)) by changing various parameters, like pile and soil modulus, pile length, pile diameter and number of piles of the pile group. In each case the response is converted to frequency domain to understand the shift in frequency. Further, an attempt has been made to understand that complex behaviour of Soil Foundation Structure Interaction (SFSI). For that purpose, a 5 storey pile supported frame structure is modeled and its nonlinear behaviour under strong earthquake excitations is studied. A comparison of linear and nonlinear responses and the effect / significance of soil inelasticity on the structural response are commented. A SFSI system is modeled by considering the nonlinearity at the interface of the soil and pile. For that purpose, an interface element is used to model the interface between pile and soil. Parametric study has been carried out to know the response of pile with and without interface element and also to know the response of pile supported framed buildings with and without interface element. Besides this, the change in response of a high rise structure when a group of adjacent pile supported structures are present under seismic excitation is also studied (Structure Soil Structure Interaction (SSSI)). Different case studies are considered, namely 1. the group effect of structures supported on piles are considered (like group of two identical structures, group of three identical structures and group of three different structures), 2. the effect of variability in structure height is considered (like 5 storey structure, 10 storey structure and 15 storey structure) and 3. the effect of variability in structure shape is considered. For each case, the SSSI response is compared with the conventional fixed base response to understand the significance of SSSI. Few quantitative conclusions as mentioned below are made out of this study by commenting the significance of each behaviour (free field over SFI, SFSI over fixed base analysis, SSSI over fixed base analysis). The presence of soil and foundation in a SSI make a considerable change in response of the structure with a shift of natural period of the system. A peculiar behavior in the stress state of pile is observed for both elastic and inelastic soils, this behavior is because of Soil resistance acting downwards along the pile shaft because of an applied transient load. Repeated dynamic contacts of soil and pile is observed for both SFSI and SFI, this is because of the lateral compression of soil leading to formation of gap between pile and soil. The behavior on stress state of pile is very much different for the case of analysis with Interface elements. SSSI effects have been found to be important, when a group of identical structures with same dynamic characteristics are present,. The middle structures are attracting more displacements because of trapping of seismic waves. In case of group of structures with variable height, while considering SSI there is a decrease in response for 15 storey structure when compared to 10 storey structure which is not observed in fixed base system. In case of response of structures of variable shape the top floors will attract more displacement because of reduced stiffness on top floors but in conventional fixed base case opposite behavior is observed. So it has been recognized from this study that a reasonable seismic analysis for high rise buildings supported on pile foundations is needed to produce a safe and economic design.

Abstract

One of the accessory proteins of SARS coronavirus, 3a, is a 274 residue long protein with three transmembrane (TM) domains. This protein has been suggested to oligomerize to form tetrameric ion channels, which assist viral release from host cells. However, the atomistic details of the three-dimensional structure of the protein are still not available. In this study, molecular dynamics (MD) simulations have been used to understand the conformational properties of the three transmembrane domains (TM1, TM2 & TM3), and to model a structural model of the bundle formed from these domains. Extensive MD simulations have been performed in implicit bilayer environment with four different thicknesses, and in presence of explicit lipid bilayer environments (DLPE, DMPC, POPC, DPPC). The tilt angles to overcome the hydrophobic mismatch obtained at these eight different models were found to be slightly different from each other, but the inherent properties of the TM domains themselves were independent of the lipid bilayer model. TM1 domain was found to have a kink around Pro42 consistently in all the simulations. The conformational dynamics of each of the three TM domains were understood using tilt angle, kink angle, intra- and inter-molecular hydrogen bonding, and solvent accessible surface area. Using the stable conformations obtained using the simulations on the individual α-helices, a method by which potential three-dimensional structural models for the bundles is proposed. The surface areas of overlapping residues of possible bundles were calculated, and four different possible structures for the bundle are proposed. The best model structure comprising all three alpha helices was subjected to MD simulations to examine its quality. The TM bundle was found to form a compact and stable structure with significant intermolecular interactions. Further analysis indicates that residues from the TM2 and TM3 domains are likely to line the pore of the ion channel, which is in good agreement with a recent experimental study on the ion channel activity of SARS 3a protein.

Abstract

The earthquake resistant design of structures according to the existing design philosophy aims to ensure that during their lifetime, the structures resist the maximum possible earthquake without collapse. This philosophy ignores the fact that for the allowable damage at the end of the design life, it is necessary to account for the seismicity of the area in a comprehensive manner i.e., in terms of magnitudes with proper spatial distributions around the site. It is also necessary to estimate damage due to each of these events and also cumulative damage till date. Such a procedure is proposed in the report and it is applied to heritage structures which stand for longer duration compared to ordinary buildings. As a case study, the proposed methodology is used to evaluate damage to 3 Heritage structures,India gate and Qutb Minar located in Zone IV and Golconda fort located in Zone II according to IS 1893-2002 .Proposed approach is based on the estimation of expected number of earthquakes at each source with the help of Gutenberg-Richter relation and time-dependent hazard model and on the estimation of damage to SDOF structure during each of these events. The corresponding structural damage has been estimated by considering oscillator to be hysteretic in nature. The cumulative damage during the design life has been estimated by considering the most critical sequence of earthquake events and by considering event to event stiness and strength degradation for the oscillator.

Abstract

The elucidation of order parameter/reaction coordinate for molecular dynamics (MD) without any a priori knowledge is an open and illposed problem. Several methods for extracting the order parameter like Bayesian analysis, genetic neural network etc. require some input information (like reactant and product state) about the system or they involve extracting thermodynamic/statistical quantities (like “free energy”), as a function of a “progression coordinate”, which is typically not known beforehand. We have implemented a recently developed nonlinear dimension reduction and spectral clustering technique “diffusion map” (DM) on equilibrium trajectory of alanine dipetide and non-equilibrium trajectory of β-hairpin. DM is successfully able to extract small number of good order parameters known as “Diffusion Coordinate” (DC), without any a priori knowledge. These extracted DC’s are dynamically meaningful and also show good correlation with physical parameters. We have integrated two features in DM: i) coarse graining of the graph and ii) Nystr¨om extension; these features reduce the computational cost while preserving the essential features of the dataset. Further more, we have also addressed the solutions of sampling problem in MD. We have proposed new methods to enhance the sampling of phase space along the extracted DC. In one method, we have applied a bias force to push the system (particle/biomolecule) out of the free energy minima and this bias force is a function of DC. We have successfully implemented this method on M¨uller-Brown potential. In another method, we enhance the sampling of phase space by aim-less shooting approach (without using any biased force/potential) and successfully tested this method on alanine dipeptide system.

Abstract

Many state-of-art technique in robotics such as mapping of environment, robotic exploration, localisation of robot, SLAM etc. depends a lot on effective segmentation of ground plane. An autonomous robot using camera as primary sensor should contain a processing module that can clearly indicate the sharp boundary between the obstacle and ground plane with high precision. A better understanding of environment plays a vital role in most of the robotics application. To build a map or to explore in an unknown environment or to localise a robot, all of these requires fine metric details which can only be improved if you have a clear knowledge of ground plane. Detection and segmentaion of small obstacle of the order of a few centimeters is very difficult even with sophisticated depth sensors such as laser range finders. This thesis presents an effective approach to segment ground plane and discover small obstacles in an indoor environment by exploring some of the probabilistic graphical model technniques. Probabilistic graphical models such as Bayesian Network and Markov Random Field have been used with a robotic application point of view. The Bayesian Network was used here by fusing appearance and geometric (homography) cues which provides a way for accurate and reliable ground plane segmentation in significantly difficult situations. Herein the appearance and homography based error models are appropriately weighed to come up with the eventual class probability of a feature track. It was observed that bayesian network works effectively in most of the cases but do fail in certain cases as posterior tends to saturate over time and sudden change in environment does not gets reflected quickly. So, to improve further on my problem, I came up with a novel pipeline for segmentation of ground plane that makes use of several state of the art modules culminating in a Markov Random Field (MRF) based graph cut formulation that provides for optimal classification. While sharing similarities to the problem of appearance based image segmentation, obstacle detection when approached as a traditional segmentation problem, suffers from the following pitfalls 1) Obstacles having same appearance characteristics with the navigable ground plane regions tend to be classified as ground plane regions. 2) Ground Plane regions that change their appearance can be classified as non-ground regions. The algorithm that uses MRF avoid both the above pitfalls and shows robust ground plane segmentation, and detection of obstacles, big and small in diverse environments. By using the pipeline discussed in the thesis, it is possible to detect obstacle as short as 2-3cms as far as 7m away from the camera at real time rates. vi

Abstract

Natural language parsers lie at the core of various natural language processing (NLP) systems such as machine translation (MT), question answering (QA), information extraction/retrieval (IE/IR), etc. Building accurate, wide-coverage parsers has been one of the main goals in NLP research for the last two decades. As a result, there exist today highly accurate parsers based on a variety of approaches not only for English but also for a few other languages. Statistical parsers have proven to be most effective both in terms of coverage and precision. However, statistical parsers whether constituency-based or dependency-based make certain independence assumptions about sentence structure. Simply put, statistical parsers of all hues assume that sentence structure can be factored into smaller sub-structures which can be predicted independently varying only in the type of factorization. Although such assumptions are necessary in order to ensure tractability of parsing algorithms, they are not linguistically tenable since we know that there is a significant amount of interaction among the factored sub-structures. There are a number of linguistic phenomena such as subject-verb agreement, verb argument structure and coreference of noun phrases where information about the linguistic relationship is spread over more than one sub-structure. In other words, in all these cases, the cues for parsing one sub-structure correctly can come from another sub-structure. Most state-of-art statistical parsing models which make independence assumptions about sentence structure fail to capture such non-local phenomena. In this thesis, I study two approaches to overcome this limitation and make use of non-local features that encode greater contextual information during parsing. The first approach is based on the technique of discriminative reranking which consists of two steps: increasing the width of the search beam to allow more candidate parses and then employing a classifier that can use non-local features to rank the candidate parses and pick the best among them. The second approach is based on the technique of ensemble parsing whereby parsing models with complementary strengths/weaknesses can be combined to obtain best possible parsing performance. In particular, I study the stacking approach to combining parsers at learning time. The explored experimental setup allows for non-local features defined over the output of one (or more) parser(s) to be used while training a graph-based parser. In my experiments on discriminative reranking and ensemble parsing, I build several highly accurate parsers for English which can be directly used in in-house large-scale English-to-Indian language machine translation systems. I combine freely available parsers using the ensemble technique of re-parsing to build the best performing model for dependency parsing of English. This high accuracy dependency parser for English is available under GPL and can be deployed in a wide array of NLP systems. In my experiments on stacking dependency parsers, I build stacked parsing models with different combinations of non-local features for three Indian languages– Hindi, Telugu and Bangla –to study the influence of each feature in improving parsing performance. The accuracies of the best performing of these models are the state-of-art accuracies for parsing these Indian languages. Although I do not come up with a entirely new way of overcoming the limitation of feature locality in statistical parsing frameworks, the insights gained from the studies presented in this thesis can inform efforts aimed at development of contextually rich models of syntactic parsing.

Abstract

Information about blood flow in the brain is of interest to detect the presence of blockages and ruptures in the vessel network. A standard way of gathering this information is to inject a bolus of contrast agent into the blood stream and imaging over a period of time. The imaging is generally done over an extended period of time (tens of minutes) during which a patient can move which in turn results in corruption of the acquired time series of volumes. This problem is often observed in dynamic magnetic resonance (MR) imaging. Correction for motion after scanning is a highly time-intensive process since it involves registering each volume to a reference volume. Moreover, the injected contrast alters the signal intensity as a function of time and often confounds traditional motion correction algorithms. In this thesis, we present a fast and efficient solution for motion correction in 3D dynamic susceptibility contrast (DSC) MR images. We present a robust, multi-stage system based on a divide and conquer strategy consisting of the following steps: i) subdivision of the time series data into bolus and non-bolus phases depending on the status of bolus in the brain, ii) 2D block-wise phase correlation for detecting motion between adjacent volumes and categorizing the corruption into four categories: none, minimal, mild and severe depending on the degree of motion and iii) a 2-pass, 3D registration consisting of intra-set and inter-set registrations to align the motion corrupted volumes. The subdivision of time-series into distinct sets is achieved using Gamma variate function (GVF) fitting. The dynamic non-uniform variation in signal intensity due to the injected bolus is handled by employing a clustering-based identification of bolus-affected pixels followed by correction of their intensity using the above GVF fitting. The proposed system was evaluated on a real DSC MR sequence by introducing motion of varying degrees. The experimental results show that the entropy of the derived motion fields is a good metric for detecting and categorizing the motion. The evaluation of motion correction using the dice coefficient measure shows that the system is able to remove motion accurately and efficiently. The efficiency is contributed to by the proposed detection as well as the correction strategy. Including the detection prior to existing correction methods achieved a savings of 37% in computation time. Whereas, when the detection is combined with the proposed correction stage, the savings increase to 63%. Notably, the above performance was found to be had with no trade-off between accuracy and computation cost.