Abstract

The role of Internet in personal, economic and political advancement is growing in a fast pace. By the turn of century, data on web reaches to petabytes or exabytes or may even scale up-to unimaginable quantities. Extraction of precise and structured information from such large amounts of unstructured or semi-structured data is the major concern of web known as Information Extraction. Named entity recognition (NER) (also known as entity identification and entity extraction) is one of the important subtask of information extraction that seeks to locate and classify atomic elements in text into predefined categories such as the names of persons, organizations, locations, monetary values, percentages, expressions of times, etc. NER has many applications in NLP, for e.g., in data classification, question answering, cross language information access, machine translation system, query processing, etc. Recognizing Named Entities (NEs) in English has reached accuracies nearing to 98%. For English, many cues aid to know the structure of language (one such important cue in identifying NEs is capitalization) which made the accuracies to be high. Whereas in Indian languages, there are no such cues available and moreover each Indian language differ from the other in grammatical structure. Hence, developing a language independent NER is a challenging task. Previous works includes developing an NER system using language dependent tools such as POS Tagger, dictionaries, Chunk Tagger, gazetteer lists, etc., or they have used linguistic experts to manually tag the training and testing data or linguistic experts used to generate rules for recognizing NEs. Language Independent approaches include supervised machine learning techniques such as CRF, HMM, MEMM, SVM, etc. These techniques need High amounts of manually tagged data which is again a point of concern. Some of the other approaches include exploiting the external knowledge such asWikipedia. But, in those methods the utilization of Wikipedia is not complete. Hence, the main objective of this work is to build a language independent NER system without any manual intervention and without any usage of language dependent tools. The approach specified throughout the work, includes language independent methods to identify, extract and recognize the NEs. Identification of NEs is done using an External Knowledge namely Wikipedia. More specifically, English Wikipedia is used as an aid to derive the NEs from Indian languages. Wikipedia hierarchal structure is explored and the documents in it are divided into specific domains. Each domain is considered and the corresponding English and Indian language documents are clustered. English documents are tagged using the Stanford NER Tagger and the non-NEs are removed. Using the term co-occurrences between the tagged English and non-tagged Indian language words, the corresponding NEs between Indian language and English are mapped. Thus the tag of English NE is duplicated to the Indian language NE. Hence, the Indian language data is tagged. The tagged data generated in previous step, is used in recognition of NEs on sets of monolingual Indian language documents. In this step, a set of features are generated from the words of these documents and these features are used for recognition of NEs in a new document. Consider each document; extract the tagged data from the document using the data from previous step. Now, from the remaining words of the document, a Naive Bayes Classifier is build which uses these words to generate a set of features for each class (features here are nothing but the important words of a particular class in that document). The importance of these features is calculated statistically by different metrics (the metrics for classification). Now given a new document, the presence of these features along with their scores is calculated. If the score exceed a threshold, implies the presence of NEs in the document. By decreasing the size of document the process is repeated again till we get the NE. Hence, the monolingual Indian language document is tagged. The approach specified in identifying and recognizing the NEs is language independent and can be extended to any language as none of the language dependent tools are used or there is no involvement of linguistic experts. Hindi, Marathi and Telugu were the languages in which the work has been done. PERSON, LOCATION and ORGANIZATION were the tag of NEs used throughout the identification and recognition process. Wikipedia is used as a dataset in identifying the NEs. Around 3,05,574 English documents, Hindi 100,000 documents, Marathi 83,000 documents, Telugu 85,000 documents are used to generate the results. The results are evaluated on manually tagged 2328, 1658, 2200 Hindi, Marathi and Telugu Wikipedia documents respectively. The F-Measure scores are 80.42 for Hindi, 81.25 for Marathi and 79.98 for Telugu. Dataset for recognition of NEs is a

Abstract

For long it has been argued that metaphor is not merely a linguistic device used figuratively in poems and literature, but a conceptual process that plays a central role in cognition. Several attempts have been made to consider metaphor as a conceptual phenomenon (Ortony, 1979; Lakoff & Johnson, 1980). Most notably, Richards (1936) argued “that thought is metaphoric and proceeds by comparison, and the metaphor of language derive there from” (1936:94). Lakoff and his colleagues proposed conceptual theory of metaphor and argued that human cognition is organized in conceptual schemas, which are metaphoric in nature. These schemas are constantly enriched and modified by the interaction with the world. Language draws on these cognitive schemas but is not identical with them. Moreover, verbal metaphors are surface manifestations of the metaphorical grounding of these schemas. Therefore, metaphor is ‘fundamentally conceptual, not linguistic in nature’ (Lakoff, 1993). One of the crucial outcomes of this cognitivist paradigm is its implication that metaphor can assume non-verbal and multimodal manifestations as well. The focus of this thesis is on visual metaphors, which are pictorial counterparts of verbal metaphors such as “The sky is crying,” or “The man is a wolf.” Visual or pictorial metaphor is nonverbal manifestation of metaphorical thought, where one or both concepts of the metaphor (the target and the source) are depicted in images. In this thesis, our aim is to study different kinds of visual metaphors: How are they generated and how are they different from verbal metaphors. We focus on the difference between them at the presentation level, which relates to the early stages of perceptual processing. A verbal metaphor is presented as text but a visual metaphor is presented in images. Several psychological studies (Paivio, 1989; Schnotz & Bannert 1999) have shown that text and images are processed in different ways. Recent brain imaging studies have also confirmed that the right-hemisphere of the brain is specialized to process visual information (Bryden, 1982; Ellis et. al., 1988; Jonides et. al., 1993; Kosslyn et. al., 1993; McCarthy et. al., 1994; Smith et. al., 1995), whereas the left-hemisphere mostly processes linguistic or alphabetic information (Beaumont, 1982; Binder et. al., 1995; Desmond et. al., 1995; Gabrieli et.al., 1996; Howard et. al., 1992). We assume that this difference in perceptual processing is also reflected in high-level semantic processing tasks such as metaphor.

Abstract

Controlling molecular processes using lasers has been a long cherished dream since their invention in the 1960s. Of the several control schemes subsequently developed, Quantum Optimal Control Theory (QOCT) has been one of the most successful for the theoretical design of laser fields for driving molecular systems to accomplish specified objectives. In this work, we attempt a reformulation of the quantum optimal control problem for controlling vibrational motion in a molecule using an external laser field and under the constraint of reasonable fluence and evolution governed by the Schr¨odinger equation in Hilbert space. We do this by transforming the Schr¨odinger equation into a set of Hamilton’s equations in new phase space coordinates. We study the characteristics of dynamics in the K¨ahler space thus generated. We examine the geometric interpretation of this dynamics and reformulate the quantum optimal control problem as a classical control problem. We apply Pontryagin’s maximum principle to this classical control problem and explore its consequences for the quantum description. We examine in particular, controllability of the system and investigate how it changes in going from the original quantum problem to the classical-like reformulation. We speculate the role of adjoint variables in the reformulation as possible Lyapunov exponents in the classical-like phase space.

Abstract

A K -Nearest Neighbor based classifier classifies a query instance based on the class labels of its neighbor instances. Although kNN has proved to be a ubiquitous classification/regression tool with good scalability, but it suffers from some drawbacks. Two of its major drawbacks are: (1) The existing kNN algorithm is equivalent to using only local prior probabilities to predict instance labels, and hence it does not take into account the class distribution around the wider neighborhood of the query instance, which results into undesirable performance on imbalanced data. (2) It uses all the training data at the runtime and hence is slow. In this thesis, we provide a suite of solutions to tackle this drawbacks. BINER: We propose a new efficient technique for regression. Our algorithm instead of directly predicting the value of response variable, narrows down the range in which the response variable has the maximum likelihood of occurrence and then interpolates to give the output. The data is Hierarchically partitioned in the pre processing step, and search for the partition in which the response has the maximum likelihood of occurrence is carried out at the run time. It takes a single parameter k, the same as in kNN and more than often outperforms the conventional state of art methods on a wide variety of datasets as illustrated by our experimental study.

Abstract

Real world phenomena, in various domains including climatology, ecology, environment(natural); diseases, theft, urbanization (man-made), are largely dynamic and their evolution over space and time is central to our understanding of the science behind them, including the processes. Such phenomena have agreat impact in the regions where they occur raising a need to assess their behavior – regions where they occur, the duration of occurrence, extent of influence etc., to help manage them suitably. Current approaches focus on collection of snapshots of data at certain intervals of time. Though this approach provides an insight into the state of the event at given times and how changes occur from one snapshot to other, it is inadequate to explain and analyze the dynamic processes. A significant amount of work has been done in spatio-temporal change analysis such as detecting land use change as part of global and regional environmental change. While trying to find major changes, we tend to ignore places with minimal changes, whose invariant behavior might give important clues about the process under study. For instance, the localized behavior of climate, especially rainfall, has been well investigated in recent years to understand the dynamics of such a phenomenon with varied outcomes. It is observed that to better understand the controlling and regulating factors, in addition to identifying or locating the change and its quantum, there is also a need to understand the invariant behavior that the phenomena exhibits. Therefore, this study focuses on the detection of these invariant regions for a given phenomenon.A region can be a single or a set of representative points, with a defined property. Given the dynamic nature, this information can be really useful not only to understand the phenomenon better but can be used as reference points for sampling/interpolation. In this thesis, we propose MiSTIC, a data format generic method based on watershed delineation, neighborhood analysis and frequent item mining to identify the set of spatially distributed regions highly influenced by a phenomenon over a period of time.The method involves both a spatial analysis step to detect focal points(representative points) and a spatio-temporal analysis over the entire data time period to identify Core regions orCores. As the nature of the cores is affected by the neighborhood in which it occurs, to understand their behavior, cores are classified as Cores with Contiguous points (CC) and Cores with defined Radius (CR). Further, the cores are sub-classified to determine the level of spatio-temporal invariance (confinement in space over time) by considering the frequency of occurrence of the focal points that constitute it. These are - Cores with Highly Dominating points (CHD), Cores with Less Dominating points (CLD) and Cores with No Dominating points (CND). Therefore, the frequent/predominantly occurring focal points capture the localized invariant behavior of a dynamic phenomenon whereas the neighborhood constraints capture the extent/degree of dynamic nature and direction of influence of the phenomenon, if any. The method proposed in this paper tries to detect such regions for all domains – climatology, environment, theft, diseases to name a few. The results are extracted by using location, time and attribute value (investigates where, when and what). For every domain, these invariant regions signify that there exist places where dynamic phenomenon is highly concentrated. Such detection can help in taking appropriate measures tounderstand and handle the phenomena. For instance, in case ofhigh occurrence of events with negative impacts like storms, theft, diseases, etc., detecting such localized occurrences can help better manage them. In addition, this study provides an insight into the area of influence of the phenomenon for a given time period. To demonstrate the generality of the proposed method and its applicability, a case study on Indian Monsoon rainfall and another on Theft in NSW, Australia has been chosen. The two datasets used in the two case studies have different time periods, different set of points for analysis and different data formats. It has been observed that the analysis in prior work on spatial data mining is restricted to a particular data format - either raster or vector. Though many suggest that their proposed approach will work for both the cases, it is not been well demonstrated. While in our study, it is clearly seen the method can be applied to a wide range of domains irrespective of the data format – Monsoon rainfall is captured in raster format whereas Theft pattern is analyzed for NSW LGAs which is polygonal data. In addition to this, ourstudy also highlights the use of topological distances and directionality while extracting relationships among entities based on an attribute varying across space and time. The use of topological relationships overcomes the need for data to be

Abstract

SAM-III riboswitch, found at the 5' untranslated region (UTR) of the MetK gene that translates into SAM synthetase in lactic acid bacteria, is involved in regulating methionine and S-adenosylmethionine (SAM) biosyntheses in these organisms. The riboswitch acts as an on-off switch at the translational level regulated by SAM, wherein the binding of SAM switches off the translation as it blocks the Shine-Dalgarno sequence, thereby preventing the ribosome from initiating translation. The riboswitch distinguishes between SAM and its close analog, S-adenosyl-L-homocysteine (SAH), and binds more tightly with SAM. Experimental studies have reported two mutually exclusive RNA conformations in the presence and absence of ligand and have proposed intermediary state of the riboswitch. The Shine-Dalgarno sequence region is reported to be crucial for both the ligand binding and also acts as the regulatory domain. In this study, we have used molecular dynamics (MD) simulations to understand the structural details of the on-off transition of the riboswitch. The riboswitch is seen to sample larger conformational space in the absence of the ligand compared to the presence of the ligand. The binding pocket and the Shine-Dalgarno - anti Shine-Dalgarno region undergo major structural changes consistent with the experimental data. The off- state of the riboswitch is seen to be stabilized energetically by the formation of a pseudo-duplex like structure comprising the adenine part of the ligand. The phenomenon of translation switch off is verified by using the interaction energies which clearly show that the Shine-Dalgarno sequence region is more stable in the bound form and hence is very difficult to disrupt for the ribosome.

Abstract

Today, our daily lives are constantly driven and influenced by services like social networking, personalized advertisements, cloud infrastructure etc. This makes any form of personal or professional data vulnerable to both security and privacy threats. User looses control over the data as soon as its published on the Internet. Recently, popular photo sharing service Instagram tried to change its privacy policy, giving itself the right to sell users’ information including their photographs to advertisers without any notification or compensation. With incidents like AOL and Netflix debacle, organizations are refraining from releasing customer data even after anonymization. This hinders future research and developments in many ways due to unavailability of customer data, behavior and patterns. Techniques like k-anonymity and l-diversity help to preserve user privacy to some extent but fails to provide any solid guarantees. Recently proposed, differential privacy provides promising results in this area with theoretical bounds on information leak and preservation of privacy even against the auxiliary information. However, differential privacy considers individual’s record independent of other data and can not be applied to linked data like social graph, time series etc. Furthermore, all these techniques compromise utility of the data while maintaining privacy. At present, two approaches are widely used to ensure security of the data. First one is based on SecureMultiparty Computations (SMC), where users communicate with each other using SMC protocol to securely evaluate any function on their data. SMC gives provable security without compromising utility of the data. However, the solutions based on the general protocol of SMC requires enormous computational and communication overhead, thus limiting the practical deployment of the secure algorithms. The second approach is to encrypt the data at the user end and perform any operations in the encrypted domain to preserve the confidentiality of the data. This leads to difficulty in performing various operations like search, retrieval and computations. Homomorphic encryption allows secure computations over encrypted data but its impractical due to high computational cost. In this thesis, we focus on developing privacy preserving, communication and computationally efficient algorithms in the domain of Data Mining and Information Retrieval. Specifically, we design efficient privacy preserving solutions for two widely used tasks - outlier detection and content based similarity search over encrypted data. Private computation of outliers among data collected from different sources has many applications in the area of data mining. First, we propose a novel algorithm of distance based outlier detection using Locality Sensitive Hashing (LSH) in a distributed setting where data is horizontally partitioned among data owners. We show that the proposed algorithm is scalable in case of large datasets with high dimensionality. Then, we extend our distributed outlier algorithm to propose an algorithm for private outlier detection that broke the previous known bounds of quadratic cost. We compare our algorithm with the state of the art technique and show that our algorithm is better both in terms of computational as well as communication complexity. Next, we explore the properties of hierarchical index structures and propose an algorithm for content based similarity search over encrypted data that do not reveal user query to the server. To the best of our knowledge, we are the first one to propose a definition and a scheme for the problem of Content Similarity Searchable Symmetric Encryption (CS-SSE). Finally, we extend our CS-SSE scheme for Private Content Based Image Retrieval, which is essential for many applications like searching health records using CT scans and patent search for logos. We also show that our algorithm achieves optimal computational cost with similar accuracy and privacy when compared to the existing techniques.

Abstract

E-commerce, buying and selling of products by electronic means, has become popular due to the emergence of World Wide Web. One of the vital components of e-commerce systems is recommender systems (RSs). The RS is employed as a part of e-commerce system to help users in finding products of their interest from a huge number of available products. The Collaborative filtering (CF) approach is one of the popular approaches employed to build recommender systems. The neighborhood formation is one of the key steps in collaborative filtering and influences the performance of recommender systems. In this thesis, we have made an effort to improve the performance of recommender systems by proposing two improved neighborhood formation methods. At first, we have extended the notion of lower-bound similarity to improve the performance of neighborhood formation in CF-based recommender system. For neighborhood formation, k-nearest neighbor (kNN) approach is followed to find k neighbors of a target user. Given a fixed k value, the approach finds k nearest neighbors using different similarity methods. We identified the following issue with the kNN approach. Due to fixed value of k, the users who have rated few products may get less-similar neighbors and the users who have rated more products may miss the genuine neighbors. In the literature, the notion of lower-bound similarity has been proposed as an alternative to the popular k-means approach to improve the clustering performance in which the clusters are extracted by fixing the similarity threshold. By extending the notion of lower-bound similarity, we have proposed a neighborhood formation approach by fixing the similarity threshold instead of k. With this approach, it was proposed that it is possible to get appropriate number of neighbors of a target user. The experimental results on real-world dataset, show that the proposed approach improves the performance over the existing kNN-CF approach.

Abstract

Cloud Computing is the technology that enables users to host their applications or subscribe to computing resources on remote servers in a pay-as-you-go model. The users access these applications and computing resources in the form of web services. These services offered by the Cloud providers can be broadly classified as: Software-as-a-Service (SaaS), Platform-as-a-Service (PaaS) and Infrastructureas- a-service (IaaS). The pricing models for different types of services vary from provider to provider. With massive improvement in the internet connectivity in recent years, many users and enterprises are favouring these kind of services as they save a lot of infrastructure and maintenance cost. MapReduce framework has received a wide acclaim over the past few years for large scale computing. It has become a standard paradigm for batch oriented workloads. It is usually run on large number of physical machines called as ‘nodes’ which are collectively termed as ‘cluster’. MapReduce framework suits very well to develop applications that can rapidly process huge amount of data in a distributed fashion over large clusters. This framework is widely used in the industry to analyse log files, index files, crawl the web, social media monitoring, data mining etc. MapReduce is fairly simple framework which only takes the code that needs to be executed and the data to be processed as input, while the rest of the processes is handled transparently from the user. Though there are many distributed paradigms, MapReduce has seen a wider scope in industry and academia because of its simplicity. It works on a simple master-slave architecture, where the jobs are submitted to the master, which divides them into smaller units and schedules them across the cluster. MapReduce is mostly used to run data intensive jobs which are usually very long and sometimes even run from days to months. Since the jobs may be very long, intelligent scheduling decisions help in reducing the overall runtime of the jobs. Given the scale at which the MapReduce applications work, reducing the overall runtime would have a direct impact on minimizing power consumption of the cluster. Since the cluster is comprised of heterogeneous commodity hardware, the scheduler has to face another challenge of scheduling tasks effectively on a limited diverse resource pool. The first problem that we address in this thesis is: Reduce the overall runtime of MapReduce jobs by intelligent scheduling. We propose an approach which tries to maintain harmony among the jobs running on the cluster, and in turn decrease their runtime. In our model, the scheduler is made aware of different types of jobs running on the cluster. The scheduler tries to allocate a task on a node if the incoming task does not affect the tasks already running on that node. From the list of available pending tasks, our algorithm selects the one that is most compatible with the tasks already running on that node. We bring up heuristic and machine learning based solutions to our approach and try to maintain a resource balance on the cluster by not overloading any of the nodes, thereby reducing the overall runtime of the jobs. We evaluate our algorithm on a variety of workloads and our results show that the proposed algorithm achieves substantial savings in runtime of the jobs when compared to Yahoo!’s Capacity scheduler. Our approach takes into account of the interoperability of MapReduce tasks running on a node of the cluster and ensures that a task running on a node would not affect the performance of other tasks. This requires the scheduler to be aware of the resource usage information of each task running on the cluster. The second problem that we address in this thesis is: Energy efficient and SLA aware scheduling of virtual machines in a data center. We propose algorithms which try to minimize the energy consumption in the data center duly maintaining the level of service that is formally agreed between the service provider and the user, termed as Service-Level Agreement (SLA). The algorithms try to utilize least number of physical machines in the data center by dynamically rebalancing the virtual machines based on their utilization. The algorithms also perform an optimal consolidation of virtual machines on a physical machine minimizing SLA violations. Our algorithms make sure that the physical machines are utilized to the maximum extent and put the low utilized physical machines to standby mode, by intelligently migrating the load on to other physical machines. In this part of work, we try to utilize least number of physical machines in the data center, there-by conserving energy. The virtual machines are consolidated on a physical machine based on the resource usage patterns in order to avoid any race condition for resources. To achieve close to perfect consolidation we follow a similarity model and the virtual machines are consolidated based on this similari

Abstract

The need for low power integrated circuits is well known because of their extensive use in the electronic portable equipments. On chip SRAMs (Static Random Access Memory) determine the power dissipation of SoCs (System on Chips) in addition to its speed of operation. Hence it is very important to have energy efficient SRAMs. This Thesis proposes energy efficient SRAM cells (6T and 5T) based on adiabatic principles and design modifications. Bulk of the energy in SRAMs is wasted during charging of the bit lines and discharging it to the ground during read and write operations. It is proposed to use adiabatic approach to collect this energy and recycle it. Based on this thought process a separate and simple adiabatic driver circuit has been designed and used for bit line charging. It is shown that in 6T SRAM, a total energy of the order of 50% over a given period and around 80% during write cycle can be saved by the help of this driver. With this adiabatic driver circuit working in conjunction with conventional 6T SRAM cell other performance characteristics like read stability, write ability, read and write delay etc have been found by simulation in addition to energy saving under varied conditions of memory operations. The effect of device parameters of the driver on total energy of the SRAM cell has been investigated. Further studies covered proposed SRAM cell arrays. With a view to increase energy saving further, the possibility of having adiabatic SRAM with single bit line for reading and writing is examined. This architecture improves the total energy saving further (90%). Feat SRAM is designed to get better speed of operation along with energy saving. All these investigations have been carried out by simulations using HSPICE with 65nm PTM models and JUN-CAP1 level 4 for diodes. Thus the thesis describes the investigations that are carried out to arrive at energy efficient adiabatic SRAM cells.