Abstract

Coloring is an abstraction for partitioning a set of objects into a few independent sets. The notion of independence and the associated coloring rules vary from context to context. In the simplest case, adjacent vertices in a graph are required to receive different colors ( proper coloring). In parallel scientific computing, a proper coloring is used to identify computational subtasks that can be performed concurrently. A proper coloring of vertices of a graph G is acyclic if every 2-colored subgraph of G is acyclic. The acyclic coloring problem arises in the context of matrix partitioning for the estimation of the Hessian matrix associated with numerical optimization problems. The smallest number of colors required to acyclically vertex color a graph G is called its achromatic number and is denoted by a(G). Finding the achromatic number, a(G), of a graph(G) is an NP-hard problem. Several approaches have been used to solve this problem. Some researchers looked at finding the achroamtic number of family of graphs such as planar graphs, planar graphs with large girth, 1- planar graphs, outerplanar graphs, and d-dimensional grids. Another direction of study is finding upper bounds on a(G) in terms of the maximum degree of G. Alon et al. used problabistic arguements and showed that it is possible to acyclically color any graph of maximum degree D , with O(D^{4/3}) colors. Fertin et al. designed a polynomial time algorithm to find upper bounds on a(G) in terms of D. This thesis is dedicated to designing deterministic algorithms to reduce upper bounds on a(G) for bounded degree graphs. By extending/generalizing ideas of Skulrattanakulchai we reduce upper bounds for a(G) for family of graphs of maximum degree five from 9 to 8 and, for the family of graphs of maximum degree 6 from 15 to 12 respectively. We show above result by extending a partial coloring by one vertex at a time. Let v be the vertex that we color during an iteration. During this process, in some scenarios it is required that we recolor some of the vertices already colored so as to make a color feasible for the vertex v, the vertex we try to color. However, note that this recoloring, if required, is limited to the neighborhood of the neighbors of v in all cases. We have presented a polynomial time algorithm to acyclically color the vertices of graphs with maximum degree D using D^2+2D+2/3 colors. The algorithm improves the state-of-the-art by a factor of 3/2 to the best known result till date. Our algorithm is greedy, and at each time we observed up to 3-neighborhood of a vertex even though recoloring is done up to 2-neighborhood of vertex.

Abstract

In recent times the discovery of several ncRNA (non coding RNA which does not code for proteins but directly performs structural and catalytic functions) genes have drawn progressively greater scientific attention to RNA studies and drawn renewed attention to the hypothesis of “RNA world” where RNA potentially has served the dual role as both the genetic material and as the principal biocatalyst. The non covalent interactions, which are responsible for folding of highly flexible and negatively charged sugar phosphate backbone of RNA molecules are far less understood, compared to those involved in protein folding. These interactions are relatively more complex than in regular DNA double helices, which are held together by canonical A:T and G:C Watson-crick base pairing, which is suited for structure and function of DNA molecules. In contrast, single stranded RNA molecules display a richer variety in base pairing patterns, which govern their folding on themselves into complex dynamic structures. Non canonical base pairs, which constitute ~ 40% of base pairing interactions in RNA (Leontis et al, 2001) have been recognized for their role in molecular recognition including proteins, ligands and metal ions and mediating numerous tertiary interactions. (Westhof et al, 2000) High concentration of charges has long since been identified as one of the major features distinguishing nucleic acids from proteins, in terms of their structure, activity and folding dynamics. Neutralization of the negatively charged backbone phosphate groups, involving metal counter ions, has e. g., been shown as one of the primary events in RNA folding in vitro.(Misra et al, 2003) However, there is now a growing acceptance of the fact that, apart from phosphates and metal cations, the nucleobases themselves can acquire charges through protonation. This development indicates a major change in paradigm, particularly with respect to the role of metal cations in nucleic acid folding and catalysis. It may be noted in this context, that the role of nucleobase protonation in nucleic acids goes much beyond general purpose neutralization – something which the metal cations ubiquitously perform. Several studies have pointed towards more specific roles, including the mediation of global conformational changes in DNA as well as in RNA structures, whereby the protonation of nucleobases in specific macromolecular contexts may be important for defining their catalytic roles and folding pathways. In general, nucleobases do not get protonated at physiological pH, since the pKa values for imino nitrogens are ~ 3.5 and 4.2 for adenine and cytosine respectively, and ~9.2 for guanine and uracil. (Saenger, 1984) It is thus important to understand the basis of context dependent pKa shift which leads to protonation of nucleobases in different cases. Based on their occurrence contexts and functional features, protonated nucleobases identified in known structures have been divided into two classes, (Bevilacqua et al, 2005) viz. Class I, for which the loaded proton is sequestered in hydrogen bonding between paired bases, and class II sites, where the proton is not directly involved in base pairing. Of these, we have investigated Class I type of interactions. For the detection of these base pair types, we have extended available methods (Das et al, 2006) of base pair detection for detecting putative protonated base pairs and understand their contexts. We have also used advanced quantum chemical methods, both to confirm their occurrence as well as to study their geometries and stabilities. We have used a non redundant dataset of selected highresolution RNA crystal structures (PDB ids given in Appendix) from Protein Data Bank (PDB) to analyze the geometries and analyze the occurrence contexts of base pairs belonging to protonated base pair. Out of twelve RNA base pair geometric families described by Leontis-Westhof classification scheme (Leontis and Westhof, 2001), we have identified eighteen possible protonated base pairs spanning eight base pair families. In addition, we also report a putative base pair on the basis of modeling. Out of nineteen distinct possibilities studied in this work, as many as six instances needed hypothesis driven manual intervention for addressing ambiguities; which arouse due to variety of factors , and which were resolved to different degrees using quantum chemical methods. Out of nineteen distinct geometries studied in this work, nine base pairing geometries are new, and not previously being detected in nucleic acid structures. These base pairs have potential to nucleate higher order structures and participate in tertiary interactions joining distant regions in RNA structures. The interaction patterns of protonated base pairs are highly diverse, with gas phase optimized interaction energies in the range from -24 to -49 Kcal/mol. The high interaction energy is generally observed for

Abstract

In the emerging web databases and e-commerce scenario, information systems have to meet intensive information requirements from a large number of users. These information systems receive both update transactions (UTs) and read-only transactions (ROTs). A UT contains both read and write operations and an ROT contains only read operations. Designing efficient protocols to process ROTs is a research issue. There are three aspects for designing a concurrency control protocol for processing ROTs: correctness, data currency and performance. The protocol should process transactions by satisfying serializability criteria. Also, the protocol should process transactions without any data currency issues. Note that “data currency” is another important aspect of the protocol. A protocol should process the ROTs without missing the effect of any preceding UTs. Finally, the protocol should give high performance. If both the UTs and ROTs are processed with the popular two-phase locking (2PL) protocol, the performance degrades with the data contention as the UTs have to wait for ROTs and vice versa in case of a conflict. On the other hand, it can be noted that, the 2PL processes ROTs without any correctness and data currency issues. So, efforts are being made to propose improved protocols by exploiting the special property of ROT that “it does not modify the data” and by compromising on correctness and data currency. There are efforts to improve the performance by processing ROTs with multi-version based approaches, at lower isola tion levels, and by compromising correctness. One of the popular protocols is snapshot isolation (SI)-based protocol, in which an ROT reads the snapshot of the database ignoring modifications done by preceding UTs. In SI-based protocols, even though performance is improved, both correctness and data currency aspects are compromised. The 2PL protocol suffers from the performance problems and SI-based protocol suffers from both correctness and data currency problems. So, the research challenge is to develop efficient concurrency control protocols to improve the performance of ROTs without correctness and data currency problems. In this thesis, we have proposed speculation- and semantics-based protocols for processing ROTs that provide high performance and process transactions without any correctness and data currency issues. Speculation-based protocols have been proposed in the literature to improve the performance of UTs. Basically, under speculation, a transaction carries out multiple executions by reading the uncommitted values of preceding conflicting transactions. A transaction retains one of the speculative executions based on the termination decisions of preceding transactions. Speculation improves the parallelism but requires extra processing resources. Also, the number of speculative executions and number of object versions explode with data contention. In this thesis, the notion of speculation is being extended to propose improved protocols for processing ROTs. In the proposed protocols, ROTs are processed with speculation and UTs are processed with 2PL. The ROTs access after-images produced by UTs and carry out speculative executions. As a result, the following advantages have been identified: (i) an ROT can carry out speculative executions and commit independently based on the status of preceding UTs, and (ii) the number of speculative executions and data versions is significantly reduced. We have proposed two speculation-based protocols for processing ROTs. In the synchronous approach, the speculative executions of an ROT can be carried out in a synchronous manner, i.e., all the speculativeexecutions of an ROT are carried out at the same pace. In the asynchronous approach, the speculative executions of an ROT are carried out at different pace. It was observed that asynchronous approach improves the performance over the synchronous approach. In the proposed speculation-based protocols for ROTs, UTs follow 2PL and are made to wait if they conflict with concurrent UTs and ROTs. To reduce the waiting time of UTs, we have proposed a semanticsbased approach by proposing the notion of “compensatability”. In this protocol, a UT need not wait for an ROT, if the computation of that ROT is compensatable. However, the compensatable ROT has to perform compensating computations before its commitment. We have proposed enhanced protocols by extending semantics to the proposed speculation-based protocols. The proposed protocols bring significant benefits. The ROTs are processed without violating correctness and compromising data currency. The performance results show that the proposed protocols significantly improve the performance over 2PL and SI-based protocols with manageable extra processing resources.

Abstract

The detailed molecular level understanding of physicochemical interactions responsible for the overall architecture and dynamics of functional RNA molecules embodies a major challenge to the scientific community. The 3D architecture of RNA is mainly influenced by various non covalent interactions such as hydrogen bonding and stacking interactions between the nuleobases, interactions involving the sugar and phosphate backbone and interactions involving the solvent molecules and metal cations. A proper description of all these non covalent interactions and their involvement in various recurrent structural motifs help us to understand the physicochemical principles which are crucial for the complex structure, folding and functional dynamics of RNA molecules. Current approaches in mining are constrained by their dependence on identification of strong hydrogen bonded canonical and noncanonical base pairs and motifs and are thus restricted by conventional stability benchmarks. Collections of several weak, 'non-base specific' interactions, found in structurally, as well as functionally, important regions such as A-minor motifs, tetraloops and in various tertiary interactions are often not detected by these algorithms. In this work, we have used a comprehensive BOTTOMUP approach towards understanding structure. This task has been achieved by studying 'weak' and 'other than stable base pairing' contacts from a reduced redundancy dataset of functional RNA molecules by applying a python based in house developed tool INCAR (Inter-Nucleotide Contact Annotator in RNA), which efficiently manages time and space to capture, categorize and suitable annotate all inter-nucleotide non-covalent interactions such as hydrogen bonding and ion mediated contacts. A new automated centroid based approach which doesn't require a priori knowledge on standard base pair geometries and atoms involving in hydrogen bonding is designed for detection of glycosidic bond orientation of various standard and nonstandard base pairing geometries ( bifurcated, single hydrogen bonded, deformed).Results are with high specificity with out compromising on sensitivity with respect to currently analyzed benchmarks. Other key features include a) Classification of bifurcated geometries, b) Classification of higher order interactions such as triplets, quartets etc. based on spatial topologies. c) Identification of various structural elements such as platforms, bulges, loops, stems etc. We have identified a new structurally important AA-Diloop and an interesting tertiary interaction in a ribozyme involving weak and 'non-base specific' contacts. In addition, INCAR has applied in several areas such as comparative analysis to investigate the structural conservancy of a class of sequence variants, investigating motifs in terms of 'non-base specific' contacts and dynamic structural analysis of RNA molecules. A repository has been developed for (http://web.iiit.ac.in/~ramsagar.bpg08/incardataset) archiving details of the analyzed RNA structures using INCAR.

Abstract

Text summarization is the process of distilling the most important information from a source to produce an abridged version for a particular user or task. That is restating of the main ideas of the text in as few words as possible in a pertinent format. Automated text summarization has drawn a lot of interest in the natural language processing and information retrieval communities in the recent years due to the rapid growth of the World Wide Web and electronic information services. Information is becoming available on-line at an incredible rate but no one has time to read everything. Hence, the technology of automatic text summarization is becoming indispensable for dealing with this problem. With the growing need for good summarization systems, summarization evaluation plays an important role in their creation. Evaluation has become one of the ongoing issue in this field of automatic text summarization. Human judgement often has wide variance on what is considered a ”good” summary, which means that making the evaluation process automatic is particularly difficult. Manual evaluation like ’Likert Scale rating’, ’Pyramid Evaluation’ can be used, but this is both time and labor intensive as it requires humans to read not only the summaries but also the source documents. Hence, there is an urgent need for developing automatic evaluation metrics to fasten the process of evaluating summarization systems which can result in better summarizing algorithms. Summaries can be evaluated based on two properties : content and form. The evaluation of content is called ’Content Evaluations’ and that of form is called ’Readability Evaluation’. There are various manual evaluation metrics for content evaluation including ’Likert Scale rating’, ’Pyramid Evaluation’ and ’Content Responsiveness’. For Readability evaluations a ’Likert scale rating’ is used by human experts to rank summaries. In the context of automated metrics for evaluation of summary quality, content evaluations have been presented through the last decade and continue to evolve. However, a careful examination of readability aspects of summary quality has not been as exhaustive. In this thesis, we dissect readability into 5 parameters and automate the evaluation of readability based on some of these parameters. Readability of a summary is usually graded manually on five aspects: grammaticality, coherence, focus, referential clarity and nonredundancy. We explore alternative evaluation metrics for grammatvviicality, focus and coherence. By defining grammaticality as a degree of acceptance, we use language models built over shallow features such as parts-of-speech (POS) and chunk tags to estimate the acceptability of a sentence to be a part of the summary. To capture the coherence in a summary, we use lexical chains and compute semantic relatedness of the sentences within the summary. We claim that the focus of a summary is a characteristic dependent on the cohesiveness of a summary, due to which, any metric for coherence should be a good indicator of focus. Our approaches to capture grammaticality, focus and coherence are able to strongly correlate with manual ratings. Overall, in context of query focused multi-document summaries, we observe that none of the five aspects of readability are independent of each other, and hence by addressing the individual criteria of evaluation, we aim to achieve automated appreciation of readability of summaries.

Abstract

Data Mining is a technology that blends traditional data analysis methods with sophisticated algorithms for processing large volumes of data. It is the process of automatically discovering useful information in large data repositories. Data Mining includes extensively researched techniques like clustering, outlier mining, frequent itemset mining, classification and regression. In this thesis, we consider the problem of extracting the special properties of any given record in a relational dataset. We are interested in determining what makes a given record special or different from the majority of the records in a dataset. In the real world, records typically represent objects or people and it is often worthwhile to know what special properties are present in each object or person, so that we can make the best use of them. This problem has not been considered earlier in the research literature and led to the introduction of Speciality Mining. There are several scenarios where this Speciality Mining can be useful: A shopper can select from a range of products by analysing the special properties of each product in comparison with the other products. For example, there are many varieties of mobile phones in the market and it would be convenient for the customer to know how each mobile phone differs from the remaining group. “Speciality Mining” is based on the intuition that a record is special if it contains a property that is present in very few records. Intuitively, we say that a property is special if it is present in only a few objects. However, we argue that if similar properties are present in a large number of objects, then even such a property should not be considered special. For example, in a database of 20 people if only 2-3 persons know English, they are special with respect to the language attribute. However, if for every language in the database, there are only 2-3 people who know that language, then it means that all people are special with respect to the language attribute. This is absurd – if everyone is special, no one is truly special. To ensure that the above definition of speciality captures this intuition in an elegant fashion, we use ideas from information theory, cluster analysis and frequent itemsets. We also provide the speciality of records in a convenient, easily-interpretable manner. An illustrated example is provided on how users can interpret the results. Experiments on real and synthetic data sets reveal interesting properties of data records that cannot be mined using traditional approaches. Keywords: Cluster analysis, Frequent itemsets, Outlier, Surprisal.

Abstract

The exponential growth of world wide web has transformed it into an ocean of knowledge in which highly diverse information is linked in a extremely complex and arbitrary manner. It has become the repository for all the information needs of the users who search for answers to their diverse needs. Having been entrusted with the responsibility of serving the information needs of this ever- increasing pool of internet users, search engines, in order to sustain this highly competitive and huge market, are forced to mine this vast pool of information to serve information that is relevant, accurate and veritable. Typically, a search engine in these days, returns hundreds of results in response to a user query. The user is left with the painful task of mining these results to find the information needed. But sometimes, these results may not contain the information needed by the user and hence the user has to rephrase the query and restart the search session. The search engine which minimizes this process and makes it more user-friendly is bound to capture more market. Traditional search engines used to return generalized results for particular queries i.e., they used to rank the results based on query irrespective of the preferences of the searcher. But such generalized ranking of results may not satisfy all the searchers since each searcher is unique and has different information need(sometimes even in case of similar queries), different tastes and preferences. Hence, of late, search engines have started concentrating on fetching personalized results according to the taste of each individual user. For example, for a query “Sourav ganguly”, a user who likes both “Sourav Ganguly” and “Shahrukh khan” may be more interested in news about “IPL”, which has both the subjects involved in it, when compared to a user who does not like “Shahrukh khan”. Similarly, for a query “Apple”, a user who is a computer professional may like to know news about “Apple products” whereas a botanist or a dietician may want to know about “Apple” fruit. Thus search engines started focussing on knowing the tastes and preferences of the users and retrieve results that they might find more relevant. Personalization of search can be done by knowing information about the user like his topics of interests, his background knowledge on different topics and his browsing model. This user information can be known by posing a generalized set of questions to the user through which we can learn the information we need about the searcher which is called explicit feedback. But again, such generalized set of questions shall limit the extent to which we can learn the searcher and also such feedback is expensive to collect due to the amount of effort of the user involved. Hence researchers have sorted out a new type of feedback of late. Here, we collect the user interactions with the search engine without any effort from the user. Such feedback is called Implicit relevance feedback. Implicit relevance feedback has received wide attention recently as a means to capture the search context and improving search results. However, implicit feedback is usually not available to public or even research communities at large for reasons like being a potential threat to privacy of web users. Hence, researchers in personalization of search are compelled to generate their own datasets in lab environments. These datasets are generally domain-centric, uniform and restricted to a small set of users. But if we examine the feedback data from a real world commercial search engines, it may range over a number of domains, varying in subject and content and may involve millions of users. Thus, personalization algorithms trained on lab generated dataset may not satisfy a real world search user. Hence, it is difficult to experiment and evaluate web search related research, especially web search personalization algorithms. Given these problems, we are motivated towards creating a synthetic user relevance feedback data, based on insights from query log analysis. We call this Simulated feedback. We believe that simulated feedback can be immensely beneficial to web search engine and personalization research communities by greatly reducing efforts involved in collecting user feedback. The benefits from ”Simulated feedback” is that - It is easy to obtain and also the process of obtaining the feedback data is repeatable, customizable and does not need the interactions with the user. In this thesis, we describe a simple yet effective approach using Prognostic Search process for creating simulated feedback. In this approach, we create virtual users from the user profile data of real world users and simulate search sessions of these users. We propose two models to represent the user profile of a virtual user viz., “Skewed Mean Model” and “Probabilistic Bayesian Model”. We achieved high accuracy levels with both the models. But the

Abstract

Large scale pattern classification systems are necessary in many real life problems like object recognition, bio-informatics, character recognition, biometrics and data-mining. This thesis focuses on pattern classification issues associated with character recognition, with special emphasis on Malayalam. We propose an architecture for the character classification, and proves the utility of the the proposed method by validating on a large dataset. The challenges we address in this work includes: (i) Classification in presence of large number of classes (ii) Efficient implementation of effective large scale classification (iii) Simultaneous performance analysis and learning in large data sets (of Millions of examples). Throughout this work, we use examples of characters (or symbols) extracted from real- life Malayalam document images. Developing annotated data set at the symbol level from a coarse (say word-level) annotated data is addressed first with the help of a dynamic program- ming based algorithm. Algorithm is then generalized to handle the popular degradations in the form of cuts, merges and other artifacts. As a byproduct, this algorithms allows to quantitatively estimate the quality of the books, documents and words. The dynamic programming based algorithm aligns the text (in UNICODE) with images (in Pixels). This helps in developing a large data set which could help in conducting large scale character classification experiments. We then conduct an empirical study of classifiers and feature combination to explore their suitability to the problem of character classification. The scope of this study include (a) applicability of a spectrum of popular classifiers and features (b)scalability of classifiers with the increase in number of classes (c) sensitivity of features to degradation (d) generalization across fonts and (e) applicability across scripts. It may be noted that all these aspects are important to solve practical character classification problems. Our empirical studies provide convincing evidences to support the utility of SVM (multiple pair-wise) classifiers for solving the problem. However, a direct use of multiple SVM classifiers has certain disadvantages: (i) since there are nC2 pairwise classifiers, storage and computational complexity of the final classifier becomes high for many practical applications. (ii) they directly provide a class label and fail to provide an estimate of the posterior probability. We address these issues by efficiently designing a Decision Directed Acyclic Graph (DDAG) classifier and using the appropriate feature space. We also propose efficient methods to minimize the storage complexity of support vectors for the classification purpose. We also extend our algebraic simplification method for simplifying hierarchical classifier solutions.We use SVM pair-wise classifiers with DDAG architecture for classification. We use linear kernel for SVM, considering the fact that most of the classes in a large class problem are linearly separable. We carried out our classification experiments on a huge data set, with more than 200 classes and 50 million examples, collected from 12 scanned Malayalam books. Based on the number of cuts, merges detected, the quality definitions are imposed on the document image pages. The experiments are conducted on pages with varying quality. We could achieve a reasonably high accuracy on all the data considered. We do an extensive evaluation of the performance on this data set which is more than 2000 pages. In presence of large and diverse collection of examples, it becomes important to continu- ously learn and adapt. Such an approach could be more significant while recognizing books. We extend our classifier system to continuously improve the performance by providing feed- back and retraining the classifier. We also discuss the limitations of the current work and scope for future work.

Abstract

The signi¯cant growth in computational power of modern Graphics Processing Units (GPUs) cou- pled with the advent of general purpose programming environments like NVIDIA's CUDA, has seen GPUs emerging as a very popular parallel computing platform. A lot of work has gone into successfully implementing a large number of algorithms on the GPU. While there is a general consensus on what types of algorithms can successfully leverage the computing power of the GPU's, there is no way to ascertain how much faster the algorithm will be as compared to a sequential version or how it will compare with an alternative algorithm for the same task. In other words this is the analytical equivalent of stating that The only way to ¯nd out how fast an algorithm is, is to implement it and measure it's running time". This clearly demonstrates a huge gap in our understanding of GPGPU computing. A performance prediction model for the CUDA GPGPU platform is presented in this thesis. This model encompasses the various facets of the GPU architecture like scheduling, memory hierarchy, and pipelining among others. We also perform experiments that demonstrate the e®ects of various memory access strategies. The proposed model can be used to analyze pseudo code for a CUDA kernel to obtain a performance estimate, in a way that is similar to performing asymptotic analysis. To validate the model the analysis of three fundamental Parallel algorithms is performed: Matrix multiplication, List ranking, and Histogram generation. To further illustrate the power of our model, two symmetric key encryption algorithms Blow¯sh, The Advanced Encryption Standard (AES) and their secure versions are implemented and analyzed. These encryption algorithms prove to be particularly close to most real world algorithms as they contain a mix of heavy computation, irregular memory access and the movement of large amounts of data.

Abstract

Words can have more than one distinct meaning and many words can be interpreted in multiple ways depending on the context in which they occur. This phenomena poses challenges to Natural Language Processing systems. State-of-the-art methods to resolve word ambiguity make use of manually annotated data. However, obtaining such data is costly for certain languages and domains. In this thesis we have developed word sense disambiguation (WSD) methods for languages and domains where no annotated data is available. We have proposed unsupervised corpus based methods for Semantic Category Labeling, a task very similar to assigning coarse grained WSD and hence relatively easier than traditional WSD. Methods that rely on lexical knowledge base (WordNet) are also evaluated. Furthermore, we have developed methods for domain-specific WSD and evaluated our performance on “domain specific WSD of all words” task which is a part of ACL SemEval- 2010. The results reveal the importance of domain information in domain-specific WSD. Very little work has been reported on integrating various knowledge sources for WSD. Current methods for WSD take advantage of only a few knowledge sources and do not use them collectively. We propose a novel framework which can model information from various knowledge sources into constraints and collectively use them for disambiguation. Our initial experimental results are competitive with that of state-of-the-art methods.