Abstract

Symmetry breaking is a fundamental operation in distributed computing. It has applications to several important and fundamental problems such as graph vertex and edge coloring, maximal independent sets and the like. Although this area has been studied for over 3 decades now, deterministic algorithms for symmetry breaking that run in poly-logarithmic number of rounds are not known. However, randomized algorithms that run in poly-logarithmic number of rounds are known starting from Luby’s algorithm. Recently, orientation on edges was considered and it was shown that an O(
) coloring of the vertices of a given oriented graph can be arrived at using essentially O(log
+ √log n) bits of communication. In our work, we further demonstrate the power of orientation of edges in symmetry-breaking. We present efficient algorithms to construct fractional independent sets in constant degree graphs using very low order communication between the vertices. For instance, we show that in bounded degree graphs and planar graphs, it is possible to construct a fractional independent set by exchanging O(1) bits. Further, we present algorithms to construct maximal independent sets in bounded degree graphs and oriented trees. Our algorithm for constructing an MIS of an oriented tree uses only O(log n) bits of communication. We also aim at an empirical analysis of distributed vertex coloring algorithms. To this end, we compare the empirical performance of the recently proposed distributed vertex coloring algorithm which uses orientation with that of Luby’s algorithm. To get a good coverage we look at the cycle graph on n vertices, cliques, and random graphs from the family G(n, p) by controlling n, p and np. The results of our experiments fairly demonstrate the improvement in the bit complexity of the algorithm proposed by the authors of the oriented coloring algorithm. vi

Abstract

Automatic speaker verification (ASV) is the task of verifying a person’s claimed identity from his/her voice using a digital computer. The existing ASV systems perform with high accuracy of verification when the speech signal is collected close to the mouth of the speaker (< 1 ft). However, the performance of the ASV systems reduces significantly for speech signals collected at a distance from the speaker (2-6 ft). The objective of this work is to address some research issues in the processing of speech signals collected at a distance from the speaker, for text-dependent ASV system. The distant speech signal is collected using single channel microphone. An acoustic feature derived from short segments of speech signals is proposed for ASV task. The key idea is to exploit the high signal-to-noise nature of short segments of speech in the vicinity of impulse-like excitations. We demonstrate that the proposed feature suffers lesser degradation with distance when compared to the widely used Mel-frequency cepstral coefficients (MFCCs), and also yields better performance of speaker verification than MFCCs. We propose a method of begin-end detection based on the strength of the spectral peaks. A score normalization method is proposed by considering only the robust regions of speech signal. In addition, the regions of speech signal with high signal-to-reverberation ratio are identified, and greater weightage is given to these regions. These modifications are shown to result in a systematic improvement in the performance of the speaker verification system. The use of additional features of duration and pitch is shown to further improve the performance of speaker verification system for distant speech. Keywords: automatic speaker verification, text-dependent, distant speech, high signal-to-noise ratio, pitch, duration. iii

Abstract

When humans modify speaking rate they do not perform a simple expansion or compression of the speech signal. In order to maintain the intelligibility and naturalness of the speech, they modify some of the characteristics of the speech production mechanism in a complex way. This causes the acoustic features extracted from the speech signal to change in a complex way. These changes affect the performance of speech systems like speech recognition, speaker recognition etc. Most of the studies on the effect of speaking rate on acoustic features focus on features at segmental and suprasegmental level. The present work focuses on analysis of the effects of speaking rate on features at subsegmental level. Three features at subsegmental level, namely, instantaneous fundamental frequency, strength of excitation of epoch and perceived loudness are chosen, and their variation with speaking rate is studied. It was observed that instantaneous fundamental frequency increases with increase in speaking rate, but when speaking rate is decreased the changes in the instantaneous fundamental frequency is speaker-specific. Similar observations have been found in the case of strength of excitation at epoch. Strength of excitation decreases with increase in speaking rate, and the change in strength of excitation is speaker-specific when speaking rate is decreased. The effect of speaking rate on the perception of loudness is also studied using perceptual loudness studies. It was observed that fast speech was perceived louder than normal speech for majority of speakers, whereas the difference between perception of loudness of normal and slow speech is speaker-specific. It was also observed that speaking rate does not have significant affect on objective loudness measure. A modified measure of loudness in the case of speech at different speaking rates is proposed, and its variations correlate with results from perceptual loudness tests. The variations of subsegmental level features with speaking rate are incorporated in a non-uniform duration modification method. Subjective studies on the synthesized speech showed that incorporation of the subsegmental variation improved the quality of speech at different speaking rates. Keywords: Speaking rate, spontaneous speech, segmental features, instantaneous fundamental frequency, strength of excitation, perceived loudness and duration modification.

Abstract

Graph coloring is a fundamental problem in Computer Science. Despite its status as a computation- ally hard problem, it is still an active area of research. Depending on the specific area of requirement or an application, there are several variants of coloring. One such variant of graph coloring is Acyclic Graph Coloring. This requires that after a graph has been colored there should not exist any cycle that runs on vertices that are colored by only two colors. Such a cycle is called a bichromatic cycle. When a coloring does not present itself with a bichromatic cycle, it is said to have acyclically colored the given graph. As with the case of proper coloring of graphs, acyclic coloring can either be on vertex set or the edge set of a graph. When such a coloring is performed on the edges of a graph, a bichromatic cycle is said to be one that runs on the edges that are colored by only two colors. In absence of such a bichromatic cycle, an edge coloring is said to be an acyclic edge coloring of that graph. The smallest number of colors required to acyclically vertex color a graph is called its acyclic chro- matic number and is denoted by a(G). Similarly, the smallest number of colors required to acyclically edge colors a graph is called its acyclic edge chromatic number and is denoted by a′ (G). There are several applications of acyclic coloring of a graph which include Hessian computation, applications in coding theory as well as other theoretical problems such as Minimim Feedback Vertex Set. In addition to this, acyclic chromatic numbers are closely related to several other types to colorings of a graph each of which are applicable in several other fields of interest. A notable example among these is the star chromatic number of a graph and star arboricity. Star graphs are used to model star network topologies that have applications in computer networks and distributed computing. The problems of finding the acyclic chromatic number or acyclic edge chromatic number of a graph are known be NP-hard. Also, there is a very little knowledge about such a characteristic of a graph even for the most simple classes of graphs like complete graphs. This thesis is dedicated to explore some common classes of graphs for which the acyclic chromatic number or the acyclic edge chromatic number can be found out. We also try to strengthen our results by providing contructive bounds and efficient linear time algorithms for the graphs that we study. In this respect, we have presented appreciable results for acyclic edge chromatic number of complete graphs when the number of vertices can be represented as a certain product of a prime and numbers one less than a prime. Another class of graphs that we have considered are the grid-like graphs. The name implies that these graphs are structurally similar to a standard grid graph. More specifically, these graphs can be represented as a product of certain simple class of graphs such as a path or a cycle. In this case, we have successfully acyclically vertex colored some specific cases of these graphs. Lastly, we mention here that through out this work, we have provided elaborate intuition on how we arrived at our coloring schemes and how such schemes are helpful in gaining an understanding of the structure of the graphs in question. This intuition can be very helpful for gaining an overall understanding of this work apart from the mathematical proofs. It should also be an important asset in any possible extension of our work.

Abstract

The area of graph mining deals with mining frequent subgraph patterns, graph classication, graph clustering, graph partitioning, graph indexing and so on. In this thesis, we focus only on the area of frequent subgraph mining and more precisely on maximal frequent subgraph mining. MARGIN is a maximal subgraph mining algorithm that moves among promising nodes of the search space along the “border” of the infrequent and frequent subgraphs. This drastically reduces the number of candidate patterns in the search space.

Abstract

Contracts play a major role in establishing binding relationships between various business units and also between businesses and their customers. A contract consists of numerous activities that have to be carried out by the involved parties and contract clauses that address specific concerns in the business process interaction. An e-contract is a contract modeled, specified, executed and deployed (controlled and monitored) by a software system (such as a workflow system). As contracts are complex, their deployment is predominantly established and fulfilled with significant human involvement. This necessitates a comprehensive framework for generic fulfillment of e-contracts. So, the goal of e-contracting is to transform a traditional contract document into an executable e-contract.

Abstract

The rapid increase in the performance of graphics hardware have made the GPU a strong candidate for performing many compute intensive tasks, especially many data-parallel tasks. Off-the-shelf GPUs are rated at upwards of 2 TFLOPs of peak power today. The high compute power of the modern Graphics Processing Units (GPUs) has been exploited in a wide variety of domain other than graphics. They have proven to be powerful computing work horses in various fields. We leverage the processing power of GPUs to solve two highly compute intensive problems: Singular Value Decomposition and Ray Tracing Parametric Patches. Singular Value Decomposition is an important matrix factorization technique used to decompose a matrix into several component matrices. It is used in a wide variety of application related to signal processing, scientific computing, etc. However, little work has been done to implement Singular Value Decomposition on parallel architectures. Direct ray tracing of parametric patches provides high geometric precision resulting in less artifacts and results in better rendering using true normals for lighting at every pixel. Researchers have developed algorithms to ray tracing parametric surfaces directly, but these algorithms are either computationally expensive or have other disadvantages. Both these problems are both computationally demanding and amenable to massively parallel implementations. Singular Value Decomposition computations requires factorizing a dense matrix into component matrices. Finding the intersection of a ray with a B´ezier patch requires finding the roots of a 18 degree polynomial. They require enormous number of floating point operations. The advent of GPUs with support for higher precision and their ever-growing amount of parallel horsepower makes them a tempting resource for such numerical computations. We propose parallel implementations for these problems on a GPU. They outperform the best CPU implementations available significantly. We implement the Singular Value Decomposition of a dense matrix on GPUs using the two step Golub Reinsch algorithm. In the first step, bidiagonalization decomposes a given dense matrix into bidiagonal matrix and component orthogonal matrix using a series of Householder transformations. In the next step, diagonalization is performed by applying the implicitly shifted QR algorithm which takes O(n) iterations. It decomposes the bidiagonal matrix into a diagonal matrix and orthogonal matrices. Each householder transformation reduces a row-column pair. We divide the number of householder transformations required into n=L blocks. L householder transformations are applied in parallel by mapping them to CUBLAS operations to derive maximum performance. We thus, exploit the underlying hardware to the maximum. We use a hybrid implementation for the diagonalization step that splits the computations between the CPU and the GPU. Every iteration of the QR algorithm applies Givens v vi rotations on the elements of the bidiagonal matrix and the corresponding inverse rotations are applied on the rows of the orthogonal matrices which are initially identity. Transformation applied on each row depends on the previous row and transformation applied on it, thus making computations on every row independent. Rotations on the elements of the bidiagonal matrix are applied on the CPU. The inverse transformations are performed on every row in parallel on the GPU. We combine the power and functionality of using CUDA and the high performance software libraries available with it to exploit the GPU parallelism and achieve high computing performance. This approach can be used for solving other graphics and non-graphics tasks. Our complete Singular Value Decomposition implementation outperforms the MATLAB and Intel R Math Kernel Library (MKL) LAPACK implementation significantly on the CPU.We show a speedup of upto 60 over the MATLAB implementation and upto 8 over the Intel MKL implementation on a Intel Dual Core 2:66GHz PC with NVIDIA GTX 280. We are able to compute the Singular Value Decomposition of very large matrices, upto 14K which is otherwise impossible on the CPU due to memory limitations. The GPUs are limited to single precision numbers, though that is changing with the newer generations. The error due to lower precision was less than 0:001%. We present correct ray tracing of parametric bicubic surfaces on the GPU using Kajiya’s approach without subdividing to the GPU.We use a BVH representation of the patches to remove non-intersecting rays. The process starts with a list of rays to be traced in each frame. The BVH is traversed for each ray to enumerate the potential ray-patch intersections. This method forms a univariate 18-degree polynomial for each intersection and finds its roots using the Laguerre’s method. The real roots are the parameter values at the intersection points. Polynomial formation and root finding for

Abstract

This work is about coverage and exploration with multiple robots, and it especially focuses on the terrains represented as digital elevation models. Our work in coverage utilizes greedy decomposition of terrains on the basis of both visibility and time, and intends to show its merits over the aforementioned approaches. We introduce the notion of coupled metrics which not only enables us to ascertain the ‘goodness’ of a terrain point, but also allows us to provide a reasonable solution to the hitherto un-tackled problem of finding good starting points for the robots. The proposed metric approach also allows us to affect a co-ordinated multi-robot effort, something else which is lacking in existing coverage literature (although there are significant works in 2D exploration literature). We introduce joint allocation strategy variants which ensure that the robots cover efficiently in reduced time or reduced sum of path lengths. The issues of robustness and proper observability are also addressed in subsequent variants of the problem. We provide a methodology that guarantees coverage as long as one of the robots is functional and a visibility model which enforces sufficiency constraints on terrain observability. Our work on exploration deals with both 2D and 3D terrains. A more efficient metric is utilized for choosing the next view point; Extensive simulations both in 2D and 3D, and real world experiments on Pioneer-3DX establish its efficacy over the ones in use now. Moreover, apart from using the previously used synchronous frontier allocation mechanism for multiple robots, we propose an asynchronous frontier allocation strategy; This is shown to be advantageous not only in terms of effectiveness, giving us much better exploration times but also in implementation terms. In 3D, we propose an exploration methodology for UAVs covering terrains represented as heightmaps. We introduce a way for calculating expected visibilities ( expected information gain ) and a way of utilizing information attained from terrain features already explored in deciding the next points of visit.

Abstract

The problem of evaluating software architecture is an important problem of software engineering. The purpose of the architecture evaluation of a software system is to analyze the architecture to identify potential risks and to verify that the quality requirements have been addressed in the design. Different techniques have been developed to evaluate a software architecture. Most common among these techniques are model based approaches, metric based methods and scenario based analysis. Service-Oriented Architecture (SOA) is an architectural approach (or style) for constructing complex software-intensive systems from a set of universally interconnected and interdependent building blocks, called services. Services used in composite applications may be brand new service implementations, they may be fragments of old applications that were adapted and wrapped, or they may be combinations of the above. The emergence of SOA as an approach for integrating applications presents many new challenges to organizations resulting in significant risks to their business. Particularly important among those risks are failures to effectively address quality attribute requirements such as performance, availability, security, and modifiability. Hence, it becomes necessary to evaluate a service oriented architecture based application in the context of quality attributes. In this dissertation, our aim is to investigate the limitations of using scenario based software architecture evaluation approaches in SOA paradigms. We investigate that most of the current approaches in the literature of software architecture, do not consider the factors that are more specific in SOA based applications. For example, to the best of our knowledge, current evaluation approaches do not address the quality issues that arises due to a SOA governance lifecycle. There must be a mechanism to investigate how governance policies are impacting the quality attributes (positively or negatively). We show that a governance lifecycle is a critical element of any SOA based application and must be analyzed in the context of quality attributes. Current software architecture evaluation methodologies also have not been studied and used in the areas of modern cloud based services. In brief, we look at the problem from following different angles: (1) evaluating a SOA governance model; (2) analyzing data security risks in cloud based service environments; and (3) evaluating the attack surface and root cause of an attack in an SOA based enterprise application. Security is considered as the most prominent quality attribute in software applications. Therefore, throughout our work, we primarily focus on security analysis, out of all the quality attributes. The impact of SOA governance mechanism on the organization’s quality attributes is largely not studied or evaluated in a structured manner. To overcome this problem, we propose SAGE (Service Oriented Architecture Governance Evaluation) as a quantitative approach, to evaluate the impact of SOA governance policies on prominent quality attributes. Our approach facilitates an exhaustive quantitative impact analysis to evaluate the effectiveness of SOA governance policies. This can be further used to estimate the current maturity level of any SOA based enterprise. To evaluate the data security risks in cloud based services, we did a survey of prominent security issues in current cloud computing environments. Based on these issues, we propose a risk analysis approach for analyzing the data security risks. This approach can be used by any potential service user, before putting his confidential data into a cloud computing environment. As a solution to the security analysis in SOA based enterprise applications, we present an approach to compute the attack surface in a SOA based enterprise application. We also discuss that how we can map an attack surface from a service layer to a business process layer. Further, we present an approach to investigate the root cause of an attack. This approach can be used directly by any SOA based enterprise to evaluate the security and therefore a possible reduction in security attacks. In our work, we attempt to answer the following questions: (1) Are the existing software architecture evaluation approaches sufficient in service oriented paradigms? (2) If no, what are the areas that remain unexplored? (3) How to address these unexplored areas? Our study brings out some interesting results. We show that evaluation of a SOA governance lifecycle is necessary to estimate the quality and dynamic behavior of the composed application. Our work also unveils various security issues in cloud based service environments. The presented work is an initial attempt to make the SOA evaluation and management more structured and effective.

Abstract

Sentence realisation involves generation of a well-formed sentence from a bag-of-words. Sentence realisation has wide range of applications ranging from machine translation to dialogue systems. In this thesis, we present five models for the task of sentence realisation. The five models proposed are sentential language model, subtree-type based language models (STLM), head-word STLM, part-of-speech (POS) based STLM and marked head-POS based LM. The proposed models employ simple and efficient techniques based on N-gram language modeling and use only minimal syntactic information as dependency constraints among the bag-of-words. This enables the models to be used in wide range of applications that require sentence realisation. We have evaluated the proposed models on two different types of input (gold and noisy). In the first input type, dependency constraints among the bag-of-words are extracted from treebank which is manually transcribed and in the second input type, the dependency constraints among the bag-of-words are noisy as they are automatically extracted from a parser. We have evaluated the models on noisy input in order to test the robustness of our models. From the results, we observed that the models performed well even on the noisy input. We have achieved state-of-the-art result for the task of sentence realisation. We have also successfully tested a graph based nearest neighbour algorithm for the task of sentence realization. We have shown that using the graph-based algorithm, the computational complexity can be reduced from factorial to quadratic at a cost of 2% reduction in the overall accuracy. This method makes our module suitable for employment in several practical applications.