Abstract

The World Wide Web (WWW) is a huge, widely distributed global source of information to web users. Web documents are broadly classified into: unstructured and structured documents. Users prefer structured documents when looking for a piece of information. Hence, in the past decade research community focused on mining structured information from unstructured documents and attempted to preserve them in the form of attribute-value pairs, tables, flow charts etc. But, the focus has been only on extracting information at document level or on particular domains like disaster, finance, medicine etc. The techniques never attempted to integrate the extracted information to common knowledge repositories like Wikipedia, DBPedia etc. Structured databases like Wikipedia, DBPedia etc are created through collaborative contributions from volunteers and organizations. Since they rely heavily on manual effort, the process of updating these databases is not only tedious and time consuming but is also fraught with many drawbacks. Hence, automatic updation of structured databases has become one of the hot topics of research in the past few years. Automatic updation of structured databases can be broken down into two sub problems: Entity Linking and Slot Filling. In this thesis, we address Entity Linking. Entity Linking is the task of linking named entities occurring in a document to entries in a Knowledge Base. This is a challenging task because entities can not only occur in various forms, viz: acronyms, nick names, spelling variations etc but can also occur in various contexts. Once named entities from documents are linked to entries in a knowledge base, information can be integrated across them. Current IE techniques can be used to extract information from documents. Person named disambiguation and Co-reference Resolution are two tasks that share a lot of similarities with Entity Linking. These tasks have attempted to link entities across documents but never attempted to integrate them into a common Knowledge Base. Our approach to Entity Linking begins with building of an Entity Repository (ER). ER contains information about different forms of named entities and is built using Wikipedia structural information like redirect pages, disambiguation pages and bold text from first paragraph. Our core algorithm for Entity Linking can be broken down into two steps : Candidate List Generation (CLG) and Ranking. In the CLG phase, we use the ER, Web search results and a named entity recognizer to identify all possible variations of a given named entity. Using these variations we obtain an unordered list of candidate nodes from the KB which can be linked to the given named entity in a document. In the ranking phase, we rank the unordered list of candidate nodes using various similarity techniques. We calculate the similarity between the text of the candidate nodes and the document in which the named entity occurrs. We experiment ranking using various similarity functions like cosine similarity, Na¨ıve Bayes, maximum entropy, Tf-idf ranking and re-ranking using pseudo relevance feedback. Our experiments show that cosine similarity and Na¨ıve Bayes perform close to state of the art and the Tf-idf ranking function performs better in some cases. Our approach was tested on a standard Entity Linking dataset provided as part of Text Analysis Conference (TAC) for Knowledge Base Population (KBP) shared task. We evaluated our approach using Micro-Average Score which is the standard evaluation metrics. We achieved very impressive MAS of 83% and 85% on TACKBP, Entity Linking 2009 and 2010 data sets, which secured top spot in these shared tasks respectively.

Abstract

Real-life city-traffic simulation presents a good example of multi-agent simulations involving a large number of agents (each human modelled as an individual agent). Analysis of emergent behaviors in social simulations largely depends on the number of agents involved (more than 100,000 agents at least). Due to large number of agents involved, it takes several seconds or even minutes to simulate a single second of real-life. Hence, we resort to distributed computing to speed-up the simulations. We used Hadoop to manage and execute multi-agent application on a small cloud of computers and used CUDA framework to develop an agent-simulation model on GPUs.

Abstract

In the internet environment, computers-based information systems are being employed to maintain large amounts of information to meet different users’ information requirements. The users interact with the system by inserting/updating/querying the required information. The information systems process the user requests by executing the update transactions (UTs) for inserts/updates and readonly transactions (ROTs) for queries. An ROT contains only read operations whereas an UT contains both read and update operations. Processing of ROTs in a correct and efficient manner is a research issue. Efforts are being made in the literature to propose improved approaches. The main issues in processing ROTs are correctness (serializability), ensuring data currency and high performance. Even though the popular two-phase locking (2PL) protocol processes ROTs correctly with no data currency related issues, its performance deteriorates with data contention. Snapshot-based algorithms have been proposed to improve the performance by compromising both data currency and correctness aspects. Recently, two speculative locking-based (SL-based) approaches have been proposed in literature for improving the performance of ROTs. In these protocols, UTs are processed with 2PL and ROTs are processed with SL. One is synchronous SL-based approach in which speculative executions are carried out in synchronous manner and another is asynchronous SL-based approach in which speculative executions are carried out in asynchronous manner. Overall, the SL-based protocols for ROTs improve the performance without compromising both correctness and data currency. However, the SL-protocols follow 2PL to process UTs. Under SL-protocols UTs are blocked if they conflict with ROTs. Semantics-based protocols have been proposed in the literature for improving the performance without blocking UTs if they conflict with ROTs. The notion of compensability of ROTs is being exploited to improve the concurrency. The SL-based approached have been proposed by considering centralized database environment. In this thesis, we have extended SL-based approaches for processing ROTs in distributed database system (DDBS). In addition, we have analyzed the performance of semantics-based protocols by considering TPC-C and TPC-W benchmarks. We have extended both synchronous SL-based as well as asynchronous SL-based locking, protocols to process ROTs in DDBS. While extending SL-based protocols, it has been identified that an ROT under SL-based protocols requires an additional commit phase and requires single round of communication. In addition it has been found out that, additional messages are required for making speculative versions available to ROTs during the execution phase of an update transaction. In spite of these overheads, the performance results show that the proposed protocols significantly improve the performance over 2PL and SI-based protocols. Similar to centralized case, the proposed protocols do not compromise both correctness and data currency aspects. The analysis of semantics-based protocol with TPC-C and TPC-W benchmarks has been carried out by identifying various types of conflicts among the pair of transactions in both benchmarks. The analysis showed that six out of the eleven cases are compensatable in TPC-C and eleven out of twelve UT-ROT conflicts are compensatable in TPC-W. The analysis indicates that semanticsbased protocol has a potential to improve the performance in a realistic scenario.

Abstract

Every data set has a story to tell and has a unique set of characteristics depending on various factors like (a) the domain of the data, (b) external factors forcing the data to follow some pattern, (c) data instances, (d) various dimensions and their data types, (e) interactions between the instances and the dimensions and (f) most importantly, the underlying patterns in the data set. Interactions are the various types of relationships that the instances and dimensions share; for instance, similarities, dissimilarities, nearest neighbor relations, or any other semantic relation defined over data instances and dimensions. Various knowledge discovery techniques aim to obtain these characteristics of data or parts of it - by analyzing the data, identifying common patterns (like classes, clusters and frequent itemsets) and anomalous patterns (i.e., outliers). With very large data sets, the summarized characteristics could also be large, in contrast to the small size they should ideally represent. Effective presentation of the summary of data is a great utility for the end-user. The aim of this dissertation is to capture data’s characteristics with the underlying patterns as clusters and outliers. And later, present a visual information thumbnail of the data’s characteristics for the user to analyze and understand the data and patterns. Capturing data’s underlying patterns is achieved with data clustering and outlier detection algorithms based on the concept of reverse nearest neighbors. This dissertation elaborates on the properties and behavior of reverse nearest neighbor sets useful in the process of detecting outliers and identifying clusters. We propose a suite of techniques to: (i) identify candidate outliers, (ii) identify clusters, (iii) identify local outliers, (iv) rank outliers, (v) obtain agglomerative clustering and finally (vi) obtain a stable clustering result. We also propose two cluster validity measures based on proximity graphs to evaluate the “goodness” of the clustering results. Visual information thumbnail is generated by using the results obtained from the clustering algorithm and the subspace data analysis done using nearest neighbors. The information thumbnail incorporates various levels of detail, displayed on-demand to the user.

Abstract

With the advancement of the internet, 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. Various research efforts have been going on to develop improved methods to automatically search and analyze such large amount of information on the internet. Most of the data on the internet is in textual form, hence text mining and text analytics, particularly information extraction has become an active research area in recent years, to extract interesting and useful information. In this thesis, we have made an effort to propose improved information extraction approach for better resume processing. One of the areas of interest in recent years, to both corporate and research community, has been information extraction from resumes. In the current scenario, big enterprises and corporations receive thousands of resumes on a regular basis. Currently available techniques or services filter thousands of resumes to some hundred potential ones based on the requirement of the available job position. Since these filtered resumes are similar to each other as per the filtering criteria, they have to manually look through each of the hundred resumes to select the appropriate candidate for the job. Hence, there is a need to automatically extract data from resume and mine information from it to help in selection process. We have investigated the problem of resume election from set of similar resumes and proposed an efficient framework to solve the same. We have extended the notion of special features employed in product selection environment and proposed improved information extraction approach for resume processing. A special feature is a feature of a given product which distinguishes it from other products. Normally a resume is a semi-structured document and contains sub-sections. Each sub-section contains information in different format. For example, the skill information exists as a set of skill names whereas experience section contains a paragraphs describing different types of jobs/projects. A resume may have specialty in skills and specialty in experience. We have made an effort to extract special features from the resumes and have proposed approaches to extract special skills and special experience. At first we improved the special feature extraction algorithm and extended it to skills sub-section of the resume. To extend the notion of special features to experience section, we first proposed a short-text labeling agorithm and used the proposed algorithm to label each paragraph for capturing the nature of experience. Next, we used the labels as features and find special experience information and organized the labels. We have performed experiments on real world data-set of resumes and obtained encouraging results. Overall, information extraction from resume is a complex task. Even though several products are available, not much related work is available. The proposed work is a part of initial effort.

Abstract

The genome of eukaryotes is packaged in the form of chromatin where DNA is coiled around nucleosomes. The cell type specific complex packaging of genome and regulation of gene expression is established by several factors like histone variants, post translational modification of histone tails and DNA methylation. The higher order genome packaging is established, interpreted and also recreated dynamically by several transacting protein and RNA factors. The interpretation and establishment of these events are also associated with the non coding functional elements like enhancers, repressors, boundary elements, hormonal and environmental stress response elements. The complex packaging of genome and differential expression of genes has evolved from yeast to human. During this process the number of protein coding genes was expanded to a lesser extent compared to the non-coding part of the genome. The evolution of complexity is parallel with two aspects of genome evolution. The expansion of the non-coding portion of genome from lower to higher organisms and also the protein and RNA factors that are associated with the non coding functional elements involved in genome packaging and regulation. We studied two such factors, Polycomb protein which is involved in maintenance of genes in silent state and Simple Sequence Repeats which are shown to be essential for genome organization and regulation.
Polycomb group (PcG) proteins maintain expression pattern of genes set early during development. Although originally isolated as regulators of homeotic genes, PcG members play a key role in epigenetic mechanism that maintains the expression state of a large number of genes. Polycomb (Pc) is conserved during evolution and while invertebrates have one Pc gene, vertebrates have five or more homologues. It remains unclear if different vertebrate Pc homologues have distinct or overlapping functions. We have identified and compared the sequence of Pc homologues in various organisms to analyze similarities and differences that shaped the evolutionary history of this key regulatory protein. Comparative analysis of these sequences led to the identification of a novel insect specific motif and several novel and signature motifs in the vertebrate homologues. Unique motifs acquired by each homologue have been maintained for more than 500 million years indicating their functional relevance in boosting the epigenetic ‘tool kit’. To support our bioinformatics findings we performed functional characterization of the homologues. Each homologue has a unique nuclear localization pattern indicating the functional diversity among the homologues. The transgenic expression of mouse Cbx2, Cbx4, Cbx6, Cbx7 and Cbx8 in Drosophila showed discrete effects. This study indicates that Cbx7 is the functional homologue of Drosophila Polycomb. Our functional studies on the conserved motifs indicated that the functional diversity of the homologues is achieved through the motifs that are uniquely conserved among each Cbx protein.
Simple Sequence Repeats are the major component of non-coding region of the genome. We studied the distribution of 501 possible perfect SSRs from monomers to hexamers. The genome sequences of 19 different organisms ranging from E.coli to human were analyzed. We observed a selective enrichment of repeats specific to eukaryotes, while some are enriched in lineage and some in a species specific manner. Some SSRs have unusual enrichment of longer size repeats in vertebrates. We also analyzed SSRs distribution in the context of different functional compartments of the genome and we found that ACG and CCG repeats are enriched around transcriptional start site (TSS). Selective enrichment of a minority of SSRs in lineage and species dependent manner indicates their association with evolutionary conserved factors and indicates that these elements are evolving like any other functional element. Our study helped us to understand the evolution of factors associated with complexity.

Abstract

Abstract Window in a building provides daylight, ventilation and the outside view. A well designed fenestration system usually provides sufficient daylight during the day but there is a problem of glare and heat. Usual glare control strategies deploy blinds or curtains which are not automated and these systems block the outside view when they are controlling the excess daylight. Emerging technologies such as electrochromic windows satisfy the purposes of glare protection and clarity of outside view but these systems are expensive. The developed system which is a multiple film based daylight control system for window is a cost effective solution which has been developed to maintain the illuminance level at task plane without blocking the outside view and to achieve energy saving by utilization of natural light. The developed system consists of three tinted films with visual transmittivities (Tvis) of 0.50, 0.20 and 0.02 which are stitched together to form a long sheet rolled over two motorized rollers mounted on top and bottom of window. This sheet operates in synchronization with a 2x55W dimmable compact fluorescent lamp (CFL) fixture place above the task plane. The system works on the principle of feedback control, which records the changes in light intensity on the task plane with the help of photo sensor placed on the ceiling, facing the task plane and accordingly adjusts the film-position as well as the control voltage of dimmable CFL to maintain the task plane illuminance within a tolerance of -10%, +25% of set point. Optimized use of solar illuminance saves energy used for the task lighting for the period from 8:00 to 19:00, which was found to be about 70% without occupancy sensor and 80% by using mobile phone as occupancy sensor. The experiment has been performed to work out practical problems and refine design to increase acceptability of the system for real-world applications. As the sheet is in between the two pans of the double glazed window by using reflective films, the amount of heat entering the room can be reduced. The corresponding results were calculated by developing a simulation model of proposed system. Along with HVAC energy savings, annual energy savings were calculated by simulation method. The simulation shows that developed system improves the total energy consumption. Overall, the developed system is a cost-effective solution for smart fenestration systems which not only provides dynamic sunlight control with glare reduction but also saves energy.This thesis report describes the design, implementation of the proposed system and the preliminary results for task light illuminance and energy savings achieved in laboratory setup. Also, it discusses the annual savings achieved due to use of proposed control system with the help of simulation results. Keywords: Daylight control, Dynamic envelope, Energy saving, Fenestration, Multiple film

Abstract

The present work deals with a detailed analysis of the structural and energetic features of base pairing interactions in RNA macromolecules. Crystal structures of RNA molecules provide examples of a fascinating variety of base pairing interactions, which play an important role in maintaining their three dimensional structures and in facilitating their functions. An accurate atomic level description of interactions in these well dened structural building blocks of RNA, and an understanding of their roles in higher order structures involving recurring motifs and tertiary interactions, is essential for understanding structurefunction relationship in these macromolecules. Some of these higher order structures and motifs are base triplets, quartets etc. in general, and dinucleotide platforms, kink-turn motifs etc. in particular. In the present work, a detailed analysis of base pairing geometries and interactions in RNA molecules is carried out using combined quantum chemical and structural (database) analysis methods. The role of base-base hydrogen bonding interactions in the formation of structural and functional motifs as mentioned above, is assessed. An eort has been made to project the conclusions drawn from gas phase quantum chemical computations on RNA base pairs in a wide biochemical context of their occurence in macromolecular RNA structures. In addition, two theoretical investigations into specic structural and functional contexts in nucleic acid systems are carried out- one involving the analysis of geometric and energetic features of ligand binding in a specic type of noncoding RNA- the purine riboswitches, and the other involving the interaction of gold clusters with a novel type of synthetically modied DNA- the size expanded DNA.

Abstract

The problem of document clustering is to arrange a set of documents into groups such that documents within a group are related to each other. Document clustering has been studied extensively because of the huge increase in the amount of digital text content online and also due to its wide applicability in areas such as web mining, information retrieval, etc. Typical document clustering algorithms have issues like handling high dimensionality, scalability, building an efficient hierarchy, good clustering accuracy, etc.

Abstract

The acoustic contrast perceived among the basic units (phonemes) of human speech is the result of dierent configurations of the articulatory system excited by dierent configurations of the excitation source. While one can perceive the combined eect of source and system in the speech, it is dicult to analyze and detect acoustic features corresponding to both the system as well as the source from the standard spectrum-based methods of analysis. Glottal stop and ejective sounds form an important class of phonemes in most of the Semitic languages such as Amharic, which dier from other phonemes mainly due to their source of excitation. Therefore the study of acoustic characteristics of speech including glottal stop and ejective sounds based on spectrum-based methods becomes dicult, as these methods reflect mostly the resonance characteristics of the vocal tract system,. The features in a spec- trographic display bring out the distinction between voiced and voiceless excitations. But it is dicult to derive details of the features of the source of excitation from spectrum analysis alone. This thesis proposes non-spectral methods of analysis to derive features of the source of excitation from the speech signal, and demonstrate their significance in the analysis of glottal stop and glottalized (ejective) sounds in Amharic. The features of excitation source such as the instant of significant excitation, strength of excitation, instantaneous pitch period and jitter, are derived using a technique based on applying zero frequency resonator to speech signal. The normalized residual of LP analysis is used to detect the instants of oral release. It is seen that these non-spectral methods of analysis can be used to extract some source related features more precisely than the spectral-based methods. Voice onset time (VOT), closure duration, and phonation quality and amplitude rising time (ART) of the post-target vowels are some of the production-based attributes of ejective sounds, which are derived using the excitation source features. Ejective sounds in Amharic are found to have longer closure duration and shorter VOT than their voiceless pulmonic counterparts at the same place of articulation. The first few glottal cycles of the vowels following the ejective sounds are found to have more creaky phonation than that of vowels following pulmonic voiceless sounds. Also, the amplitude of these vowels grows more slowly than that of vowels following voiceless pulmonic sounds. It is observed that ejective sounds in Amharic have shorter duration and higher strength of frication than their voiceless pulmonic conjugates. The acoustic realization of glottal stop sounds in Amharic is found to vary from a brief closure period followed and/or preceded by a few cycles of creaky phonation to a few glottal cycles of creaky phonation without any closure duration. Since creaky regions have irregular glottal cycles, creakiness is used as a primary measure in the analysis of glottal stop phonemes. The creakiness of the speech signal is measured using the cross-correlation coecient computed between successive pitch cycles. Once the acoustic characteristics of the glottal stop and glottalized (ejective) sounds are understood, the learned acoustic features are used to spot these sounds in continuous speech.