Abstract

In earlier times, computer systems had only a single core or processor. In these computers, the number of transistors on-chip (i.e. on the processor) doubled every two years and all applications enjoyed free speedup. Subsequently, with more and more transistors being packed on-chip, power consumption became an issue, frequency scaling reached its limits and industry leaders eventually adopted the paradigm of multi-core processors. Computing platforms of today have multiple cores and are parallel. CPUs have multiple identical cores. A GPU with dozens to hundreds of simpler cores is present on many systems. In future, other multiple core accelerators may also be used. With the advent of multiple core processors, the responsibility of extracting high performance from these parallel platforms shifted from computer architects to application developers and parallel algorithmists. Tuned parallel implementations of several mathematical operations, algorithms on graphs or matrices on multi-core CPUs and on many-core accelerators like the GPU and CellBE, and their combinations were developed. Parallel algorithms developed for multi-core CPUs primarily focussed on decomposing the problem into a few independent chunks and using the cache efficiently. As an alternative to CPUs, Graphics Processing Units (GPUs) were the other most cost-effective and massively parallel platforms, that were widely available. Frequently used algorithmic primitives such as sort, scan, sparse matrix vector multiplication, graph traversals, image processing operations etc. among others were efficiently implemented on GPU using CUDA. These parallel algorithms on the GPU decomposed the problem into a sequence of many independent steps operating on different data elements and used shared memory effectively. But the above operations -- statistical, or on graphs, matrices and list etc. -- constitute only portions of an end-to-end application and in most cases these operations also provide some inherent parallelism (task or data parallelism). The problems which lack such task or data parallelism are still difficult to map to any parallel platform, either CPU or GPU. In this thesis, we consider a few such difficult problems -- like Floyd-Steinberg Dithering (FSD) and String Sorting -- that do not have trivial data parallelism and exhibit strong sequential dependence or irregularity. We show that with appropriate design principles we can find data parallelism or fine-grained parallelism even for these tough problems. Our techniques to break sequentiality and addressing irregularity can be extended to solve other difficult data parallel problems in the future. On the problem of FSD, our data parallel approach achieves a speedup of 10X on high-end GPUs and a speedup of about 3-4X on low-end GPUs, whereas previous work by Zhang et al. dismiss the same algorithm as lacking enough parallelism for GPUs. On string sorting, we achieve a speedup of around 10-19X as compared to state-of-the-art GPU merge sort based methods and our code will be available as part of standard GPU Library (CUDPP). It is not enough to have a truly fine-grained parallel alogrithm for only a few operations. Any end-to-end application consists of many operations, some of which are difficult to execute on a fine-grained parallel platform like GPU. At the same time, computing platforms consist of CPU and a GPU which have complementary attributes. CPUs are suitable for some heavy processing by only a few threads i.e. they prefer task parallelism. GPUs is more suited for applications where large amount of data parallel operations are performed. Applications can achieve optimal performance by combining data parallelism on GPU with task parallelism on CPU. In this thesis, we examine two methods of combining data parallelism and task parallelism on a hybrid CPU and GPU computer system: (i) pipelining and (ii) work sharing. For pipelining, we study the Burrows Wheeler Compression (BWC) implementation in Bzip2 and show that best performance can be achieved by pipelining its different stages effectively. In contrast, a previous GPU implementation of BWC by Patel et al. performed all the tasks (BWT, MTF and Huffman encoding) on the GPU and it was 2.78X slower than CPU. Our hybrid BWC pipeline performs about 2.9X better than CPU BWC and thus, about 8X faster than Patel et al. For work sharing, we use FSD as an example and split the data parallel step between CPU and GPU. The Handover and Hybrid FSD algorithms, which use work sharing to exploit computation resources on both CPU and GPU, are faster than the CPU alone and GPU alone parallel algorithms. In conclusion, we develop data parallel algorithms on the GPU for difficult problems of Floyd-Steinberg Dithering, String Sorting and Burrows Wheeler Transform. In earlier literature, simpler problems which provided some degree of data parallelism were adapted to the GPUs. The problems we solve on GPU involve challenging sequential depende

Abstract

Twitter is a widely used micro-blogging service, which in recent times, has become a reliable source of happening news around the world. Breaking news are covered in twitter; the magnitude and volumes of tweets reflecting on the nature and intensity of the news. During events, many tweets are posted either expressing sentiments about the event or just about the occurrence of the event. Events related to an entity that have attracted a huge number of tweets can be considered significant in the entity’s twitter lifetime. Entity could represent a person, movie, community, electronic gadgets, software products and like wise. In this work, we attempt to automatically detect significant events related to an entity. An episode, is an event of importance; identified by observing the volumes of tweets/posts in a short period. On the other hand, the average number of friends for a facebook user is approximately 190. Therefore, for each user there can be lot of daily feeds from their friends to keep track. Not all feeds are important, but important ones are not to be missed. We address the problem of identifying important news feeds from the clutter of un-important ones. We also detect important news feeds from the facebook page of a given entity. An important feed (i.e., a user’s status or a post) which receives high responses (likes or comments) is called an episode. With the growing use of social networking sites, there is a huge deluge of messages at macro and micro level. For a marketing team, analysing the product reception; the number of messages considered across various number users is very large. Another scenario where the number of messages overwhelming a user is the number of status updates posted by the user’s friends. For both the scenarios identifying what are important ones is a crucial problem to address. The sudden noticeable increase in number of messages relating to a particular object (like a person, place, products etc.) can indicate such important ones. This thesis attempts to address the problem of identifying important happenings at a macro (over tweets) and a micro (over friends news feeds) level. In this work, we propose SMEA (Short Message Episode Analytics) system for detecting significant episodes over the life span of an entity. We have implemented the system over two short message domains Twitter and Facebook; both tweets and facebook posts can be considered as short messages. We present two different techniques for the systems, Tweet Episode Analytics (referred to as TEA) and Facebook Episode Analytics (referred to as FEA) separately in this work. The key features implemented in Tweet Episode Analytics (TEA) system are: (i) detecting episodes related to a given entity over a period of time (from the entity’s birth i.e., mention in the tweet world till date) among the streaming tweets, (ii) providing visual analytics (like sentiment scoring and frequency of tweets over time) of each episode through graphical interpretation. As a part of Facebook Episode Analytics (FEA), we propose a ranking scheme to determine episodes (i.e., important feeds) through a number of parameters like frequency of communication between the friends and the user (or an entity), sentiment polarity of the posts and the comments and influence of the post on the user’s friends.

Abstract

The development of general purpose micro-processor based computers has been quite notable in recent times. Arithmetic and Logic Unit (ALU) is a common component in these systems to support all arithmetic operations needed. The speed of the system gets enhanced by using ALU that also supports floating point operations. Floating Point Unit (FPU) works as a co-processor when there is a need for main processor to work on intensive tasks. The main functionalities of FPUs include addition, subtraction, multiplication, division, finding square root etc. Many digital designs in history consider speed as the primary parameter and power as the secondary. The miniaturization of silicon devices is highly followed these days and the dimensions of the MOSFET are going smaller day by day. Power dissipation in CMOS circuits is caused from two different components 1. Static power 2. Dynamic power, of which, dynamic power is the major contributor. Hence, an effort to optimize power has to be aimed at dynamic power dissipation. In general, using power reduction techniques causes the speed/performance of the system to go low. As reduction in speed is not desirable, ways to optimize the speed of the devices need to be considered. In short, Speed-Power optimization is a benchmark for a good design. In this thesis, the Speed-Power optimization of floating point ALU is carried out in two steps. 1. Enhancing the speed of Normalization Unit using partition technique that is used in realizing Adders and Multipliers. 2. Decreasing the power dissipation in array multiplier using carry propagation technique. When two floating-point numbers with the same exponents are subtracted, normalization of the result is required. In this case, the result of subtraction may come nearly zero, but may not satisfy the requirement of IEEE floating-point standard. In order to bring the result in IEEE format, the normalization of result is necessary. The Normalization Unit consists of an appropriate left shift until the occurrence of first nonzero digit. The amount of shift is determined by counting the number of zeros starting from the MSB until the first nonzero digit is reached. In conventional NU for an n-bit input, checking for first ‘1’ has to be in sequential manner. There is more delay while searching for a ‘1’ from MSB towards LSB. In this thesis, a new design technique to calculate normalization with high speed and low area overhead compared to conventional normalization units is presented. In conventional technique, a large size input leads to high speed since it has more fan-in. New technique conveys that, in order to decrease the delay of the overall circuit, the input is partitioned to reduce the complexity created by high fan-in. This technique makes use of two decoder units, one simple adder and a barrel shifter. By choosing appropriate partitioning, the delay and the area results of the above technique are observed to be better than conventional approaches till now. It is also observed that this technique has better performance in case of large input size. There is a 40% improvement in speed and 14% improvement in power consumption for 24-bit input. In many digital applications, adder is the basic building block of an arithmetic unit. Multiplication is the second basic operation to be carried out next to the addition. A wide usage of these adders and multipliers can often be seen in areas such as Digital Signal Processing (DSP) and Graphics Processing. Multipliers are built based on a structured arrangement of adders. Though the adder circuit itself is small, the replication of many adders in multiplier makes the operation time consuming and quite expensive. A low power design technique called carry propagation is applied to an array multiplier, a major building block of a floating point multiplier. This architecture considerably lowers the switching activity of conventional multipliers. A single precision floating point multiplier consists of a 24 x 24 bit array multiplier resulting in a 48 bit output. The output is rounded-off by discarding the last 24 LSBs and adding either ‘1’ or ‘0’ (carry) to remaining output depending on the value of 24 LSBs. The proposed carry propagation technique reduces the hardware requirement substantially since the 24 LSBs need not be calculated, which results in lesser area and lower power dissipation. Since the 24 LSBs are not being calculated, a tolerable rounding error occurs while using this technique in floating point multiplier. To ensure that the 24 MSBs are correct, only carry bits are propagated from the LSB side of the array multiplier. Although this technique has no effect on the critical path delay, it does reduce power dissipation up to 6.7%. An FIR filter is designed based on this floating point multiplier unit and is tested with various set of inputs. After the analysis of parameters like power and power-delay product, it is observed that the FIR filter ba

Abstract

Treebanks are major resources for developing various natural language processing applications. Dependency framework has proved to be successful for handling free word ordered languages. Indian languages are mostly morphologically rich and are relatively free-word order (MoR-FWO) languages. There has been a recent surge in addressing parsing for morphologically rich languages. Most of the work in parsing Indian languages has been done at the chunk level. Full sentence dependency parsing is not explored in detail till now. In this work, we start our experiments to improve dependency parsing accuracies for Indian languages (Hindi, Telugu and Bangla) as part of ICON 2010 Tools Contest. We explored MaltParser, a data driven parser, on grounds of large feature pool consisting of morphological and syntactic features. We prepared different parser configurations by considering different parsing strategies, classifiers and feature templates. Additionally for Hindi, we utilized shallow parser output as features and tried to incorporate minimal semantics. We selected the best onfiguration for each set of data and were able to produce the best average accuracy in the ICON 2010 Tools Contest. We achieved Labeled Attachment Scores (LAS) of 88.63, 70.12, 70.55 on the fine grained data of Hindi, Telugu and Bangla respectively. Subsequent to this, we moved to developing a robust rule based intra-chunk dependency annotator which generates full sentence dependency treebank from interchunk dependency treebank by marking dependencies inside the chunk. We developed the detailed intra-chunk dependency guidelines for Hindi. The rule-based annotator uses these guidelines as the basis for framing rules. The rule based annotator was further improved by using the output from MaltParser, a statistical parser. The tool has the state of the art LAS, Unlabeled Attachment Score (UAS) and Labeled Score (LS) accuracies of 98.17, 98.81 and 98.63 respectively. As we prepare a full sentence dependency tree by marking intra-chunk relations on an inter-chunk dependency tree, we call this process as ’Expansion’ of inter-chunk dependency treebank. Dependency treebanks are capable of containing lots of information apart from the syntactic information and therefore make a rich resource for other linguistic annotations on top. These annotations happen layer wise. For example, the present Hindi dependency treebank is enriched with propbanking and minimal semantics information. These layers of annotation happen in parallel on the initial version of dependency treebank. While these layers are being annotated, the base layer (initial version) undergoes further changes in the tree structure either due to change in guidelines or due to correction of annotating errors. Hence it is essential to merge the additional layers of linguistic information onto to the latest version of dependency treebank. We concentrated on building a simple tool which extracts these additional linguistic information and maps on to the newer version of dependency treebank. We call this process ’Merging’ of different versions of same dependency treebank.

Abstract

Today, Infrastructure-as-a-service (IaaS) providers are trying to minimize the cost of data center operations, while maintaining the Service Level Agreements (SLAs). This can be achieved by one of the advanced state-of-the-art services of virtualization - the live migration capability. Live migration is defined as the process of transferring an active virtual machine (VM) from one physical machine to another without any disconnection. This is achieved by transferring all of the encapsulated states of the VM from one host to another. Thus, it has become an essential tool for efficient management of resources in a data center by enabling server consolidation and load balancing among other possible benefits with a minimal effect on client services. There are two classical migration techniques, namely - pre-copy and post-copy, which employ different memory transfer mechanism during the offloading of a VM. In the case of pre-copy, the memory is iteratively transferred from the source to destination until the remaining dirty memory along with the other device states is left to be transferred in a shorter last iteration. While in the case of post-copy, all the device states except memory is immediately transferred to the destination. Source VM’s memory is only transferred if needed by the running VM. However, these existing techniques suffer from high network bandwidth utilization, large network data transfer, large migration time as well as destination’s VM failure during migration. In this thesis, we propose a novel hybrid live migration technique by combining the existing pre-copy and post-copy approaches. Our hybrid technique is a fast, efficient and a reliable migration technique compared to its counterparts. This technique provides a reasonable solution to high efficiency and less disruptive migration scheme by utilizing all the three phase of the process migration. For effective network bandwidth utilization and reducing the total migration time, we introduced a learning phase to estimate the writable working set (WWS) prior to the migration process. Only those pages which are not present in the estimated WWSare transferred to the destination initially. Pages from the estimated WWS are retrieved from the source machine through page faults as the virtual machine resumes execution on the destination. Our learning technique helps us in achieving almost a single time transfer of the pages when compared against the naive hybrid technique. Several other optimizations like compression, block based paging, page pre-fetching and push phase parallel transfer are incorporated in the migration scheme. Similar to the post-copy technique, hybrid live migration results in virtual machine failure if the destination machine fails during the pull phase of migration. We introduced reliability into the pull phase by using a fail-stop model which periodically checkpoints the virtual machine state during the pull phase. If the destination machine fails during the pull phase, the virtual machine can be recovered on the source host from the latest check pointed state on the disk. We implemented the proposed hybrid approach on the top of a KVM hypervisor and conducted experiments on diverse workloads. Our compression based hybrid learning approach decreases the total data transfer by 1:83 - 7:47 times for pre-copy, and 1:16 - 12:21 times for post-copy. And it decreases the total migration time by 1:42 - 9:84 times for pre-copy, and 2:43 - 8:57 times for post-copy.

Abstract

All visible objects have shape and texture. The main aim of computer graphics is to represent and render real world objects efficiently and realistically. To make the objects look realistic from a geometric point of view, we have to make sure that the shape and texture of the object are accurate. In practice, shape is either hand crafted using 3D modeling tools such as Blender, or is acquired from real world objects using 3D reconstruction techniques. Texture is the second aspect of appearance that must be ensured to make the rendered objects look real. The texture has to be pasted on the surface in such a manner that it perceptual corresponds to the correct part of the mesh. This process of pasting the texture on the surface of a mesh model is called Texture mapping. Texture mapping can be done in two ways. First way is to texture a surface by synthesizing the texture directly on the surface. The second method is to wrap a synthesized texture around the surface and cut and merge the seams so that it fits correctly on the surface. To visualize this problem we can think of texture as a cloth. The first method can be thought of weaving around the body to fit it exactly like a sweater, while the second method is like cutting and stitching an already woven cloth according to the shape of the mesh model. In this thesis we propose a new method that follows the second approach. The primary goal of our method is to map a texture on to large mesh model at interactive rates, while maintaining the perceived quality. The primary technique for mapping a flat texture (image) onto an arbitrary shaped mesh model is to parameterize the shape, which defines a mapping from points on the mesh surface onto a 2D plane. When parameterizing these mesh models, we try to maintain the geometric correspondence between the mesh vertices intact to reduce the distortion of the texture. Typically, parameterizing a mesh model involves solving a set of linear equations representing the geometric correspondence of the triangles. The approach involves defining an energy function for the mapping and searching for a global optimum which minimizes the distortions during the mapping. Such methods are capable to achieving texture mappings that has high perceptual quality. However, typical energy minimization procedures are computationally expensive and cannot be applied for real time applications or with large mesh models. As the size of mesh models increase, global optimization techniques employed by the parameterization methods tend to become computational bottlenecks. To make parameterization a real time procedure for large meshes, we propose a greedy approach that operates on local optimization function rather than the traditional global optimization function. We express the surface in terms of local curvature and store these values in a priority queue, which is used to determine the portion of the mesh that is to be textured next. Our algorithm is simple to implement and can texture at approximately one million polygons per second on current day desktops. We show that our algorithm is robust to dynamically changing meshes and produces the same texture even when a part of the mesh is removed and brought back. This is an important feature because in case of optimized rendering of large objects, we cull out large parts of the model from rendering based on visibility, and render them again when these objects fall back into the view frustum. In such situations, re-texturing of previously seen parts should not change its appearance. The proposed algorithm is also not affected by a sudden change in the density of points on a noisy mesh surfaces. That is, the algorithm’s runtime complexity does not depend upon the complexity of the surface unlike most traditional parameterization algorithms. The time complexity is linearly related to the model size and it is not affected by the size of the texture. To complement the proposed texture mapping algorithm, we introduce a method to make a texture self tileable. This allows us to store only the texel structure, if the required texture is repetitive. We present qualitative and quantitative results in comparison with several other texture mapping algorithms. The proposed algorithm is robust in terms of the output quality and can find applications in different scenarios such as rapid prototyping, where you require interactive texture mapping rates and the ability to deal with dynamic mesh topology. It can also be used for applications such as large monument visualizations, where we need to deal with large and noisy mesh models that are generated using techniques such as multi-view stereo.

Abstract

The current state-of-the-art text-to-speech systems use either statistical parametric synthesis or hybrid systems (a combination of statistical parametric synthesis and unit selection synthesis). In statistical based techniques, phones (along with their context) are used as basic units. A major issue is to model the trajectories and reduce the over smoothing effect. Longer units such as syllables are not straight-forward to model when compared to phones. In this thesis, we show how syllable HMMs are effective in generating a HMM based TTS system HTS). We will explore the issues in modeling these sub-word units, clustering them with different categories of features including contextual information of the phone, position and manner of articulation, linguistic and syntactic features. We will also present the advantage of using syllable based models in explicitly capturing the prosodic based characteristics. Later, we will propose an approach using longer size units such as syllable, and build a statistical template for each syllable using dynamic programming to inherently capture the trajectories. Two types of statistical templates are being used for synthesis: average and median. The technique can also avoid source modeling, as one could use median templates as exemplars to build concatenative speech synthesis system. Also, the effects of using local constraints in DTW has been explained with respect to average template based speech synthesis system. Experiments are conducted on Telugu, Kannada, Hindi and English speech databases. The subjective evaluations show that the statistical template based approach performs reasonably good. Finally, different prosody modification approaches such as time-domain and frequency-domain with their limitations are described. Mainly, prosody modification using instants of significant excitation and Mel-cepstral vocoder are explained in detail and a comparison of both the techniques over non-linear modification is discussed for integrating into TTS systems.

Abstract

In this thesis we present a mathematical model for applications in the area of energy. The mathematical model is based on Kalman Filter prediction and correction technique. Kalman Filter has been applied to predict the maximum power point of a solar photovoltaic array and also to forecast the load and schedule the load for smart grid. Maximum Power Point Tracking has been the key area for solar photovoltaic array. A lot of research has been going on in this area so that efficient solar inverters can be built for power transmission with minimum loss. MPP tracking requires a prediction and correction model when done in real time; hence we opted for Kalman Filter algorithm. Two types of Kalman Filter algorithms have been used for MPPT. The one is considering the whole system to be linearly varying i.e. considering somewhat ideal behavior of the panels hence we have used Discrete Kalman Filter approach for this purpose. However, in the real situation the behavior varies with irradiance and temperature hence ideally the system shows a non linear behavior. Hence, for that purpose we have used Unscented Kalman Filter approach. Using either of these approach the maximum power point tracking (MPPT) becomes much faster than using the conventional Perturb &Observe approach specifically in case of sudden weather changes. In this thesis comparative analysis of both the algorithms being implemented on FPGA is presented. Simulations have been performed under optimal conditions as well as under cloudy conditions i.e. falling irradiance levels. Using the linear Kalman filter the maximum power point of a solar PV array has been tracked with an efficiency of 97.11% while using the Unscented Kalman filter technique the maximum power point of the same solar PV array is tracked with higher efficiency of 98.3%. However, the maximum power point has been tracked at a much faster rate i.e. 4.5 ms using the linear Kalman filter approach as compared to the unscented Kalman filter approach which tracks maximum power point at 11 ms which is in turn faster than existing generic Perturb and Observe approach which takes 15ms to track the maximum power point . The system has been implemented on Altera EP2C20F484C7 FPGA board to check the number of resources being used. The FPGA based Kalman Filter has been used for load forecasting and that to focusing on short term load forecasting which leads to load scheduling for smart grid. With smart grids the forecasting becomes much easier as we would be receiving load consumption data at the household level. The information of load consumption can be obtained from smart meters already installed in smart grid. This problem also requires a good prediction and correction model so we again took Kalman Filter algorithm in consideration. For this case we have used only Discrete Kalman Filter algorithm based upon the parameters we have considered for load forecasting approach. The algorithm proposed in this paper uses load consumption and temperature of previous few days as parameters for estimation and this forecasted data is used for scheduling purpose. Estimation is done separately for Weekdays & Weekends/Public Holidays. Using the proposed algorithm the load has been estimated with absolute mean percentage error around 1.5% and the algorithm for load scheduling has been successfully implemented on the logic of FPGA.

Abstract

Processing a sentence for any practical application requires complete understanding of the syntactic and semantic structure of the sentence. Natural language parsers, are used to perform formal analysis of a sentence into its constituents(words or phrases), resulting in a parse tree showing their syntactic relation to each other. For example, which groups of words in a sentence go together as phrases and which words are the subject or object of a verb. Natural language parsers are generally two types, Rule based parsers- often constructs a parser given a grammar and data-driven parsers - construct a parser given a treebank (sentences with the whole syntactic information annotated in them in the form of tags and dependent relations). The accuracy of these parsers, both rule based and data driven often depends on the complexity of the sentence they are parsing. The complexity varies from the ambiguous structures/words, out of vocabulary words, loosely annotated syntactic information of a sentence like Parts-of-speech tags, syntactic relation between phrases or words etc. In case of data-driven parsers, they use knowledge of language processes from the sentences they learn on to produce the most likely analysis of new sentences, hence it is very important for the parsers to extract enough and proper information from the sentence before it parse. Consider an example like below where all the syntactic information like subject, object, verb etc is present in the sentence and it is easy for any application to extract complete information. Jon and Mary went to hospital Now, consider the following example ‘John can sing a song, and Mary can too’ Sentences like these are very common to appear in the treebanks, as the treebanks are created from a wide range of sources like articles, books, discourses. As mentioned earlier, to accurately predict the syntactic structure of these sentences, it needs the syntactic information annotated in them. Now, if we look at the example above, the complete syntactic information expected from the parsers are ‘John can sing a song, and Mary can (sing) too’ In the first example, ‘John can sing a song, and Mary can too’ Whether or not the verb ‘sing’ is included in this sentence is up to the speaker and to communicative aspects of the situational context in which the sentence is uttered. But, for the parser, the verb ‘sing’ along with its information like POS tag and its relation with other elements in the sentence, very important to be part of the sentence to parse it properly. The missing elements not only create a problem for parsing the sentence, but for any application that requires sentence syntactic understanding, for instance, information extraction, question-answering, and related semantic tasks, machine translation, parts-of-speech tagging, morphology etc. The more precise and detailed our predicate argument structures are (including empty categories), the more complete our event descriptions will be, and therefore the more effective our semantic processing techniques will be. We call these missing words/phrases as ‘Empty Categories’ or ‘Null Elements’. In this work, empty categories are retrieved in two ways: 1. Retrieve empty categories in sentence itself 2. Retrieve empty categories in parse trees while parsing Inserting in the sentence is handled statistically with the help of machine learning algorithms and by leveraging this method as a postprocessing step, i.e empty categories are inserted on the parser output. Then we will see how to detect and retrieve empty categories in a data-driven parser itself. We will then move to handle empty categories in Hindi dependency treebank by analysing and classifying the empty categories and then identify various discovery procedures to automatically detect the existence of these categories in a sentence. For this we make use of lexical knowledge along with the parsed output from a constraint based parser. Through this work we show that it is possible to successfully discover certain types of empty categories while some other types are more difficult to identify. This work leads to the state-of-the-art system for automatic insertion of empty categories in the Hindi input sentence and a generic approach to handle empty categories in any language dependency treebanks.

Abstract

The past decade has witnessed the emergence of participatory Web and social media, bringing together people in many creative ways. Millions of users are playing, tagging, working, and socializing online, demonstrating new forms of collaboration, communication, and intelligence that were hardly imaginable just a short time ago. Social Media refers to interaction among people in which they create, share and exchange information and ideas in virtual communities and networks. Social Media also helps reshape business models, sway opinions and emotions, and opens up numerous possibilities to study human interaction and collective behavior in an unparalled scale. In the study of complex networks, a network is said to have community structure if the nodes can be easily grouped into sets of nodes (even overlapping) such that each set of nodes is densely connected internally. Community structure are quite common in real networks. Social Networks often include community groups based on common location, interests, occupation etc. Metabolic Networks have communities based on functional groupings. Citation Networks form communities by research topic. Being able to identify these sub-structures within a network can provide insight into how network function and topology affect each other. In this thesis, we design an end-to-end framework for identifying communities from raw, noisy social media data. The framework is composed of two important phases. First, we introduce a new method of converting the raw, noisy social media data into a weighted entity-entity co-occurrence based consistency network. This includes a simple iterative noise removal procedure for cleaning the entity consistency network by removing noisy entity pairs. Secondly, we propose an approach for identifying coherent communities from the weighted entity network, by introducing novel notions of community-ness and community, based on eigenvector centrality. We use this framework to solve three different problems from two distinct domains. The first problem involves detecting communities from raw social media data and showing the application of the communities discovered in a recommendation engine setting. We use the framework for converting the raw data into a clean network and propose a highly parallelizable seed based greedy algorithm to detect as many communities as possible from the weighted entity consistency network. Our framework for community detection is unsupervised, domain agnostic, noise robust, computationally efficient and can be used in different Web Mining applications like Recommendation Systems, Topic Detection, User Profiling etc. We also design an recommendation system to evaluate our framework with existing state-of-art frameworks~cite{LDA,Farkas,bigclam} on a variety of large real-world social media data - Flickr, IMDB, Wikipedia, Bibsonomy, Medline. Our results outperform other frameworks by a huge margin. The second problem is, given a set of communities of discovered by traditional community detection methods~cite{Palla,Lancichinetti09}, we need to identify loose communities among them and partition them into compact ones. Here, we use the second phase of our framework to identify such loose communities using our notion of community-ness and propose an algorithm for partitioning such loose communities into compact ones. We illustrate the results of our algorithm over Amazon Product and Flickr Tag data and compare its superiority over the traditional community detection methods in a recommendation engine setting. The third problem is about showing the application of such framework in an Image Annotation scenario in presence of noisy labels. The problem of image annotation is defined to be, given an unknown image, we need to predict labels which best describes the semantics of the image. This problem is best solved in a supervised nearest neighbor setting, and we show how our framework can be used to address this problem, when the labels associated with training images can be noisy and redundant.