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.

Abstract

With the rapid advancements of communication and computational technology, theWorldWideWeb has witnessed a rapid growth in the user-generated content with more and more users actively creating, publishing and sharing content over the web. As a result, the web is now overloaded with information on varied topics contributed by diverse set of contributors. This phenomenon has given rise to the “big data” wherein lies a key problem of intelligently extracting the most relevant and accurate information specific to a user. With this, it is essential to provide more personalized web experiences to the user, where every user query is catered and satisfied according to her preferences. However, doing so would require extraction and understanding of the context and semantics of the content, which currently is not readily available. Moreover, automated systems show limited capabilities in performing the same task. This thesis is an attempt to utilize collective human intelligence to support extraction and understanding of the content over the web, which will in turn help to create personalized web experiences. In particular, we propose crowdsourcing based systems for the following tasks: 1) extracting user preferences, 2) extracting named entities, and 3) renarration of the web documents. First, we propose a friend sourcing based approach called as Crowd Consensus where we extract user preferences from the collected opinions from her friends and tested it with an online game called as Power of Friends. The current method of eliciting information is to pose direct questions to friends and expect a truthful response in return. Power of Friends, on the other hand, involves a novel way of identifying the unanimous opinion of all the friends about a question related to an individual. Next, we describe a system called as uPick, which extracts named entities and their relations from a given text and crowdsource these extracted named entities for validation. The existing systems built around the task of identifying associated relations among named entities within a text document lack human precision and they also struggle to handle erroneous documents. uPick helps to improve the accuracy of the generated relations by gathering judgments from the interested users and validate the relations based on the majority responses. Finally, we worked on a renarration framework to the web called as Alipi to make the multi-lingual documents accessible to the users. This framework supports alternative descriptions for a web page or parts of it via rewriting for a given target audience by volunteers. We developed a browser plugin to enable users to re-narrate any page and to render the requested page dynamically based on the user preferences. Our developed prototypes along with the studies show that leveraging human energy and skills have potential to provide solution to the problems that machines cannot accomplish solely. We hope our work would inspire system designers to consider crowdsourcing based systems for creating personalizing web experiences and to think beyond system efficiency and accuracy by focusing on the task experience and invested efforts by the users.

Abstract

Computational Geometry is regarded as an emerging subfield of computer science. In computational geometry the standard range searching problems are studied widely because they have many real-world applications in spatial informatics, VLSI design, geographical information systems, information retrieval, databases, computer vision, computer graphics and other areas. In the standard range searching problem on an object set S we either report points or count the number of points in a given query region q. But just reporting and counting points in the query region is not sufficient for real world applications like data mining where data analysis is the major concern. In order to support applications which require data analysis to capture significant features we compute an aggregation function over the given query region like Sum, Max, Average, etc. Range Queries with such aggregate functions are called range-aggregate queries. But to capture intricate geometric properties on the data set we do geometric aggregation. Some of the examples of geometric aggregation functions are skyline, convex hull, closest pair, Voronoi diagram, triangulation and so on. However, advances in the creation and archival of digital information have led to an information explosion and therefore the number of objects inside a query range can be huge. In such cases, reporting a sample of the result set is preferred. In this work we present solutions to two such geometrical problems which give such samples. Both skyline and convex hull concepts have wide applications to other problems like outlier detection, clustering and so on. Abstractly both skyline and convex hull concepts provide some type of ordering in higher dimensions. Intuitively we all know that ordering on a set of objects makes it more efficient for answering relevant queries by capturing significant features. Let S be a set of n points in the two dimensional plane. A point p = (p x ; p y ) is said to dominate another point q = (q x ; q y ) if p x > qx and p y > qy . Points not dominated by any point in the set are called maximal or skyline points. We preprocess S into a data structure such that we can efficiently compute maximal points or skyline for any given query q. We propose a linear space data structure which takes O(log n + k) query time for any given query q in the word RAM model where k is the total number of points that are reported. We solve this problem for 2-sided quadrant queries and 3-sided range queries. We not only report points inside the given query region but we also count the number of points in S q.

Abstract

Human beings use specific characteristics of people such as their facial features, voice and gait to recognize people who are familiar to us in our daily life. The fact that many of the physiological and behavioral characteristics are sufficiently distinctive and can be used for automatic identification of people has led to the emergence of biometric recognition as a prominent research field in recent years. Several biometric technologies have been developed and successfully deployed around the world such as fingerprints, face, iris, palmprint, hand geometry, and signature. Out of all these biometric traits, fingerprints are the most popular. This thesis is focused on improving the efficiency of fingerprint recognition systems using local minutiae based features. Initially, we tackle the problem of large scale fingerprint matching called fingerprint identification. Large size of databases (sometimes containing billions of fingerprints) and significant distortions between different impressions of the same finger are some of the major challenges in identification. A naive solution involves explicit comparison of a probe fingerprint image/template against each of the images/templates stored in the database. A better approach to speed up this process is to index the database, where a light-weight comparison is used to reduce the database to a smaller set of candidates for detailed comparison. In this thesis, we propose a novel hash-based indexing method to speed up fingerprint identification in large databases. For each minutia point, its local neighborhood information is computed with features defined based on the geometric arrangements of its neighboring minutiae points. The features proposed are provably invariant to distortions such as translation, rotation and scaling. These features are used to create an affine invariant local descriptor called an Arrangement Vector, which completely describes the local neighborhood of a minutiae point. To account for missing and spurious minutiae, we consider subsets of the neighboring minutiae and hashes of these structures are used in the indexing process. Experiments conducted on public databases show that the approach is quite effective and gives better results than the existing state-of-the-art approach using similar affine features. We then extend our indexing framework to solve the problem of matching of two fingerprints. We come up with a novel fixed-length descriptor for a minutia that captures its distinctive local geometry. This distinctive representation of each minutiae neighborhood allows us to compare two minutiae points and determine their similarity. Given a fingerprint database, we then use unsupervised K-means clustering to learn prominent neighborhoods from the database. Each fingerprint is represented as a collection of these prominent neighborhoods. This allows us to come up with a binary fixed length representation for a fingerprint that is invariant to global distortions, and handle small local non-linear distortions.Given two fingerprints, we represent each of them as fixed length binary vectors. The matching problem then reduces to a sequence of bitwise operations, which is very fast and can be easily implemented on smaller architectures such as smart phones and embedded devices. We compared our results with the two existing state-of-the-art fixed length fingerprint representations from the literature, which demonstrates the superiority of the proposed representation. In addition, the proposed representation can be derived using only the minutiae positions and orientation of a fingerprint. This makes it applicable to existing template databases that often contain only this information. Most of the other existing methods in the literature use some additional information such as orientation flow and core points, which need the original image for computation.

Abstract

Scene Classification has been an active area of research in Computer Vision. The goal of scene classification is to classify an unseen image into one of the scene categories, e.g. beach, cityscape, auditorium, etc. Indoor scene classification in particular is a challenging problem because of the large variations in the viewpoint and high clutter in the scenes. The examples of indoor scene categories are corridor, airport, kitchen, etc. The standard classification models generally do not work well for indoor scene categories. The main difficulty is that while some indoor scenes (e.g. corridors) can be well characterized by global spatial properties, others (e.g. bookstores) are better characterized by the objects they contain. The problem requires a model that can use a combination of both the local and global information in the images. Motivated by the recent success of the Bag of Words model, we apply the model specifically for the problem of Indoor Scene Classification. Our well-designed Bag of Words pipeline achieves the stateof- the-art results on the MIT 67 indoor scene dataset, beating all the previous results. Our Bag ofWords model uses the best options for every step of the pipeline. We also look at a new method for partitioning of images into spatial cells, which can be used as an extension to the standard Spatial Pyramid Technique (SPM). The new partitioning is designed for scene classification tasks, where a non-uniform partitioning based on the different regions is more useful than the uniform partitioning. We also propose a new image representation which takes into account the discriminative parts from the scenes, and represents an image using these parts. The new representation, called Bag of Parts can discover parts automatically and with very little supervision. We show that the Bag of Parts representation is able to capture the discriminative parts/objects from the scenes, and achieves good classification results on the MIT 67 indoor scene dataset. Apart from getting good classification results, these blocks correspond to semantically meaningful parts/objects. This mid-level representation is more understandable compared to the other low-level representations (e.g. SIFT) and can be used for various other Computer Vision tasks too. Finally, we show that the Bag of Parts representation is complementary to the Bag ofWords representation and combining the two gives an additional boost to the classification performance. The combined representation establishes a new state-of-the-art benchmark on the MIT 67 indoor scene dataset. Our results outperform the previous state-of-the-art results [58] by 14%, from 49.40% to 63.10%.