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.

Abstract

Automatic speech summarization is the task of generating a concise summary of a speech signal using a digital computer. The existing speech summarization systems rely on automatic speech recognition (ASR) transcripts and gold standard human summaries to generate summaries of speech signals. The limitations with these approaches are, ASR errors make summaries less usable by humans, also ASR systems are not available for all languages, especially for less resource languages and it takes considerable resources and effort in building one. Gold standard human summaries are not available for all speech signals and building them is tedious and time consuming task. In this work, we propose two techniques for summarization: 1) Exploiting anchor speaker role in broadcast news (BN) show to construct summaries, 2) A generalized ranking of speech segments based on prominence values of syllables in them. By analyzing manual summaries of news shows, it was found that anchor speaker segments are mostly picked in manual summaries. Therefore it is desirable for automatic summaries to exhibit this characteristic. We proposed two techniques to perform anchor speaker tracking, based on auto associative neural network model and Bayesian information criterion method. Audio summaries are generated for desired summary length by concatenating anchor speaker segments based on their positional features. These summaries are evaluated with the help of ROUGE, an automatic text summarization evaluation pack age by transcribing the audio summary into text. ROUGE-N metric measures the N-gram overlap between human reference summaries and the automatic summary. The f-measure scores of the proposed system for ROUGE-1 and ROUGE-2 metrics are 0.561 and 0.392 respectively. These scores showed that the system is capable of generating summaries that are as good as supervised speech summarization system trained using gold standard human summaries which achieved 0.553 and 0.382 for ROUGE-1 and ROUGE-2 metrics respectively. Also, we performed a task based evaluation where, humans were asked to listen to the summary and answer questions regarding the contents of a news show. The percentage of questions answered by the humans was 71 % for the proposed system which is better than 60.2 % of the supervised speech summarization system. The coherence of the summaries was also evaluated by asking the users to rate the summaries on a scale of 1-5 where 1 corresponds to very bad and 5 corresponds to very good. The mean opinion scores (MOS) of these ratings for the proposed method and the supervised speech summarization system are 4.05 and 3.2 respectively. The task based evaluation of these summaries by humans showed that, they prefer the summaries generated by the proposed techniques over the summaries generated by standard speech summarization methods. In other part of the work, a technique to rank segments in a speech signal using prosodic features that indicate importance is proposed. When humans convey message through speech, they attract listeners’ attention to information bearing parts of speech through variations in pitch, amplitude, duration and stress. Speakers make some words prominent and reduce other words. The proposed method computes syllable level prominence values as a function of syllable nucleus duration, sub-band energy (300-2200 Hz), and pitch variation and these values are used to obtain a segment level score, which is used for ranking the segment for summarization. It is shown that this type of scoring captures the prosodic information relevant to summarization in an unsupervised framework. We have also proposed a method to combine lexical and positional features with the prominence based scoring when text transcripts of speech signals are available. The proposed prominence based scoring captures complimentary information to lexical features derived from text transcripts of speech signals. The combination of these features perform better than the individual features. The proposed method was evaluated on two types of speech data; read style news speech and spontaneous telephone conversations. The proposed system based on prominence scoring achieved ROUGE-1 and ROUGE-2 f-measure scores of 0.508, 0.341 on read style news speech and 0.666, 0.464 on spontaneous conversations respectively. In read style speech the basic unit of extraction was obtained based on pause based segmentation which does not give semantically meaningful segments, where as in spontaneous telephone conversations we have considered speaker turns which are semantically meaningful units as basic unit of extraction.

Abstract

Conventional CMOS logic circuit design approaches rely on charging the output capacitive nodes to the power supply Vdd or discharging it to ground. This design approach has been widely used. For Low power applications, although there are many techniques both at circuit level and system level, a very fundamental source of energy dissipation is the discharge of the capacitor to ground. Every time a capacitor is discharged to ground, an amount of energy = 12 CV 2 stored in the capacitor is lost. This loss of energy can be prevented if instead of discharging the capacitor to ground, the charge or energy stored can be recycled. Another way of reducing the power consumption is to design the circuit in such a way that the charging of the capacitive node takes place very slowly. It has been observed that slowly charging the capacitor requires lesser energy than abrupt charging. Adiabatic circuits use the above two methods viz. slow charging and discharging, and charge recycling to minimize the power consumed. Several Adiabatic designs have been proposed in literature. Most of them achieve significant power savings in comparison to conventional circuits. Drawbacks of these circuits include complex circuit design for achieving simple operations, requirement of multiple clocks and/or requirement of complimentary input signals for controlling the charging/discharging process. The Current work is based on an existing adiabatic logic style known as GFCAL (Glitch Free and Cascadable Adiabatic Logic )which is simple and does not require complimentary signals or complex clocking. The GFCAL has a drawback that it uses junction diodes for controlling the charging and discharging of output nodal capacitance. Junction diodes are difficult to fabricate in a CMOS process and they are responsible for power dissipation due to the cut-in voltage drop across them. This work improves the circuit by replacing the diodes with transistors that control the charging and discharging process. The efficiency has gone up from 50% for GFCAL to about 60% for the modified circuit in comparison to conventional CMOS logic circuits. The modified design is found to work satisfactorily, is cascadable and simple block level implementations like adders have been demonstrated and verified to work with lower power consumption than conventional CMOS circuits.