Abstract

With the exponential increase in amount of data being stored in the cloud, a lot of distributed storage systems have started moving to erasure coding based storage schemes due to their advantage of providing the same reliability as replication with a smaller storage overhead. Locally recoverable codes have started being the defacto code of choice for their ability to correct a small number of erasures by only accessing a small number of other coordinates. Maximally recoverable codes are a class of codes which recover from all potentially recoverable erasure patterns given the locality constraints of the code. In earlier works, these codes have been studied in the context of codes with locality. The notion of locality has been extended to hierarchical locality, which allows for locality to gradually increase in levels with the increase in the number of erasures. We consider the locality constraints imposed by codes with two-level hierarchical locality and define maximally recoverable codes with data-local and local hierarchical locality. We derive certain properties related to their punctured codes and minimum distance. We give a procedure to construct hierarchical data-local MRCs from hierarchical local MRCs. We then provide a construction of hierarchical local MRCs for all parameters. We then provide an alternate construction using tensor product codes that construct the code in a smaller field. This construction works for a restricted set of parameters. Research shows that the most commonly deployed LRCs have low number of global parities. Hence, we then consider three cases, with a small (and sometimes fixed) number of global and mid-level parities and provide a separate construction for them. These constructions use smaller fields still.

Abstract

This thesis proposes a novel pose-graph based formulation to map moving object trajectories onto a stationary global reference frame where the moving objects are observed from a single moving camera. This is performed in a multi-body fashion as a consequence of which we obtain accurate estimations to both the ego-camera trajectories as well as trajectories to multiple dynamic participants in the scene. This set up is dovetailed to on-road dynamic vehicles observed from a monocular sensor mounted on a moving ego-car such as in the KITTI dataset. The original triangulation problem is intractable in this scenario as it is impossible to triangulate a moving object from a single moving camera unambiguously unless there are appropriate restrictions on the object motion. The problem of unobservability also manifests in the form of the relative scale problem in classical multi-body SFM/SLAM formulations wherein there exists an unresolved scale factor (called as relative scale) such that a family of infinitely many solutions exist for any pair of motions in the scene. This prevents accurately representing the moving vehicle and camera in the same stationary frame. We overcome this relative scale factor by leveraging single-view metrology, advances in deep learning, and category-level shape estimation. We show in this paper by invoking single view reconstruction techniques, that moving objects can be represented in the same global frame in which the camera trajectory is represented without any assumptions or restrictions on object motion. More specifically we solve for the relative scale problem through a factor graph formulation where the nodes include camera and moving object poses and thereby obtain trajectories of the moving object in the starting camera frame. We use Gaussian Process based motion model prediction and lane constraints to further improve the trajectory estimates and show performance gain with previous formulations that have attacked this problem. This optimization helps us reduce the average error in trajectories of multiple bodies over real-world datasets, such as KITTI. To the best of our knowledge, our method is the first practical monocular multi-body SLAM system to perform dynamic multi-object and ego localization in a unified framework in metric scale

Abstract

Graph algorithms are one of the most robust and powerful algorithms to solve many contemporary real-world problems. The humongous real-world graph networks should be parallelized to study and gain understanding from them. Literature consists of several studies that proposed multiple methods to compute various centrality measures for a multi-core system. In this thesis, we study about farness and closeness centrality measures. To the best of our knowledge, this is the first work in parallel algorithms with respect to farness-centrality. We utilize the information about the structure of the graph to abstain from doing repetitive tasks. In this thesis, we propose a parallel algorithm to compute the farness-centrality value using graph optimizations while avoiding the redundancy on the graph using the properties detailed in this thesis below. It is inevitably tough and time-consuming to calculate the values for each and every node in social graphs since they are too big to handle even after optimizations. So, we estimate the values by taking a trade-off on time vs. quality. We accept a little reduction in the quality of results prioritizing on time. We analyze our algorithm and reduction techniques on various classes of real-world graphs. However, as these graphs evolve and change, it is crucial to study how to update farness and closeness measures on changes to the underlying graph. In this thesis, we also present approaches to compute closeness-centrality on dynamic graphs. As existing work by Sarıyuce et al. (CLUSTER 2013) in this ¨ field is limited to a single edge update, we extend it to batch update. We implement our algorithms on Intel 24-core CPU. We conduct detailed experiments to study the impact of various parameters associated with our algorithms and their implementation. Our results indicate that on a collection of real-world graphs, our techniques improve the state-of-the-art with respect to updating closeness-centrality by a factor of 10 to 34 for a batch of 100 edges on dynamic graphs and 10 to 20 on static graphs over a corresponding adaptation of the work of Sarıyuce et al. (CLUSTER 2013) ¨ and MULTIBFS respectively.

Abstract

The enormous proliferation of battery-operated portable devices such as cellphones, laptops, wireless sensor networks, etc. has made power management one of the major concerns in IC industry. The power management is being allocated an ever-higher priority by trying to sustain the life of the batteries and hence the whole device powered by this battery. In this scenario, low-dropout (LDO) voltage regulators have turned into the desired choice for low-voltage on-chip power management solutions because of their fast response, low power, and low cost of implementation. Designing an Output Capacitor LDO achieving better load/line regulation and transient characteristics with low quiescent current consumption has been a major challenge for analog designers. This thesis presents a novel low-power, area-efficient and output capacitor-less LDO that satisfies all primary requirements of power mapping for a Power Management IC (PMIC). The design introduces a dynamically biased feedback resistor which responds instantly to the output voltage variations, thereby achieving better load transient behavior. Besides, the employed adaptive-biasing technique contributes to architectural transformation to attain stability over a wider range of load currents (0-100mA). It provides a regulated voltage of 1.87V from a supply ranging from 1.92V to 3.6V with a reported load and line regulation of 0.00136mV/mA and 0.078mV/V respectively. Moreover, the circuit potentially supports the load transients either from 0A to 100mA or 100mA to 0A with a rise and fall times of 10µs. The achieved overshoot and undershoot values are 160mV and 154mV respectively. Hence, it demonstrates a substantial steady-state and transient performance with low-power thus making it suitable to be used in PMIC for battery-operated portable devices. This work also focused in designing a PVT invariant current reference whose stability decides the stable operating point of the Error Amplifier (EA) used in LDO design. The designed current reference has achieved a low figure-of-merit (FOM) of 1.3501ppm/◦C 2 on consuming a minimal quiescent current of 199.37nA. To cancel out process variations, the current subtraction technique is employed and a β-multiplier is used to compensate for mobility (µ) and threshold voltage (Vth). In addition, curvature compensation technique backed by PTAT and CTAT current cancellation is adopted to attain a lower temperature coefficient (TC). Hence, an imperceptible variation of accuracy with temperature and supply variations across all process corners is attained. An adopted trimming scheme further minimizes the overall process spread to ±1.515% without compromising on accuracy. Accordingly, a TC of 67.04ppm/◦C over a wide temperature range of -50◦C to 100◦C is obtained. Furthermore, 1.413%/V line sensitivity (LS) in the supply range of 1.38V to 3V is observed.In addition, a CMOS-only ultra low power voltage reference of 0.925V is designed to provide stable to reference to the proposed LDO so that to attain stable regulated output voltage. it achieved a temperature coefficient (TC) of 3.75ppm/◦C over a wide temperature range of -55◦C to 140◦C with 27nW power consumption.

Abstract

In the big data era, pattern mining is an important task of data mining and involves the extraction of interesting associations from large databases. In the literature, pattern mining approaches have been investigated to extract different kinds of patterns such as frequent patterns, sequential patterns, periodic patterns, utility patterns, and coverage patterns from transactional databases. The pattern mining approaches have been widely employed to improve the performance of applications in the areas of recommendation systems, e-commerce, customer relation management, internet advertising, decision support systems, social media, and so on. One of the key issues of developing pattern mining algorithms is as follows: a pattern mining algorithm has to process a huge volume of the transactional dataset. Research efforts are going on to develop pattern mining algorithms to operate on large datasets by exploiting different parallel processing paradigms, namely shared memory, shared disk, shared-nothing, GPUs, incremental, MapReduce, and Grid. In this thesis, we propose both MapReduce based and Incremental techniques to extract the knowledge of patterns called Coverage Patterns. The framework of MapReduce has become very popular to process big data. It enables the distributed processing of huge amounts of data on hundreds of machines in geographically distributed environments with robust fault-tolerance. With Incremental mining framework, when the increment database is added, it is possible to improve the performance by limiting the computation to incremental part and with the required additional processing. Given a transactional database, the coverage pattern mining involves the extraction of multiple sets of items, where each set (covers a certain percentage of transactions) satisfies relative frequency, coverage support and the overlap ratio constraints. The applicability of coverage patterns has been demonstrated in improving the performance of search engine advertising and banner advertising. In the literature, a level-wise iterative coverage pattern mining (CMine) and a pattern growth approaches have been proposed. As a first contribution, we have proposed a MapReduce based coverage pattern mining approach. The key issue is to compute the overlap ratio value of a pattern in an efficient manner under MapReduce. However, we exploit the observation that it is possible to compute the overlap ratio of a given pattern by computing the numerator and the denominator independently in a distributed manner. Experimental evaluation with both real-world and synthetic datasets demonstrate that the proposed approach significantly improves the performance over the existing CMine approach. Furthermore, we have proposed an incremental coverage pattern extraction algorithm, when an increment of the transactional database (simply Increment) is added to the existing transactional database. It has been observed that, when the Increment is added, if the order of items in the frequency list (Flist) of the database is changed, additional patterns have to be validated and require additional processing. By considering the issue of change in the order of items in the Flist, we have proposed an Incremental framework to extract coverage patterns. We have also proposed a MapReduce based Incremental approach by combining the advantages of Incremental and MapReduce techniques. We have conducted experiments on both synthetic and real-world datasets and demonstrated that the proposed approaches could improve the performance significantly even though increment size is equal to the existing transactional database. Overall, we have proposed MapReduce, Incremental, and MapReduce based Incremental approaches to extract the knowledge of coverage patterns from large transactional databases. The efficiency of the proposed algorithms is demonstrated by conducting extensive experiments on both real-world and synthetic datasets. We hope that the proposed approaches will enable the applications which extract coverage patterns to process large transactional databases

Abstract

Estimation of time delay from the received broadband signals like speech, collected at two or more spatially distributed microphones, has many applications, ranging from speaker localization, speaker separation, determining the number of speakers and tracking a moving speaker. Cross-correlation based methods like the cross-correlation of signals directly and generalized cross-correlation based methods (GCC, GCC-PHAT) have been used for several years to estimate the time delay. Performance of these methods degrades due to noise, multipath reflections, and reverberation in a practical environment, like a live room. The objective of this thesis is to address the issues of robustness and accuracy of the estimated time delay by generating multiple evidence from several cross-correlation sequences using single frequency filtering (SFF) method for decomposition of the received signals into components, one at each frequency. The accuracy of the estimated delay is improved by exploiting the amplitude information of the samples of the cross-correlation sequence around the peak corresponding to the integer delay. The estimated fractional part of the delay is shown to be not only accurate, but also robust against different types and levels of additive noise degradations. The accuracy of the estimation of the fractional part is further improved by using a trained artificial neural network model for regression. Simulation experiments with known time delay are used to evaluate the accuracy and robustness of the proposed time delay estimation methods. Complementary information to the SFF magnitude is provided by the phase component of the SFF output. The time delays are estimated accurately and independently by using the signals reconstructed from the SFF phase alone. The complex SFF spectra at each instant are used to obtain the instantaneous time delay. The instantaneous time delay is exploited for separation of individual speakers from the mixed signals received at two spatially separated microphones in a live room. The proposed time delay estimation method is also used for determining the number of speakers from the mixed signals. Applications of the time delay estimation methods are illustrated using the actual field speech data of speakers, collected at two spatially separated microphones in a live laboratory room, while the speakers are reading a text simultaneously. Performance of the proposed time delay estimation methods is evaluated in terms of accuracy and robustness.

Abstract

In this thesis, we develop a higher understanding of a dynamic road scene by Leveraging the information present in the evolution of spatial relations present between the objects of interest in the road scene. We first propose a novel motion clustering formulation over Spatio-temporal depth images obtained from stereo sequences that segments multiple motion models in the scene in an unsupervised manner. The motion models are obtained at frame rates that compete with the speed of the stereo depth computation. This is possible due to a decoupling framework that first delineates spatial clusters and subsequently assigns motion labels to each of these clusters with analysis of a novel motion graph model. A principled computation of the weights of the motion graph that signifies the relative shear and stretch between possible clusters lends itself to a high fidelity segmentation of the motion models in the scene. The fidelity is vindicated through accuracies reaching 89.61% on KITTI and complex native sequences. In the second part of thesis, we develop a semantically meaningful awareness of the dynamic road scenes for Understanding the on-road behavior of vehicles Humans typically can decompose a dynamic scene as vehicles exhibiting behaviors like ”moving away from me”, ”moving towards me”, ”changing lane” and the like. Such higher-level scene awareness can have implications on the performance of algorithms lower in the hierarchy. For example, a SLAM or state estimation algorithm can benefit from the knowledge that a car is ”parked” as features from a parked car is indeed useful for estimating relative camera motion. In this paper we decompose a road scene into vehicle behaviors such as ”parked”, ”following lane - moving away”, ”following lane - coming towards” and similar such labels. We accomplish this through Multi-Relational Graph Convolutional Networks (MR-GCN) that is proving itself to be an apt architecture to learn behaviors of agents or objects based on their evolving relations with other agents or objects in the scene. We show high fidelity behavior prediction of vehicles encountered in a variety of datasets such as Cityscapes, KITTI, ApolloScape, and Indian. More critically we show the effective model transfer from one dataset to another verifying generality and repeatability across a diverse and rich set of worldwide scenes.

Abstract

In recent years there has been a growing interest in understanding natural language for the purpose of answering questions related to science and maths. Automatically generating computer programs to solve problems posed in natural language is one of the holy grail problems of AI. A step by step approach to this would first involve understanding the problem from the text and then categorising this problem into certain categories based on algorithms and many other criteria and then finally generating the code. In this thesis we tackle the problem of automatically categorising mathematical and programming word problems. Recent advances in Deep Learning, Machine Learning based classifiers as well as the advent of word embeddings has shown impressive results in the field of Text Classification. In light of the advances in text classification we model the task of operator prediction in math word problems and algorithm prediction in programming word problems as a text classification problem and solve it using the state of the art approaches for text classification. In the first part of this thesis we deal with arithmetic word problems. Arithmetic word problems can be solved with the help of the numbers mentioned in the text and their relationships through basic mathematical operations (addition, subtraction, division, multiplication). We start by creating a model which detects the mathematical operation (+, -, *, /) that would be used to solve an arithmetic word problem. We then use this model to build an arithmetic word problem solver, a solver which takes as an input an arithmetic word problem and outputs the answer. We use various machine learning and deep learning based algorithms to build the model which detects the mathematical operation. Our solver is able to solve 81 percent of all the problems correctly in our dataset. We then broaden our focus to deal with programming word problems. These are problems in natural language which can be solved by a computer program. These problems are significantly harder than math problems for the following reasons. The solver must first decode the intent of the problem, or understand what the problem is. Then the solver needs to apply their knowledge of algorithms to write a solution program. Another reason is that, the solution programs must be efficient with respect to the given time and memory constraints. An outgrowth of this is that, the algorithm required to solve a particular problem not only depends on the problem statement, but also the constraints. These problems are routinely used by major tech companies to hire software engineers. Hence, these problems represent a significant problem for AI which has largely been untouched in current literature. As a first step towards solving these problems we introduce the task of algorithm prediction for programming word problems. We formulate the problem as a single and multi-label classification task and use state of the art Machine Learning and Deep Learning Based classification algorithms on this task. We create the first publicly available dataset for the task of algorithm prediction in a programming problem. From this dataset, we create 4 classification tasks; 2 single label classification tasks with 5, 10 classes respectively and 2 multi-label classification tasks with 10, 20 classes respectively. Our best performing classifier gets an accuracy of 62.7 percent on the 5 class single label classification whereas the best multilabel classification model has an accuracy only 9 percent lower than a skilled human. To the best of our knowledge, these are the first reported results on such a task. We make our code and datasets publicly available.

Abstract

Designing communication systems and protocols in the real-world often involves various subproblems such as: a) “what information should be sent?”, b)“how to syntactically encode this information to messages?”, c) “how to reliably transmit these messages?” among other similar questions, and d) since communication is often means to some end, “how can the communicated information be used at destination?”. While information theory and communication engineering allow us to approach a significant half of these problems, aspects such as ”what should be communicated?” and ”how should the information be used?” often demand accounting for the context and underlying objectives of designing communication systems. Building upon economic theories of communication and signaling, we approach the problem of engineering of communicative structures within an economic paradigm, and discuss various algorithmic and game-theoretic issues that emerge from this exploration. We first study the problem of optimal lossy compressions – of comparing different ways to compress a piece of information on the basis of economic utility – when communication takes place between cooperating agents. Using ideas from combinatorial optimization, we present approximation algorithms for the simple version of the problem, as well as in the presence of side-information and in presence of uniform noise. We then study the problem of designing communicative structures in presence of strategic behaviour from Sender and Receiver. We discuss three forms of design problems in this model: a) Sender-led design, b) Receiver-led design, and c) Design by some third-party principal. For the first two, we discuss the general model, Best Response characterizations, Stackelberg (or leader-follower) equilibriums, and the relevant versions of revelation principle. We also present the associated linear programs for solving them under unbounded communication and noiseless conditions, and discuss the relationship with related ideas in Persuasion and Mechanism Design. We also show the existence of instances of Sender-led (or Receiver-led) design problem where the presence of exogenous (stochastic) noise has gainful (or welfare-positive) effects for the Receiver (or the Sender respectively).Further, for the problem of design by third-party principals, we propose a novel methodology of empowering the third-party designer (say, Wirepuller) with ability to deliberately design channel noise. We discuss how this simplifies the problem of selecting some optimal protocol such that neither the Sender not Receiver is incentivized to deviate from it, and provide the two-sided relevation principle for the problem, and present the corresponding linear programming formulation. We also discuss how this framework provides an economic model of ambiguous signalling conventions. Finally, we provide a preliminary discussion of the sequential version of this model, with infinitehorizon discounted rewards as objectives, in terms of communicating states of Markov Decision Processes (MDPs). This allows us to move beyond the static assumptions, towards designing continual communication systems with long-term preferences. We provide an analysis and demonstrate the sufficiency of single state history for the Receiver-led design, i.e. policy that is strategyproof (or incentive compatible) for planning under strategic revelation of state information.

Abstract

Increasing the spectral efficiency of the cellular networks has been and continues to be one of the major factors from 1G to 5G and beyond. In this regard, cellular operators have turned towards heterogeneous cellular networks (HetNets) to improve the area spectral efficiency of the networks. One of the significant challenges in HetNets is the underlying co-channel interference that is experienced by the users. Though the network throughput increases due to a better area spectral efficiency of a HetNet, there is a possibility that high interference will make few link capacities close to zero when users regard interference as noise (IAN). In other words, the dynamic nature of these co-channel interference links is also a problem due to its threat of causing outage or reduction in quality of service (QoS) to the UEs. Instead of trying to avoid interference, nodes in the network can also exploit it if they are equipped with such capabilities. In this work, successive interference cancellation (SIC) technique is investigated to reduce the crosstier interference in a reverse time division duplexing (RTDD) two-tier HetNet. In this work, the sum link capacity expressions for an RTDD HetNet, where the users use SIC to remove the cross-tier interference is derived. The derived sum link capacity expression for SIC is compared with that of IAN to derive a switching condition on using SIC. This opportunistic use of SIC (which is referred to as switching in this thesis) ensures a minimum sum link capacity (proportional to the desired signal strengths) independent of the interference links, thereby solving the QoS problem. A network operator can also remove the interference dependency by splitting the available resources between the tiers. However, we have proven that the maximum sum link capacity that can be achieved by orthogonal resource allocation schemes is the same as the minimum that is ensured by switching. System-level simulations are done to show the gain in the overall system capacity of switching compared to only using either IAN or SIC for randomly paired UEs. The system capacity for IAN, SIC, and switching can be further improved by optimizing the selection of UEs across the tier (user pairing) that use the same frequency resources. In this regard, the user pairing scheme that should be used for IAN, SIC, and switching cases is formulated as a discrete optimization problem. This optimization problem also encompasses the cases where all the UEs do not need to be paired. The Hungarian algorithm is used to solve this optimization problem after some prepossessing done to the cost matrix. Through system-level simulations, the gains in system capacities for Hungarian paired UE using IAN, SIC, and switching is shown compared to their random counterparts.The above-discussed results assume that the UE has the necessary demand for the supported downlink (DL) and uplink (UL) data rates. In the case of any traffic asymmetries, the subframe allocation can be dynamically adapted in a synchronized TDD HetNet. However, the inability of a synchronized RTDD HetNet’s frame structure questions the usefulness of these results when there is an asymmetric data demand (DLUL). In such cases, the UE does not need to operate at its full capacity in UL. Hence, it would throttle either the transmission rate or power. Rate expressions for rate and power throttling are derived for cases where UE uses SIC or regards IAN. System-level simulations are performed to compare the overall system throughput of IAN and SIC for different traffic asymmetries (DL:UL ratios). It is shown that if UEs does rate throttling, then using SIC would improve the overall achievable rates compared to IAN, and vice-versa for power throttling