Abstract

A dictionary data structure is a key-value store which supports insert, search and delete operations. Conventional data structures such as balanced binary search trees and hash tables are good both in theory and practice. However, these dictionaries are not adaptive as they do not exploit the temporal locality in key access patterns over time. On the other hand dictionaries like splay trees and working-set trees adapt to the changing key access patterns by reorganizing themselves with every key access. Consequently, the set of most frequently accessed key, i.e. the working-set, can be retrieved quickly in these dictionaries. With the gaining popularity of GPU based accelerator platforms for general purpose computing, several data structures such as B-tees and hash tables have been successfully ported to these platforms. In this thesis, we propose heterogeneous (CPU+GPU) hash tables, that optimizes operations for the frequently accessed keys. The basic idea is to maintain a dynamic set of most frequently accessed keys in the GPU memory and the rest of the keys in the CPU main memory. Further, queries are processed in batches of fixed size. We measured the query throughput of our hash tables using Millions of Queries Processed per Second (MQPS) as a metric, on different key access distributions. On distributions, where some keys are queried more frequently than others, we achieved on an average 10x higher MQPS when compared to a highly tuned serial hash table in the C++ Boost library; and 5x higher MQPS against a state of the art concurrent lock free hash table. The maximum load factor on the hash tables was set to 0.9. On uniform random query distributions, as expected our hash tables do not out perform concurrent lock free hash tables, nevertheless matches their performance. The second main contribution of this thesis is the design and implementation of self organizing Cache Oblivious B-trees (CO B-tree) which use the memory hierarchy effectively to reduce the number of cache misses incurred while processing a query. A cache oblivious B-tree (CO B-tree) incurs optimal number of cache block transfers across any two levels in a multi level memory hierarchy. In this work, we propose two variants of the dynamic CO B-tree, a working set CO B-tree and a hybrid CO B-tree. They reorganize themselves with every key access facilitating faster retrieval of the frequently accessed keys with the minimum number of cache misses. Theoretically, we prove that a self organizing CO B-tree can be designed with a small additive factor overhead to the already proven bounds for the data structure. In empirical experiments we compare both our data structures to a B-tree, an AVL tree, a top down splay tree and a static/dynamic CO B-tree. Our CO B-trees, on average, have 1.5 to 2 times lesser cache misses compared to the B-tree and the top down splay tree respectively. For higher degree of temporal locality in access patterns, the hybrid CO B-tree has better query throughput (queries processed per unit time) and lesser number of cache misses compared to the rest of the data structures including a static CO B-tree.

Abstract

Relation between reality and language is an age old problem. The term ‘meaning’ embodies hordes of issues which are found factored into the problem. One contemporary aspect of the problem is how to computationally specify ‘meaning’ of a word. To conceive a web resource for the ‘meaning’ of a word involves ontological as well as linguistic considerations. Usually ‘meaning’ of a word is specified using other words like in dictionaries, thesauruses etc. Ontologically ‘meaning’ of a word is thought to be specified in terms of it participating in classes, relations and events. Both these accounts seem extensional as they refer to objects outside a word to determine its ‘meaning’. For both of these accounts words ‘mean’ only in the company of other words or in association with the outlying reality which words represent. We take a view that ‘meaning’ of a single word has a necessary aspect of intension. This intension is in situ formations embodied in the ‘meaning’ of a word. The in situ forms are present intrinsically in the ‘meaning’ of words and are the causes for the association of words as well as assertion of knowledge. The work presents a new approach to formal ontology of natural language based on in situ formations in the ‘meanings’ of words and pairings of words. The basic motivation is to computationally manipu- late language at the level of intrinsic lexical meanings. Lexical meanings, in the transaction of language, have discrete intrinsic forms of types and classes. Intrinsic sense-types and sense-classes have been iden- tified for 3867 verbs,1980 adverbs and 300 adjectives. Identification of sense-types and sense-classes for adjectives and nouns is in progress. These types and classes are unambiguously locatable in parts of speech through collective introspective inquiry first and then enriched with the help of computational methods of corpus study. This work reports on the construction of a web resource, in which ‘meanings’ of English words are given in terms of formal ontology of language inspired by Leibniz, Patanjali and Bhartrihari. The experimental results on testing data of SemEval - 2010 (word sense induction and disambiguation task), the measure of synonimity of verbs and nouns and the inferences drawn from the sense-class and sense-type distributions show the potentiality of the resource. Integration of resource of sense-types and sense-classes with lexical grammar of cases, interpreted as verb-noun pairs, leads to paraphrasing of English sentences into graphs of formal senses. This gives confidence that the resource can be enriched through these studies and resource exploration framework can be made such that as a resultant resource itself is continuously enriched. The proposed ontology of verbs, adverbs, adjectives and nouns, if can be implemented for large numbers of words, would make the resource adventitious in knowledge computing. We aim at extensive lexical coverage of language to show that our approach is non-reductionist unlike semantic prime approaches. Rigorous formal underpinning of the ontology resource will enhance capability, possibility and accuracy of ontology driven NLP and AI applications. It is a growing resource and as yet it covers only portion of English language. However, the resource framework is designed to include resource enriching tasks and revisionary studies.

Abstract

The thesis posits that analytical studies relating to knowledge based industries (especially social media) as rent seeking organization must be revisited. Proponents of cognitive capitalism, especially Autonomist Marxists attribute sources of revenue in knowledge based industries to “rent seeking be- havior” departing from Marx’s labor theory of value. Industrial production process requires capitalist’s active supervision for efficient production and value of labor is calculated with respect to socially ab- stract labor time invested in production process. Autonomist Marxists contest that after the crisis of Workerism(resulting in reduction in working time) and rise of knowledge as productive force, capital has become external to production process while extracting collective knowledge as a rent for provisions to access means of production. Knowledge has always been central to organization of societies, although Autonomist Marxists and economists indicate a renewed interest in knowledge (in its technological ca- pacity) owing for its effects on growth and productivity in world economy. We claim that production process must be analyzed in totality to fully apprehend the realities of today’s political economy and not just limited to advanced capitalist countries, which Autonomist Marxists neglect in their theories of cognitive capitalism. Our criticism is two fold. Firstly we present our critique to cognitive capitalist theories by analyzing Facebook: an epitome of post-Fordist management practices, and claim that Face- book is not a rent seeking organization. If Facebook is indeed a rent seeking organization, we argue that it undermines the contributions of software creators and contributors who maintain the large scale oper- ations of the firm. Secondly knowledge labors represent only one aspect of the class of multitude(term popularized by Hardt and Negri in Empire, refers to the class of collective social subjectivities present today) while other, which is often neglected, is the rise of precarious labor in global south. Marx argued that opening up of luxury industry stands on the shoulder of relative surplus population, “a population often made available owing to the preponderance of constant capital in other branches of production; these base themselves in turn on a preponderance of the element of living labor, and only gradually pass through the same trajectory as other branches”. Knowledge industries relies heavily on physical infrastructure which increases the organic composition of firm. Organic composition of firm is the ratio of constant capital(machines and raw materials) to variable capital(value of labor). The crisis of value is not because of cognitive capitalism but because of inherent antagonism between capital-labor relation- ship at play in global value chain. For Knowledge based industries, in order to recover the tendential fall of rate of profits (owing to relative increase in constant capital to variable capital) low organic firms are introduced in economy so as to shift the surplus to advanced level of production. Lastly we part from the critique of cognitive capitalism and asses the tragedy of commons evidently indicated by rising privatization of modes of production which is central to immaterial production

Abstract

Spatial modulation (SM) is a recently developed multiple-input-multiple-output (MIMO) technique that uses multiple transmit antennas in a innovative fashion. In SM, a group of information bits is mapped into two constellations: a signal constellation based on modulation scheme, and a spatial con- stellation to encode the index of a transmit antenna. At any time instant, only one transmit antenna is active, whereas other transmit antennas radiate zero power. This completely avoids inter-channel in- terference at the receiver and relaxes the stringent requirement of synchronization among the transmit antennas. Moreover, unlike conventional MIMO system, SM does not require multiple RF chains at the transmitter. SM can outperform other state-of-the-art MIMO schemes in terms of computational complexity, if many transmit antennas are available. Unfortunately, this makes SM useful only in the downlink of the cellular network, where a base station can be equipped with a large number of antennas. On the other hand, use of multiple antennas in mobile terminals has practical limitations. Besides constraints on complexity and cost, decreasing terminal size restricts the application of SM in the uplink of cellular network. To overcome these problems, distributed spatial modulation (DSM) offers a promising solu- tion. In DSM, multiple relays form a virtual antenna array and assist a source to transmit its information to a destination by applying SM in a distributed manner. The source broadcasts its signal, which is inde- pendently demodulated by all the relays. Each of the relays then divides the received data in two parts: the first part is used to decide which one of the relays will be active, and the other part decides what data it will transmit to the destination. An analytical expression for symbol error probability is derived for DSM in independent and identically distributed (i.i.d.) Rayleigh fading channels. The analytical results are later compared with Monte Carlo simulations. Next, DSM implementation is extended to a cognitive network scenario where the source, relays, and destination are all equipped with cognitive radios. A dynamic frequency allocation scheme is proposed to improve the performance of DSM in this scenario. The frequency allocation is modeled through a bipartite graph with end-to-end symbol error rate (SER) as a weight function. The optimal frequency allocation problem is formulated as minimum weight perfect matching problem and is solved using the Hungarian method. Finally, numerical results are provided to illustrate the efficacy of the proposed scheme.

Abstract

Reconstruction of images from projections lays the foundations for computed tomography (CT). Tomographic image reconstruction, due to its numerous real world applications, from medical scanners in radiology and nuclear medicine to industrial scanning and seismic equipment, is an extensively studied problem. The study of reconstructing function from its projections/line integrals, is around a century old. The classical tomographic reconstruction problem was originally solved 1917 by J. Radon, proposing and inversion method now known as filtered backprojection (FBP). It was later shown that infinitely many projections are required to reconstruct an image perfectly. It is understood that incomplete data would leads to artifacts in the reconstructed images. In addition to the artifact problem, arising due to limited data availability, the reconstructed images are known to be corrupted by noise. We study these two problems of noisy and incomplete data in the follwoing two setups. Nuclear imaging modalities like Positron emission tomography (PET) are characterized by a low SNR value due to the underlying signal generation mechanism. Given the significant role images play in current-day diagnostics, obtaining noise-free PET images is of great interest. With its higher packing density and larger and symmetrical neighbourhood, the hexagonal lattice offers a natural robustness to degradation in signal. Based on this observation, we propose an alternate solution to denoising, namely by changing the sampling lattice. We use filtered back projection for reconstruction, followed by a sparse dictionary based denoising and compare noise-free reconstruction on the Square and Hexagonal lattices. Experiments with PET phantoms (NEMA, Hoffman) and the Shepp-Logan phantom show that the improvement in denoising, post reconstruction, is not only at the qualitative but also quantitative level. The improvement in PSNR in the hexagonal lattice is on an average between 2 to 10 dB. These results establish the potential of the hexagonal lattice for reconstruction from noisy data, in general. In the limited data scenario we consider the Circular arc Radon Transform (CAR). Circular arc Radon transforms associate to a function, its integrals along arcs of circles. The transforms involve the integrals of a function $f$ on the plane along a family of circular arcs. These transforms arise naturally in the study of several medical imaging modalities including thermoacoustic and photoacoustic tomography, ultrasound, intravascular, radar and sonar imaging. The inversion of such transforms is of natural interest. Unlike the full circle counterpart -- the circular Radon transform -- which has attracted significant attention in recent years, the circular arc Radon transforms are scarcely studied objects. We present an efficient algorithm that gives a numerical inversion of such transforms for the cases in which the support of the function lies entirely inside or outside the acquisition circle. The numerical algorithm is non-iterative and is very efficient as the entire scheme, once processed, can be stored and used repeatedly for reconstruction of images.

Abstract

Urbanization is rapidly increasing in almost every city in India. Huge infrastructure developmental plans have been laid by government and private organizations. There are quite a few codes and buildings by laws are available for construction of these buildings but many of them lack in addressing the parameters for seismic design. Some issues related to seismic behaviour are still not resolved. Researchers all over the world are continuously working towards development of latest techniques for improving earthquake safety of buildings. Among several aspects, the fundamental natural period ‘T’ of the building is one of the important parameters in the earthquake resistant design of buildings. The fundamental period will decide the base shear to be resisted by the structure. Apart from knowing the seismic demand the natural period also gives insight about the damage status of the structure. Present version of Indian seismic code gives empirical formulae for natural period. These expressions of the fundamental period is originally developed based on Californian earthquakes and adopted by many of the seismic codes around the world; including current Indian seismic code IS 1893: 2002. This research study aims to check the viability of the current provision of Indian seismic code for the approximate formulae given for RC buildings with infill walls. For this purpose, ambient vibration study has been carried out in Indian cities viz. Hyderabad, Chandigarh, Mumbai and Nanded, by placing vibration sensor on topmost accessible floor. All together there are 90 RC MRF buildings and 14 RC SW buildings were tested out of which 74 RC MRF and 14 RC SW buildings were selected for further analysis. With the regression analysis performed on the new database, a conservative empirical expression is proposed for finding natural period T of RC MRF buildings and RC SW buildings.The measured periods have been compared with the code provisions. Study found that current empirical equation holds good only for low-rise RC MRF buildings, it often overestimates the natural period for medium-rise buildings with more than thirty metre heights. In case of RC SW buildings it underestimates the natural period and there by overestimates the seismic demand of a building. Hence there is an urgent need for revision of the empirical expression.

Abstract

Image based reconstruction of urban environments is a challenging problem that deals with optimization of large number of variables, and has several sources of errors like the presence of dynamic objects. Since most large scale approaches make the assumption of observing static scenes, dynamic objects are relegated to the noise modelling section of such systems. This is an approach of convenience since the RANSAC based framework used to compute most multiview geometric quantities for static scenes nat- urally confine dynamic objects to the class of outlier measurements. However, reconstructing dynamic objects along with the static environment helps us get a complete picture of an urban environment. Such understanding can then be used for important robotic tasks like path planning for autonomous navigation, obstacle tracking and avoidance, and other areas. While the literature has been fairly dense in the areas of scene understanding and semantic labeling there have been few works that make use of motion cues to embellish semantic performance and vice versa. we address the problem of semantic motion segmentation, and show how semantic and motion priors augments performance. We propose an algorithm that jointly infers the semantic class and motion labels of an object. Integrating semantic, geometric and optical flow based constraints into a dense CRF model we infer both the object class as well as motion class, for each pixel. We found improvement in performance using a fully connected CRF as compared to a standard clique-based CRFs. For inference, we use a Mean Field approximation based algorithm. We also propose a system for robust SLAM that works in both static and dynamic environments. To overcome the challenge of dynamic objects in the scene, we propose a new model to incorporate semantic constraints into the reconstruction algorithm. While some of these constraints are based on multi-layered dense CRFs trained over appearance as well as motion cues, other proposed constraints can be expressed as additional terms in the bundle adjustment optimization process that does iterative refinement of 3D structure and camera / object motion trajectories. Our method outperforms recently proposed motion detection algorithms and also improves the semantic labeling compared to the state-of-the-art Automatic Labeling Environment algorithm on the challenging KITTI dataset especially for object classes such as pedestrians and cars that are critical to an outdoor robotic navigation scenario. We show results for accuracy of motion segmentation and reconstruction of the trajectory and shape of moving objects relative to ground truth. We are able to show average relative error reduction by 41% for moving object trajectory reconstruction relative to state-of-the-art methods like TriTrack[23], as well as on standard bundle adjustment algorithms with motion segmentation.

Abstract

Preventing traffic congestion by forecasting near time traffic flows is an interesting and important problem as it leads to effective use of transport resources. Many times congestion is caused due to social events like concerts, conferences, etc. happening in the city. Social network provides relevant and useful information about social events and about sentiments of humans towards such events. Thus, with the help of social network, we can estimate which humans might attend a particular event (in near time). This can help to estimate which route is expected to see more traffic. Using these estimates, transport authorities can take appropriate measures to meet increase in ridership and possibly prevent congestion. This opens up a wide area of research and experimentation which poses need to have a framework for traffic management that can capture parameters of real-life behavior and provide an easy way to iterate upon and evaluate new ideas. In our work, we design a framework which provides modules to simulate: • a city with points of interests (house, office, school, shops etc). • human population and their daily activities. • temporally and geographically distributed social events with varied size of target audience. • a social network for humans to share their likes/dislikes with their friends and in turn influence their interest about simulated events. • a transport management system for humans transportation needs. It continuously monitors and plans train schedule to meet the needs of ridership. Our framework has a plug-and-play modular design; it supports easy integration and replacement of components. This makes it favorable for experimentation. We also emphasize on relevance of simulation parameters and design of modules with respect to how closely it mimics real-life. We also define metrics used to evaluate effectiveness of strategies in controlling congestion. To show the utility of the framework, we built a multi-agent simulation system and conducted exper- imental studies of the strategies developed. We simulated city of Singapore and its metro rail as means of public transportation. Singapore’s demographic data is easily available, geographical data available in form of OSM ([28]) is up-to-date, it has a robust public transportation system that is heavily used and its population is technologically advanced, hence social networking sites are massively used. As such, Singapore city is a fitting example to study and explain our work. We build our framework on top of DMASF ([52]), which is python-based and SQL-backed multi- agent simulation platform. Humans and transport management actors are modeled as agents. We present experimental studies to demonstrate utility and scalability of our framework, involving 100,000 humans. These experiments involve simulating social events. We found that our framework captures effect of social events which is seen as increased use of public transportation (trains). We also implemented few experimental strategies to estimate traffic flows in case of social events and strategies to control congestion. We found that for up-to medium scale events (i.e. for events involving up-to 1000 humans), our strategy performed well and prevented trains to be congested. But for higher number of attendees (approx 10,000), our strategy did not scale well. We also implemented a strategy in which human alters its trip based on state of ridership in trains and selects route which takes shortest total travel time to reach destination. We noted that there is slight improvement in waiting time and average total trip time for humans with this strategy. Results of these experiments revealed that traffic congestion can be curbed using social network data based near time forecasting. In this thesis, our focus is on design of simulation and component interfaces used in framework. We do not emphasize on any particular solution for congestion avoidance strategy. To show the utility of our system, we focus on trains and walking as means of transport. This work can be further extended to consider full multi-modal transport system having trains, buses and uber like taxis.

Abstract

In a task oriented domain, recognizing the intention of a speaker is important so that the conversation can proceed in the correct direction. This is possible only if there is a way to label the utterance with its proper intent. One such labeling technique is Dialog Act(DA) tagging. The main goal of this thesis is to build a Dialog Act tagger for the Telugu corpus. This work focuses on discussing various n-gram DA tagging techniques so as to tag the Telugu data. The n-gram DA tagging methods proposed earlier for English will not work for free word order languages like Telugu as English language follows strict subject–verb–object(SVO) syntax. This thesis explains in detail about the two DA tagging methods for tagging free word order languages preferentially Telugu. In this thesis, we propose a method to perform DA tag- ging for the Telugu corpus using advanced machine learning techniques combined with karaka dependency relation modifiers. The use of karaka dependencies for free word order languages like Telugu helps in ex- tracting the modifier-modified relationships between words or word clusters for an utterance. The modifier-modified relationships remain fixed even though the word order in an utterance changes. These extracted modifier-modified relationships appear similar to n-grams. Later, statistical machine learning methods are applied to predict DA for an utterance in a dialog. The first method uses n-gram karakas with back-off as n-gram language modeling technique at n-gram level and Memory Based Learning at utterance level. In the second method, we use syntactic features such as anaphora resolution, conjunct identification and using modifier modified relationship rules we automatically extract n-gram karakas. Then we apply language modeling (LM) with Hidden Markov Model (HMM) method for DA tagging. The proposed methods are compared with several baseline tagging algorithms. The results show that the proposed methods perform better DA tagging for free word order languages like Telugu.

Abstract

In the recent years there has been a continuous demand for increase in the power performance of the wireless electronic systems. This has been due to the tremendous increase in the data rate of the signal acquisition systems, thus resulting in huge power consumption at the RF transceiver and the A/D converter. Various data compression techniques have been used for quite some time to reduce power consumption. The recent theory of compressed sensing (CS) enables more efficient acquisition of signals at a rate much lower than the Nyquist rate. Further extension in the theory of CS has resulted in distributed compressed sensing (DCS), through which multiple signals can be acquired and reconstructed simultaneously. This brings about an increased compression efficiency, or in other words, the signal ensemble can be reconstructed with a fewer number of measurements when compared to a single channel CS. So, the need for low power signal compression circuits along with an efficient architecture for multichannel signal acquisition are the issues addressed here. In this work, a few low power hardware realizations of these data compression systems in analog domain before analog to digital conversion have been realized. Initially, a capacitor charge redistribution based multiply and accumulate (MAC) circuit capable of operating at very low power is introduced to perform evaluation of a linear equation. The application of this technique is the core contribution to the circuit level aspect of this work. Firstly, this circuit has been successfully utilized to realize a 2-D discrete cosine transform (DCT) completely on hardware in analog domain. The complete 8-point DCT architecture has been implemented in a 1.8 V, 0.18 μm digital CMOS technology. The performance of the implementation shows an average power consumption of 2.16 mW, a PSNR of 23.4 dB and the system occupies an active area of 0.0667 mm 2 . A completely digital implementation of the same system has been performed to compare the power consumption. It is observed that the proposed system utilizes only 1/5 th of the power of digital implementation. Secondly, a wireless capsule endoscopic system has been built on an embedded platform to evaluate the complexity of data compression of a multicamera scenario. Following that, an application specific integrated circuit (ASIC) implementation of a low power multichannel signal acquisition system based on the principle of distributed compressed sensing (DCS), thereby saving power and hardware complexity has been performed. The sensing operation has been realized in the charge domain using the mentioned switched capacitor technique based vector matrix multiplication (VMM) and thus consuming very low power. The technique has been tried upon two different signal ensembles, a) images sensed using CMOS imagers and b) real time neural or EEG signals. The respective systems have been implemented in a 1.8 V, 0.18 μm CMOS technology and is capable of sensing upto 64 EEG signal channels and 16 images simultaneously. The system performance has been tested with a set of EEG signals from practical neural recordings and the results show an average PSNR of 29.17 dB while sensing 64 channels at a compression ratio of 1/4, whereas the performance measures of the DCS imager system show a compression ratio of 1/4 with a power consumption of 36.8 mW per channel while sensing 16 channels simultaneously. The compressed analog signals in all of the above mentioned systems are digitized with an 8 bit ADC. The binary weighted capacitor (BWC) array based 8 bit SAR ADC has also been designed in the same technology targeting the specifications of these systems. The ADC is measured to operate with 7.97 effective number of bits (ENOB) and SINAD of 49 dB while consuming a power of 2.486 mW including the band gap reference (BGR) and associated buffer amplifiers. Finally, an ASIC consisting of a single channel CS based EEG acquisition system has been designed and fabricated which is capable of compressing sampled points in batches of 64 each while occupying an active silicon area of 1.25 x 0.85 mm 2 . In summary, a low power circuit to perform VMM in analog domain has been proposed and a few compression systems and architectures based on compressed sensing have been designed and implemented followed by a system on chip (SoC) realization.