Abstract

With technological advancements, more and more content is becoming available in digital form on a regular basis. Such overwhelming amount of available data has lead to the problem of information overload. This has led to an increased interest in developing methods that can help users to effectively navigate, summarize and organize this information. The ultimate goal is to help users find what they are looking for. Significant efforts have been made to encounter challenges posed by information overload in web-domain. These efforts include exploitation of text-content as well as links (present as URL in web-pages). Interestingly, phenomenon of data explosion isn’t limited to web-domain but also observed in various other domains as well. Though the nature of challenges induced by information load is quite the same across all domains, uniqueness of a domain demands specialized solution. Unsurprisingly, efforts have been made to build information retrieval system in other domains by extending the popular notions developed for web-domain retrieval systems. In this thesis, we made an effort to address one of the challenges in legal domain and investigated the problem of finding similar legal judgments. In legal domain, information overload has adverse effect on finding similar judgments, which is a crucial task for a lawyer to prepare his arguments. Due to enormous number of judgments available, a lawyer needs to browse through hundreds of legal judgments to find a set of legal judgments similar to a given judgment ‘J’ and hence finds this task tiring and time consuming. In order to find similar legal judgment, he starts browsing legal database using his knowledge and experience. Once he finds an older judgment (say judgment ‘J’) which adequately satisfies his requirements, he starts looking for more judgments similar to judgment ‘J’ for comprehensive analysis of the legal principle applied in those judgments. Since number of judgments in legal database is enormous and, in general, size of each judgment is huge, an automated mechanism for finding similar legal judgments turns out to be a non-trivial problem. Textual information and its accessibility play a particularly important role in legal domain. The amount of available text-data in legal domain is vast and continuously growing which makes it challenging to deal with. Apart from the size of data, the inherent complexity of legal domain demand better and more sophisticated methods to process legal documents to satisfy information need of legal practi- tioners. To begin with, we investigated the issue of finding similar legal judgment by exploiting various attributes of legal judgments. We conducted our experiment on real world dataset and found that, text-content of judgments is not as effective as links (known as case-citations) available in legal-judgments, for finding similar legal judgments.

Abstract

Queue is required when service provider is not able to handle jobs arriving over the time. In real life, job execution often requires human intervention in it’s execution. In a highly flexible and dynamic environment, some jobs might demand for faster execution especially when resources are limited and jobs are competing for acquiring resources. Thus, user may demand for speed up (reduced wait time / faster execution) for some of the jobs present in the queue at run time. In such cases, it is required to accelerate (directly sending the job to the server) jobs requesting for speed up ahead of other jobs present in the queue to facilitate earlier completion of urgent jobs. Since no additional resources are used, therefore such acceleration of jobs might result in slowing down of other jobs present in the queue. In this thesis, we model the problem of Speed Up Scheduling without acquiring any additional resources for the scheduling of on-line speed up requests posed by the user at run-time. Speed Up scheduling needs to speed up all the jobs that requested for it without unnecessarily slowing down the other jobs. Note that it might not be possible to achieve speed up for all the jobs that requested for it as well as it might be the case that while speeding up jobs, even some of the jobs that requested for speed up were slowed down. In order to address Speed Up problem, we provide implicit Speed Up techniques where the notion of acceleration is incorporated in the priority function. We use concepts of queuing theory and discrete event based simulation model for the design and evaluation of our speed up algorithms. We apply the idea of Speed Up Scheduling to two different applications - Web Scheduling and CPU Scheduling. We demonstrate our results with a simulation based model using trace driven workload and synthetic datasets to show the usefulness of Speed Up in these domains. We further examine how different scheduling algorithms can be compared based on speed up/slow down characteristics.

Abstract

With the widespread application of digital data, there has been an increasing realization of the importance of multi relational data. Multi relational objects usually capture a variety of relations among different entities. For example, in recommender systems, the rating matrix captures the relation between movies and users, a social network captures relations among users, and the cast of the movie captures the relation between movies and users, the social network captures relation between movies and actors/actressess. The multi relational analysis problems deals with the following tasks  Partition the dataset into multi-relational clusters.  Prediction of values when entries are missing. Clustering and missing value prediction gives us a better understanding of the data. For example, clustering on movie ratings dataset, could help us understand movies watched and the movie ratings provided. This also helps us to recommend movies to users and prediction of missing values. Rapid growth of digital data has brought data involving objects of multiple types. A major challenge is to deal with multiple types of data simultaneously to utilize their interrelatedness. A major challenge in developing simultaneous clustering technique is to effectively use available information contained in multi relational data namely inter type and intra type constraints. In this thesis we are concerned with various relational learning tasks by analyzing Matrix Factorization (MF) models and its extension using the Matrix TriFactorization approach. While MF models have analyzed a single class of relations, we present how TriFactorization models with constraints called inter and intra relations in Sec 4.1 can be included in the model. The experiments have been carried out in tasks discussed in Section 5.1 for link prediction and relation prediction problems. We extend the relation prediction task withentity ranking, i.e given a triple with incomplete or missing information, can we find the missing entity ? These experiments help us establish to learn from multi-relational data and we compare to learning from single relations establishing the benefits of learning from multi relational datasets.

Abstract

The compiler optimizations we enable and the order in which we apply them on a program have a substantial impact on the program execution time. There are an infinite number of possible optimization sequences that can be applied to a program and since the runtime of any program is highly dependent on the optimization sequence that was applied to it, the problem of finding the right optimization sequence is of vital importance and is a long standing issue for compiler writers. Modern optimizing compilers typically have several code-improving phases, most of which can be applied in any order. These phases interact by enabling or disabling opportunities for other optimization phases to be applied. As a result, varying the order of applying optimization phases to a program can produce different code, with potentially significant performance variation amongst them. Moreover, finding the optimal optimization sequence for even a single program is hard as the space of attempted optimization phase sequences is huge and the interactions between different optimizations are poorly understood. In this thesis we propose two different solutions to the problem of finding good optimization sequences. There are broadly two ways to attack this problem: iterative compilation methods or heuristic search techniques and machine learning based prediction models. In heuristic search techniques, we explore the space of optimization sequences by pruning out not promising paths and eventually arriving at a near optimal sequence. This approach requires a large number of iterations before we converge on an optimization sequence. In machine learning based prediction models, we learn the parameters of an optimization prediction model using a set of programs as training data. This is an off-line process. Later we can use the prediction model to determine which optimizations should be enabled or disabled on a given program. The advantage of this approach is that it requires only few runs of the program to identify the suitable optimizations that needs to be enabled on a program. However, this approach solves the problem only partially as the model does not tell the order in which the optimizations have to be applied. Any machine learning based classification algorithm may not be applicable due to the exponentially large number of available optimization sequences. There is no universal optimization sequence that will produce the best code for every program, since the best sequence depends on the characteristics of the program being compiled, the compiler, and the target architecture characteristics. Compilers (like gcc) provide default optimization sequences which can give good program speedup for most of the programs. As the default sequences have to optimize programs with different characteristics, they embed in them multiple subsequences which can optimize different classes of programs. These multiple subsequences may falsely interact with each other and affect the potential program speedup achievable. Instead of searching for a single universally optimal sequence, we can construct a small set of good sequences such that for every program class there exists a near optimal optimization sequence in the good sequences set. If we can construct such a good sequences set which covers all the program classes in the program space, then we can choose the best sequence for a program by trying all the sequences in the good sequences set. This is the basis of our first solution. We developed a down-sampling technique to reduce the infinitely large optimization sequence space to a small set (of size in the order of hundreds). During the down-sampling process, the diversity of the optimization sequences catering to different program classes is retained. Using various techniques we constructed a small set of optimization sequences from the down-sampled sequence set, which cater a large set of programs with varied characteristics. This approach completely circumvents the need to solve the program classification problem. We tested this approach using Mibench and Polybench benchmark suite. Using a sequence set size of around 10 we got an average speedup up to 14% on PolyBench programs and up to 12% on MiBench programs. This approach is quite different from either the iterative compilation or machine learning based prediction modelling techniques proposed in the literature so far. We use different training and test data sets for cross validation as against the Leave-One-Out cross validation technique. Our second solution is a hybrid approach in which we use an iterative compilation technique in the training phase, and a simple prediction model based on nearest neighbourhood technique later on. The feature vector for a program in our prediction model consists of dynamic features of a program which are normalized hardware performance counters extracted through Intel Vtune Amplifier. The heuristic/iterative search is a onetime offline procedure.

Abstract

Since the 1970s, databases continue to remain the predominant choice for storage of information for commercial as well as personal needs. While many types of databases (hierarchical, network, file-based, object-based) have been developed and put to use, relational databases continue to hold the major share of the various means of information storage. A relational database (or RDBMS) is a tool that stores data as a collection of rows and columns in tables and provides relational operators to manipulate the data in a tabular form. The data is stored in a structured manner and it is updated, manipulated or retrieved using a special language called the Structured Query Language (SQL). There are several reasons for the popularity and wide-spread use of RDBMS including: 1) high performance; 2) scalability, robustness and flexibility; 3) strong data protection; and, 4) ease of data management. In addition to these, structured data allows us to index, sort, filter or perform aggregation on the data stored within the columns of the tables through SQL. However, RDBMS suffer from a disadvantage as well. Presently, the assistance of an RDBMS expert, who knows the database schema and SQL, is required for performing computation on data and providing it to the user. Therefore, a non-technical person cannot retrieve data from a RDBMS. Moreover, form based data retrieval approaches lack the flexibility of a natural language and therefore, lack the ability to intuitively capture the user’s intent and instructions. To overcome these limitations, a medium (a software tool) is required which accepts instructions (or questions), related to the stored data, in natural language from the user and sends the response back to the user. Such a tool is called a Natural Language Interface to Databases (or NLIDB system). A NLIDB system takes as input a natural language (NL) query from a user and returns the output retrieved from the database to the user. Despite being a deeply researched area for over five decades, NLIDB systems still remain an open research problem. In the earlier systems, the focus was on implementing the NLIDB systems on a particular database. Since this was achieved with high accuracies, the focus shifted to exploring the issues of portability of NLIDB systems which included dealing with various system engineering problems of robustness and scalability of the application. An important issue in portability is the ability to quickly customize a NLIDB system to a new language and domain (of the database). Conventionally, NLIDB systems depend heavily on linguistic and domain experts for customization. Quite often, the system modules integrating the language and the domain are tightly coupled, thus, making the customizations either very expensive or sometimes impossible. Another important aspect of NLIDB systems is its ability to handle the aggregations specified in a natural language query. Aggregations are a common phenomena in natural language and the words specifying aggregations are called aggregates. In aggregations, a function is applied to a set of values or entities in a database to yield a single value. Applications using databases through SQL get restricted in processing aggregates because of the limited set of corresponding aggregate functions available in a database. Moreover, complex aggregates do not have inbuilt aggregate functions, therefore, they cannot be processed by RDBMS. Successful resolution of aggregations in NLIDB systems increases the variety of queries that a system can process and adds to the improvement of the overall accuracy. Based on the above hypothesis, in our research work, we have focussed on developing a NLIDB framework which allows us to overcome the limitation of portability across languages and domains while maintaining a high level of scalability and robustness. To achieve this, the framework uses a high accuracy general purpose syntactic parser along with semantic frames to parse a NL query to an SQL query. With this approach, we have successfully derived the semantics of a given NL query without using a semantic parser while maintaining an overall accuracy of above 90%. Such precision cannot be achieved even by the state-of-art general purpose semantic parsers available with today’s technology. We have also overcome the limitation of conventional RDBMS in handling aggregations by developing a framework which can process simple or complex aggregates independent of the processing capability of the RDBMS.

Abstract

Echo-cardiographic images provide a wealth of information about the heart(size, shape, blood flow rate, etc) and are therefore used to assess the functioning of heart. Automated analysis of echo-cardiographic images are aimed at extracting a displacement field which represents the heart motion. Such a field is critical for extracting higher order information which is needed for diagnosis of heart diseases. However, these images are very noisy which poses a huge challenge to image analysis. Most of the methods used for the analysis of the echo-cardiographic images are designed in such a way that they are very specific to the noise present in the echo-cardiographic images. These methods can be categorized into two categories: (i) de-noise the signal prior to analysis and (ii) formulate input as a noisy signal to model the noise using statistical noise model. In this thesis we propose algorithms for analysis of echo-cardiographic images which do not require any pre-processing step or explicit handling of noise present in the images. We present novel algorithms for segmentation and registration of echo-cardiographic images in this thesis. These two algorithms are designed based upon noise-robust image representation. This image representation is obtained by computing a local feature descriptor at every pixel location. The feature descriptor is derived using the Radon-Transform to effectively characterise local image context. The advantage of this representation is that, in addition to being robust to noise, it provides a good detail of the distribution of the pixel intensities in the image. Next, an unsupervised clustering is performed in the feature space to segment regions in the image. This feature-space representation is also used to extract hierarchical information for image registration. The performance of the proposed methods is tested on both synthetic and real images. A comparison against well established feature descriptors is carried out to demonstrate the strengths and applicability of the proposed representation. Overall, the results indicate promise in the strategy of doing segmenta- tion of noisy data in image. In this thesis, the algorithms are designed in such a way that the algorithm works efficiently even in presence of high level of speckle noise and doesn’t require any pre-processing. Moreover it can be easily adapted to any other modality. The main contributions of this thesis are: 1. Noise-robust representation of an image in feature space. 2. Segmentation of an image using feature space 3. Registration of images using hierarchical information.

Abstract

In this thesis, we address the problem of automatically generating human-like descriptions for unseen images. Given a collection of images and their corresponding human-generated descriptions, we generate descriptions assuming two kinds of input : (a) An unannotated image (b) An annotated image. Previous attempts for this task mostly rely on visual clues and corpus statistics, but do not take much advantage of the semantic information inherent in the available image descriptions. Here, we present a generic method which benefits from all these three sources (i.e. visual clues, corpus statistics and available descriptions) simultaneously, and is capable of constructing novel descriptions. Our approach works on syntactically and linguistically motivated phrases extracted from the human descriptions. Experimental evaluations demonstrate that our formulation mostly generates lucid and semantically correct descriptions, and significantly outperforms the previous methods on automatic evaluation metrics. One of the significant advantages of our approach is that we can generate multiple interesting descriptions for an image. Unlike any previous work, we also test the applicability of our method on a large dataset containing complex images with rich descriptions. None of the previous approaches report results on the effect of incorrect label detection on the quality of the final descriptions generated. With this motivation, we present a simple approach to generate descriptions from an annotated image and show that with accurate object and attribute detection, humanlike descriptions can be generated. We also perform an extensive task-based evaluation to analyze our results.

Abstract

Internal repetition within proteins is a commonly observed phenomenon and presents multiple binding and structural roles to proteins by forming integrated multi-repeat assemblies in three-dimensional structure. The copy number and assembly of these repeating units are responsible for diverse protein-protein interactions, and consequently, defects in repeat proteins are linked to many diseases. The variation within the repeat units makes their identification difficult at the sequence level and structure based approaches are desired. Here we propose a graph based approach for the analysis and identification of Ankyrin repeats (ANK), one of the most frequently observed structural repeats in nature. The topological details of protein structure have been shown to be effectively captured by protein structure graph, and we expect the tandemly repeated ANK motifs to be captured by the profile of the graph centrality measures. Here we show that the principal eigen spectra of the adjacency matrix captures very well the ANK repeat regions and is also reliable in predicting accurately the repeat boundaries. Furthermore, it is computationally very efficient compared to structure-structure comparison methods.
A non-redundant dataset of 54 known Ankyrin repeat proteins is used as a training set for improving the sensitivity and specificity of the proposed algorithm for identifying Ankyrin repeats. The algorithm comprises of a set of rules defined based on the length distributions of the secondary structure elements of the structural motif and the conserved pattern in adjacency eigen spectra. The analysis is carried out on a redundant set of 118 known ankyrin repeat proteins and high sensitivity (0.92) and specificity (0.89) with respect to the annotation in UniProt is observed, suggesting the reliability of the approach. Annotation of 21 proteins has been improved. All α and α + β class proteins from the SCOP database were analyzed using the proposed algorithm and 60 novel Ankyrin repeat proteins were identified.

Abstract

Carbon nanotubes were discovered in 1991 by Sumio Ijima. These molecular scale tubules of a carbon allotrope, have generated a lot of interest recently because of their extraordinary mechanical, electrical and chemical properties and because of their ability to serve as nano sized containers for various media.
This work deals primarily with the study of the dynamics of water inside a nanotube. The applications of water dynamics inside nanotubes is spread across various fields like design of devices and materials, sea water desalination and biological activities. From the perspective of biological activities, Aquaporins, which are proteins embedded in cell membranes, control the transport of water and ions across a cell. Aquaporins have dimensions similar to a nanochannel. The conclusions drawn from the understanding of the mechanism of water dynamics inside a nanochannel would also be applicable to water flow across Aquaporin pore. The phenomenon of water confinement in narrow channels whose diameter is comparable to that of water molecules alters physico-chemical properties of water and it is this alteration that presents new frontiers for research.
In past mainly two types of studies have been conducted for understanding water dynamics where flux inside nanochannel varies namely 1) System without application of external electric field or pressure and 2) System with application of external electric field or pressure. These investigations have been done on both single walled nanotube and double walled nanotube. In this study, we focus on systems without application of external electric field for investigating the dynamics of water molecules in and around nanochannel six configurations of nanosystems, five of them with nanonchannel pore (single walled nanotube in the first, and double walled nanotube in the rest) embedded in graphene sheets and the last one being graphene sheets without a nanonchannel, were simulated using Molecular Dynamics.
This study aims to investigate properties of the above systems without application of external electric field or pressure difference, to explore if there is any inherent asymmetry in the system during flow of water across the channel. Also, we have focused on hydrophobic interactions on and around graphene sheets and nanotubes. More precisely, the effect of hydrophobic interactions on formation of liquid vapor surface over graphene sheets and the resulting changes in structure of water molecule inside nanochannel.
To gain insight on water flow mechanism we want to study the correlation between various attributes of water molecules present inside nanochannel to determine if one attribute is being influenced or is dependent on another. We found that force experienced by water molecules inside the channel and average orientation angle of molecules had a very high degree of correlation. Also, there is high degree of correlation between z-coordinate of neighboring water molecules inside nanochannel.

Abstract

With the discovery of regulatory roles of RNA molecules, several scientific efforts have been made to understand its structural diversity. It has been shown that, apart from the normal and modified base and noncanonical base pairs involving them, protonated bases and protonated base pairs play an important role in shaping up the complex folded structure of the RNA molecule. But the process of protonation of nucleobases is energetically unfavourable in physiological pH. It is therefore expected that, in order to compensate the cost of protonation, the protonation induced charge redistribution and geometric changes will help the protonated base to participate in different higher order interactions such as base pair, base triple, base stack, etc. Quite a few efforts has been made in recent years to understand the kinetics and thermodynamics of the process of protonation and stabilization of the protonated bases. We have observed that there is a lack of relevance with the physiological context in the methods adopted in most of those studies. Moreover, these studies mainly focus on describing the process of protonation as a function of the difference between pH of the local environment and average pKa of the nucleobase. Significance of local pKa values of different titrable sites of different RNA bases and influence of protonation on their stabilizing factors like noncovalent interactions, have not got much attention. For the sake of comparative analysis and completeness, in our study, we have considered deprotonation of RNA bases as well.
On the basis of the results obtained from advanced ab-initio quantum mechanical calculations, in this study, we therefore have proposed a physicochemically relevant method of studying the thermodynamics of the process of protonation in terms of estimation of site specific protonation propensities of RNA bases. It considers water molecule as proton donor. We have further tried to correlate the site specific protonation propensity data with the occurrence frequency of the protonated bases. We have noticed that the stability and hence the occurrence frequency of protonated bases do not depend only on their protonation propensity but the protonation induced modifications of stabilizing factors, such as, hydrogen bonding and pi-stacking potentials play a role of greater importance. We have extensively studied the case of protonated base pairs involving N7 protonated purines. Our study revealed that, although the N7 site of Guanine has a good protonation propensity, N7 protonated Guanine can not occur in the stable planar base pairs due to reasons explained by the protonation induced charge redistribution in Guanine. N7 protonated Adenine, on the other hand, can form stable and planar base pairs and we have explored two new geometries of base pairs involving N7 protonated Adenine -- A(+):G H:H Cis and Trans. Based on the charge redistribution over both the participating bases in a protonated base pair, we have also explained the stability of base triples involving protonated bases.
Our study therefore provides a systematic estimation of site specific protonation propensities of RNA bases and evaluates the influence of protonation on hydrogen bonding and pi-stacking via them. On the basis of the both it explains stability and occurrence frequency of protonated bases and base pairs involving them.