Abstract

Forest fire is a major ecological disaster, which has economic, social and environmental impacts on humans and also causes the loss of biodiversity. Forest officials issue warnings to the public on the basis of fire danger index classes. Generally, fire danger indices are developed based on the meteorological stations in countries like Canada, United States of America, Australia, etc. Geospatial techniques such as satellite remote sensing based approaches can be useful to develop the fire danger indices in those countries that lack sufficient meteorological stations. In general, fire danger indices have been developed based on the parameters which are associated for the cause of ignition and spreading of forest fires. These properties include forest fuel type, topographic conditions and moisture conditions. Vegetation and topographic conditions are static, i.e. they do not change frequently, whereas moisture conditions are dynamic. Dynamic properties such as air temperature, relative humidity, moisture conditions changes regularly in a day. In this study, Static Fire danger Index has been developed using MODIS (Moderate Resolution Imaging Spectro Radiometer) Land cover type yearly L3 global 500 m SIN grid (MCD12Q1) and ASTER Global Digital Elevation Model datasets. International Geosphere-Biosphere Programme (IGBP) land cover type has been generated from MCD12Q1, which has been used to compute the forest fuel type index based on historical fire data. Fuel type danger index, Terrain ruggedness danger index, Slope danger index, Aspect danger index and Elevation danger index were computed from the ASTER GDEM datasets. Uttarakhand state has very few meteorological stations so geospatial techniques can be useful to derive the fire danger indices. Several authors developed the fire danger indices based on satellite derived parameters such as land surface temperature, vegetation and moisture indices such as “Normalized Difference Vegetation Index, Normalized Difference Water Index, Normalized Multiband Drought Index, Visible Atmospheric Resistant Index” etc. In this study, Dynamic Fire Danger Index (DFDI) has been developed from three parameters i.e. potential surface temperature, Perpendicular Moisture Index (PMI) and Modified Normalized Multiband Fire Index (MNDFI) using the MODIS Terra satellite datasets. DFDI has been calculated from the Near Real Time (NRT) Level 2 MODIS Terra Land Surface Temperature datasets (MOD11_L2) and MODIS Terra NRT surface reflectance dataset (MOD09). Finally, Forest Fire Danger Index (FFDI) has been developed by integrating both the Static and Dynamic fire danger indices and also used the near real time data sets that can be available for download through NASA FTP server Developing Forest Fire Danger index using geo-spatial techniques after one hour of the satellite overpass. The overall fire danger prediction accuracy was around 81.27% for the year 2016. Thus, the FFDI has been useful to assess the fire danger accurately over the study area and can be useful anywhere, where the meteorological stations are un-available. The entire procedure of calculating FFDI from NRT datasets was semi-automated so that the fire danger maps will be disseminated to the fire officials for taking timely action in controlling the forest fires.

Abstract

Sentiment analysis is a discipline of Natural Language Processing which deals with identifying and analyzing the subjectivity of data. It is an important task with both commercial and academic function- ality. It has acquired wide commercial uses including social media monitoring tasks, survey responses, review systems, etc. In review systems and surveys, sentiment analysis allows us to understand the opinions of multiple recipients. It expresses opinions such as like/dislike, for/against of general population. The merits of sentiment analysis do not stop there. The applications of sentiment analysis are broad and powerful. The ability to extract meaningful insights from social data is being widely adopted by organizations across the world.The human language is complex, teaching a machine to analyze the various grammatical nuances, cultural variations, slang and misspellings that occur in online mentions is a difficult process. To perform various sentiment analysis tasks we created a platform to employ different techniques and statistical methods to evaluate the data. By doing text analysis using computational linguistic techniques, we are able to capture and quantify affective states and subjective information. Sentiment analysis/opinion mining is done on human generated data. Since sentiment knowledge in humans grow with age and daily interactions, cognitive knowledge is required to understand emotion. In order for machines to understand underlying emotion, we need to transfer this cognitive knowledge in some form. Majority of the computational approaches to opinion mining comes using pre-existing lexicons. It has been understood that such lexicons are vital for any sentiment analysis system. These lexicons are the closest representation of our cognitive knowledge. These computational lexicon wrap sentiment information to assist in the task of opinion mining. Most research efforts in sentiment lexicon creation are bound to the English language. SentiWordNet for English is one such important lexical resource that contains subjective polarity for each lexical item. It was devised to aid in the task of opinion mining and sentiment classification. With growing data in native vernacular, there is a need for language-specific sentiment lexicon. For resource poor languages, creating such a sentiment lexicon is a difficult task to achieve. Described in this thesis are two different methods on how to build such a resource for an Indian language Tamil, using existing resources in other languages. Such a resource would serve as a baseline for further improvements in the task of sentiment analysis specific to Tamil data. Furthermore, the architecture followed in the two methods can be easily adapted to other languages.

Abstract

Forests play a key role in carbon cycle by sequestering the atmospheric carbon dioxide from various sources. Approximately 33% of the world’s land area is covered by forest ecosystems. It is thus essential to monitor forests at a regular interval for better management. Remote sensing datasets (both satellite and aerial) forms an key sources for providing a synoptic view of forest cover at landscape level to describe land use changes for monitoring purposes. However, the complexities of the forest ecosytems are not well understood with the traditional 2D remote sensing datasets (optical and radar remote sensing images) and need for the 3D structural assessment of forest ecosystems are essential. Terrestrial Laser Scanning (TLS) or Terrestrial LiDAR (Light Detection And Ranging), is an active remote sensing based ground measurement technique capable of capturing 3D information of the scene of interest with milli-meter accuracy. It transmits the laser pulse and analyses the return pulse to position the reflected object in 3D space. The main goal of this thesis is to evaluate the potential of TLS for forest biomass estimation and to develop the relevant methods to extract relevant information from TLS data. Accurate estimations of forest aboveground biomass at regional and national scales heavily depend on the field data and are upscaled using remote sensing datasets (both optical and radar). However,Field data collection of forest inventory parameters (mainly species name, tree count, tree diameter, height etc.,) using conventional methods are both labour-intensive and time consuming. So, firstly, we target the feasibility of TLS to extract forest inventory parameters accurately using the automated algorithm. We provide an automated solution to extract forest inventory parameters at individual tree level from 3D TLS data. The algorithm is tested over deciduous forests of Betul, Madhya Pradesh. Data filtering followed by a RANSAC based circle fitting algorithm was used to extract tree diameter and tree heights. An overall detection rate of 97% along with high correlation of field based easurements and TLS based measurements (Diameter R2 = 0.99 & Height R2 = 0.98) was obtained. The estimated RMSE was found to be 2.2 cm in diameter and 1.65 m in height. Further, to envisage the potential of TLS in diverse forestry applications, it was desirable to identify individual trees in the 3D TLS data to better describe tree architecture. So the focus was made to segment individual trees from the 3D point cloud by employing supervoxels and graph-cut based segmentation methods. High dense point cloud was first converted into supervoxels to reduce the data complexity and a graph-cut was performed to extract individual tree objects. The individual trees paved way for the advanced inventory parameter extraction such as crown dimensions (diameter and height) and branching patterns which would have been near impossible using conventional field measurements. Also, they form as the basic ground information for high resolution image based studies focusing on crown detection and delineations. Next, trees with relatively high completeness are selected and are described by highly accurate piecewise cylinders based on branching structure. This method helped to estimate the tree volume as the sum of the volumes of individual cylinders. Thus, an attempt has been made to accurately describe the actual tree volume in a non-destructive way. The volumes derived for selected trees were used to construct local volume equations of the study site along with the uncertainty in the total volume estimate. Tree volumes are a direct proxy of tree biomass (biomass is generally calculated by multiplying tree volumes with wood density), which help in carbon stock assessment of the forest area. Based on our estimates, tree volumes derived from conventional volume equations have underestimated the actual TLS volume by 28%. However, this estimate needs to be substantiated with destructive sampling. Also, the volume equations constructed using TLS along with uncertainty estimates are used in upscaling the field measurements to the regional biomass estimates using satellite remote sensing datasets. The standard way of producing a regional biomass map is by using a regression model using the field biomass estimates with the remote sensing variable (optical or radar). However, the uncertainty of this measurement at the spatial scale is often not calculated accurately. Both field level and the remote sensing model level errors attribute to the uncertainty of the spatial biomass estimate. Accurate assessment of biomass is essential to several social and economic incentive schemes of United Nations Framework Convention on Climate Change (UNFCCC). In this context, a possible framework to integrate uncertainties from field level measurements to regional-level estimates was established and spatial biomass maps along with uncertainty maps are gene

Abstract

Sentiment analysis is a discipline of Natural Language Processing which deals with identifying and analyzing the subjectivity of data. It is an important task with both commercial and academic function- ality. It has acquired wide commercial uses including social media monitoring tasks, survey responses, review systems, etc. In review systems and surveys, sentiment analysis allows us to understand the opinions of multiple recipients. It expresses opinions such as like/dislike, for/against of general population.The merits of sentiment analysis do not stop there. The applications of sentiment analysis are broad and powerful. The ability to extract meaningful insights from social data is being widely adopted by organizations across the world. The human language is complex, teaching a machine to analyze the various grammatical nuances,cultural variations, slang and misspellings that occur in online mentions is a difficult process. To perform various sentiment analysis tasks we created a platform to employ different techniques and statistical methods to evaluate the data. By doing text analysis using computational linguistic techniques, we are able to capture and quantify affective states and subjective information. Sentiment analysis/opinion mining is done on human generated data. Since sentiment knowledge in humans grow with age and daily interactions, cognitive knowledge is required to understand emotion. In order for machines to understand underlying emotion, we need to transfer this cognitive knowledge in some form. Majority of the computational approaches to opinion mining comes using pre-existing lexicons. It has been understood that such lexicons are vital for any sentiment analysis system. These lexicons are the closest representation of our cognitive knowledge. These computational lexicon wrap sentiment information to assist in the task of opinion mining. Most research efforts in sentiment lexicon creation are bound to the English language. SentiWordNet for English is one such important lexical resource that contains subjective polarity for each lexical item. It was devised to aid in the task of opinion mining and sentiment classification. With growing data in native vernacular, there is a need for language-specific sentiment lexicon. For resource poor languages, creating such a sentiment lexicon is a difficult task to achieve. Described in this thesis are two different methods on how to build such a resource for an Indian language - Tamil, using existing resources in other languages. Such a resource would serve as a baseline for further improvements in the task of sentiment analysis specific to Tamil data. Furthermore, the architecture followed in the two methods can be easily adapted to other languages.

Abstract

Gone are the days when individuals aimlessly pursued news from one source. Presently, they need to peruse articles and stories from an assortment of sources to see every one of its subtleties. News aggregators become an integral factor here. They gather news articles from an assortment of sources and present it to the client in one single area. With news originating from different streams, it turns out to be exceptionally cumbersome for a client to choose articles of her decision from a rundown of exhibited articles which relates to an assortment of subjects. In this thesis, we mainly focus on three major aspects of Computational Journalism which could help news aggregators to increase viewership as well as their credibility. We start with news recommendation, which is also one of the most crucial things for a news aggregator. Users, these days don’t have time to browse through hundreds of news articles and find the relevant ones. They want a recommendation system which could take into account their reading history and recommend relevant articles. We then look at a new problem which is used by news agencies to lure users into clicking at headlines and subsequently increase their viewership, which is formally known as Clickbait. Finally, we try to detect Fake News which could help news agencies in building trust and increase their credibility. We commence our research work with the problem of News Recommendation. Popular methods like collaborative filtering and content-based filtering have their own disadvantages. The former method requires a considerable amount of user data before making predictions, while the latter, suffers from over-specialization. In this work, we address both of these issues by coming up with a hybrid approach based on neural networks for news recommendation. The hybrid approach incorporates for both (1) user-item interaction and (2) content-information of the articles read by the user in the past. We first come up with an article-embedding based profile for the user. We then use this user profile with adequate positive and negative samples in order to train the neural network-based model. We then move on to various deep learning methods to tackle the same problem. We propose a Re-current Attention Recommendation Engine (RARE) which consists of two components and utilizes the distributed representations of news articles. The first component is used to model the user’s sequential behaviour of news reading in order to understand her general interests, i.e., to get a summary of her interests. The second component utilizes an article level attention mechanism to understand her specific interests. We feed the information obtained from both the components to a Siamese Network in order to make predictions which pertain to the user’s generic as well as specific interests. Building upon our previous model, we propose a Hybrid Recurrent Attention Machine (HRAM).HRAM consists of two components. The first component utilizes a neural network for matrix factoriza-tion. While in the second component, we first learn the distributed representation of each news article.We then use the historical data of the user in a sequential manner and feed it to an attention-based recurrent layer. Finally, we concatenate the outputs from both these components and use it to make predictions. In this way, we harness the information present in the user reading history and boost it with the information available through collaborative filtering for providing better news recommendations. We then experiment with non-recurrent neural networks for the same problem. We propose a simple yet effective architecture which utilizes a 3D Convolutional Neural Network which takes the word em-beddings of the articles present in the user history as its input. Using such a method endows the model with the capability to automatically learn spatial (features of a particular article) as well as temporal features (features across articles read by a user) which signify the interest of the user. At test time, we use this in combination with a 2D Convolutional Neural Network for recommending articles to users. We carry out extensive experiments to establish the effectiveness of our methods. We also perform experiments to prove the efficacy of our model on solving the item cold-start cases as well as making effective recommendations for users who have had very little interaction with articles. We then look at another aspect of Computational Journalism, which is Clickbait Detection. Online media outlets, in a bid to expand their reach and subsequently increase revenue, have begun adopting clickbait techniques to lure readers to click on articles. We propose a novel approach considering all information found in a social media post. We train a bidirectional LSTM with an attention mechanism to learn the extent to which a word contributes to the post’s clickbait score in a differential manner. We also employ a Siamese net

Abstract

The problem of developing a good humanoid platform that can operate in diverse environments is very demanding as it not only requires a considerable amount of time in hardware development but also takes into account significant effort in software development. It requires to go through various iterations to zero down on the design and remove any other potential issues associated with the hardware. In this thesis, we focus on design and development of one such humanoid platform which is modular, open source, stable, cost-effective and easy to build using modern techniques like rapid prototyping. The first and foremost reason for the development of such a platform is that it can be very useful in verification of the various algorithms, which are critical for the operation of humanoid. Secondly, in a long run, it may help in understanding the complexities of human motion in various environments and then replicate it efficiently on the robot. Such an evolution may help us to revolutionize Human-Robot Interaction (HRI). Such a humanoid robot can evolve and learn, allowing for safer interaction without any harm to either robot or the user. But there are inherent problems associated with this notion of development of software and hardware for humanoids. For humans, walking and balancing seem like a trivial task which comes naturally to us, but such is not the case for the robots. They have to be programmed and equipped with sufficient feedback to leverage their body structure and then stand in a stable posture accordingly with continuous control and feedback. A very prominent factor in achieving this stability is that humanoids have to be morphologically designed which assist in the manipulation tasks or gait to be performed by the robot. The robot should have sufficient motor torque and longevity to stand and should be able to take into account the dynamic forces acting on the body. Motors should be able to execute the given motion profiles concurrently so that the robot doesn’t fall due to conflict of joint motion. The electrical hardware has to be powerful enough to have good response time and reliability. Since there are a lot of variations in sizes of humanoids and difficulties associated with each type and sizes, It was decided to go for a miniature humanoid as it is relatively easier and cheaper to build and it still allows exploration of most important research problems. Building on Poppy project, INRIA,France, we develop a humanoid with a 5-Degree-of-Freedom (5-DoF) torso with some key changes. The benefit of such a torso is enormous as it allows for distribution of impact forces evenly on the body without destabilizing it. In contrast to Poppy robot, the ankle joint of the leg has 2-DoF joint in place of the 1-DoF joint. This enables the robot to adapt to different terrains more effectively. Humanoid was made using the rapid prototyping techniques, which reduces the hardware construction time and any reiteration occurring due to flaws. The major efforts have been made in building a humanoid platform with robust hardware and feedback modules. This is achieved by designing the structure of the robot, ensuring proper joint motion feedback, and enabling feedback from the environment through sensors in a reliable and robust manner. All these problems require painstaking effort to build and test for the whole system to work in a holistic manner. We have tried to keep the structure of the robot as close to a human morphology as possible and showed that it is stable when it stands and can perform necessary motor manipulations with large enough support polygon formed by the extremities of the foot. Incorporation of sensors like force sensing resistors, position sensors, IMU, etc. with an embedded hardware helped in coming up with a reliable platform. This was followed by the development of the algorithm for joint control by commanding the individual motors of the humanoid concurrently. The stability of humanoid is monitored by experimental calculation of Zero Moment Point (ZMP) which enables future usage of the hardware to test complicated motion planning algorithms. In order to work safely with the hardware, a MATLAB/Simulink based simulator is also developed which allows the first level of testing through simulations. This helps in understanding the implications of the developed algorithms before implementing on the real robot. With the simulation environment in place, It is easy to directly connect such an environment and the robot using a middle-ware like ROS to perform experimental validation. The platform is intended to be used for testing of various algorithms of humanoid motion in various

Abstract

Landslides are the most common and devastating natural disaster in the Indian Himalayan region other than earthquakes. Landslides affect 15% of Indias land area which is around 0.49 million km2. It is estimated that 42% of all the landslide prone areas in the country fall in North East Himalayas, especially Darjeeling and Sikkim part of the Himalayas. The damage caused due to landslides is massive leading to loss of life, property including agricultural land. The studies on landslides have drawn worldwide attention due to the rapid increase in urbanization in many of these hilly regions and thus its increasing impact on socio-economic aspects. Thus there is a dire need for understanding landslides, estimating its occurrence potential (or modeling), and formulating strategies to minimize its impact. Some of the recent studies on Darjeeling-Sikkim Himalayas have largely looked at severity zonation, identifying rainfall thresholds and other related aspects. However, a comprehensive study of the entire region of Kalimpong has been largely left unattended. While, landslides can be considered to be either shallow or deep-seated failure of the soil mass, majority of the landslides in Kalimpong are categorized as shallow landslides. Such type of landslides are caused or reactivated or induced primarily by rainfall. In a recent report by Geological Survey of India (GSI, 2016) it identified that 75% of the landslide occurrences in this region during 2006-2013 was triggered by rainfall. Therefore, it is imperative to understand the relationship between landslide incidences and rainfall conditions during and before, primarily in the context of the Himalayan region in Kalimpong. There are mainly two types of methods to understand this relationship: physical and empirical. Phys-ical process models are based on numerical models which study the relationship between rainfall, pore water pressure, soil type, and volumetric water content that can lead to slope instability. Such study is usually site specific due to variation in soil properties. It is a challenge to extend this approach to large areas, as the extensive data that is required are usually not available. On the other hand, Empirical methods study the landslides that are caused by rainfall events both the heavy downpour that triggers instantaneous landslides and the low but continuous antecedent rain that destabilizes the slope and triggers landslide. In this present work, an empirical approach is taken for assessing the landslides in the Kalimpong region by considering the daily rainfall intensities. As such methods produce only binary results i.e, either landslides occur or do not occur, we have also adopted and evaluated probabilistic methods for this region. In addition, the study further explores the relationship between rainfall and landslide occurrences, by using a mathematical model to simulate the potential triggering conditions in Chibo, one of the most active landslide regions in Kalimpong. To validate and assess the empirical model, an IoT sensor based field observations were carried out. The installed sensors are Microelectromechanical Systems (MEMS) tilt sensor and volumetric water content sensors in the Chibo area. While the former measures the tilting angle of the instrument at shallow depths and hence the lateral displacement at the slope surface; the later measures the soil moisture levels. These were used to assess the model performance. Also, it was found that antecedent rainfall of 20 days or more is one of the major causes for rainfall induced landslides in this region. The results also signify that a rainfall intensity of 60-70 mm/day has the highest probability of landslide occurrence for the Kalimpong region. The results signify that to develop an operational early warning system without the need of a monitoring system threshold values would be equal to higher than empirical derived thresholds but not higher than hydrological thresholds. The work shows that Early warning systems can hence be designed based on these rainfall thresholds as the first line of action.

Abstract

An academic citation network can be viewed as an information graph where individual nodes contain rich textual information. With the current trend of open-access to most scientific literature, we presume that the full text of a scientific article (or paper) is a vital source of information which aids in various recommendation and prediction tasks concerning this domain. The textual content of a paper serves as a rich source of information about a node in the citation network graph. The first task we focus on is competing algorithm mining from research papers. As an example, consider the association rule mining problem in data mining or the object recognition problem in computer vision. There has been a lot of research on these particular ideas and several authors and research groups have come up with their novel solutions to tackle these problems. The authors would measure their proposed algorithms against current state-of-the-art. Given the textual content of a paper we propose to mine all the algorithms which are being compared against inside the paper of interest. As our first contribution, we develop an unsupervised mechanism leveraging natural language processing techniques to solve this problem. Recently representation learning using neural networks has been receiving much attention from both industrial and academic communities. Thanks to the advent of powerful GPUs and advanced techniques like dropout and rectified linear units, the interest in neural networks has been revived. The current state-of-the-art solution for the applications in the field of Natural Language Processing (NLP) and Information Retrieval (IR) is powered by neural network based representation learning models. We explore the similar theme of using text content from research papers and propose ways of improving search, retrieval and recommendation in academic citation networks. For example, two papers published between a short timespan would not neccessarily cite each other even if they cater to very similar ideas. As our second contribution we introduce Paper2vec: a novel two step neural network based approach to obtain vector representaions of scientific papers from an academic citation network by exploiting both its textual content and network (graph) properties. Our third contribution is on similar lines, where instead of papers we focus on authors inside the whole network. We specifically explore how we can exploit the content of papers written by an author to aid in possible collaboration prediction and propose Author2vec: a novel joint training approach using neural networks for the same. In the growing body of open access to research papers and journals, the set of algorithms and frame- works proposed in this thesis could act as a first step towards the use of full textual content for the aid of various prediction and recommendation tasks in academic citation networks.

Abstract

Apple Inc. unveiled the first iPhone in 2007. Cutting edge technology was introduced in the smartphone with an interface that allowed users to interact with the device through various modes. Also,the ecosystem facilitated developers to create applications on mobile platforms, popularly referred to as “Mobile Apps”. Mobile apps are software applications designed to run on smart-phones, tablets, and other mobile devices. They are typically available through app stores operated by entities that own the corresponding mobile operating system. By 2020, its been forecasted that mobile apps shall generate around 189 billion USD [49] in revenues via app stores and in-app advertising. The increasing use of smart-phones has led to mobile applications replacing or supplementing traditional web-based applications. Given the limitations of the form factor in smart-phones, Usability is one of the essential attributes that determine the success of a mobile apps. The measures available for assessing the usability of mobile apps tend to focus more on the human aspects and less on the functional aspects of Usability. Also, quantitative metrics that measure usability of mobile apps are very limited. As part of our initial research, we studied mobile apps in banking and finance domain. An analysis of the usability issues reported by the mobile users helped capture the challenges faced by these users as part of their day-to-day transactions. Various market giants have proposed varied usability guidelines to enrich user experience (like ISO, Android, Neilson Norman group etc). These guidelines are the repository for software practitioners to build usable mobile apps. However, there are no definitive standards or effective tools to detect and address usability issues. This made us propose a few banking specific usability guidelines based on a usability index called Mobile App Usability Index (MAUI).This study helped us establish an understanding of the functional and non-functional aspects of usability features while building a mobile app. Traditionally, usability evaluation is considered as a post-development activity which is usually taken care of by UX/UI Experts. Usability evaluation was done manually using various methods like cognitive walk-through, field studies, group studies etc, which delays detection of usability issues and requires re-development to address violations. To address this challenge, we formulated a usability framework called UMETRIX to conduct an automated usability evaluation for mobile app developers. The framework is flexible and developer friendly. The framework helps software practitioners validate and verify the presence of a usability guideline in a mobile app using code analysis. We built an automated tool using our framework that has the flexibility to create developer friendly use-cases to evaluate the presence of a guideline along with a code-snippet recommendation engine to ease developers to choose a code template for implementing the desired usability guideline. We consider this framework as a productivity tool for developers to pre-validate and evaluate usability issues during the development phases of a mobile app. As part of our research, we collaborated with open source software mobile app vendors for a field study. Additionally, we conducted industrial empirical study on a few FinTech app vendors and captured their observations and results. We collaborated with industry practitioners in their mobile app development to address mobile usability issues on their pre-released version of the mobile app. The collaboration helped us document the guidelines which are possible for evaluation using code analysis.

Abstract

Parallel algorithms on large graphs play a key role in various problems from several domains of sciences and engineering. Of these, symmetry breaking problems such as matchings and colorings are fundamental owing to a large number of applications. Algorithms for symmetry breaking problems are studied in several parallel/distributed settings over the decades. However, as the size of graphs corresponding to real-world phenomenon increase, it is imperative to use not only just parallelism but also algorithmic enhancements based on the structure of real-world graphs. A popular approach in this context is to use a graph decomposition to break the problem into multiple subproblems the solutions of which can be used to solve the original problem. A big question in this direction that is left unanswered by current research is to study which decomposition is appropriate for a given computation and a target architecture. In this context, we address the above question with respect to four problems: Maximal Matching (MM), Vertex Coloring (COLOR), Balanced Coloring (BCOL), and Approximate Weighted Matching (AWM). For these four problems, we study four different decomposition techniques including one based on bridges, one based on a random partitioning, one based on vertices of degree k for a given k, and the popular METIS based decomposition. We show that existing algorithms for the above computations on a multi-core CPU and a GPU can be significantly improved by making use of an appropriate decompo- sition of the input graph. Our study indicates that the exact decomposition to use depends both on the problem and the target architecture.