Abstract

Barter was the original means of exchange and commerce in the olden days and was replaced by currency in the modern world. However, with the growth of ecommerce and the advent of the internet, online trade exchanges have sprouted. This has resulted in a spurt of online trading activity in the form of auctions, B2B and C2C barter. Hand-to-hand barter has given way to multifarious online trade exchanges such as BizXchange, BarterCard and Swap.com. Currently, one of the largest networks of online trade is BarterCard with over 50 million dollars of annual worldwide trade. In our work, we have explored a new and unstudied trade market which is a trust-based local, deadline-driven community. This trade market is explained below. Herein, the participants are members of a close-knit community such as a university hostel or a gated community. In a small social environment such as the ones mentioned, ordinary people are expected to have a variety of needs arising from time to time. Often, objects are required for short periods of time (a book to read), one-time use (redcolored shoes for a theme party) and the person is unwilling to buy new items for one-time use from the market. In such cases, the most common solution people opt for, is to borrow things from friends. We have explored and extended this trend to a larger community wherein close friends expand their barter circle to local acquaintances. Participants behave as ‘givers’ and ‘takers’ who exchange goods with each other over a period of time. The concept of ‘utility’ has been defined for both givers and takers in the following manner.

Abstract

Separation of images into its constituent components based on source of data, frequency distribution, or nature of data has been a widely used technique in the field of image processing and computer vision. Many problems are solved by partitioning images into components and working on each component separately. Common examples include breaking down of image into Red, Green and Blue channels/components for ease of representation or into Luminance and Chrominance for better compression. In this thesis, we explore the separation of natural images into appropriate components for the purpose of representation as well as recognition. We first introduce a framework where separation of images into direct and global components helps in modeling of 3D textures. These 3D textures are often described by parametric functions for each pixel, that models the variation in its appearance with respect to varying lighting direction. However, parametric models such as Polynomial Texture Maps(PTMs) tend to smoothen the changes in appearance. Therefore we propose a technique to effectively model natural material surfaces and their interactions with changing light conditions. We show that the direct and global components of an image have different characteristics, and when modeled separately, leads to a more accurate and compact model of the 3D surface texture. Direct component is mainly affected by structural properties of the surface and is therefore deals with phenomena like shadows and specularity, which are sharply varying functions. The global component is used to model overall luminance and color values, a smoothly varying function. For a given lighting position, both components are computed separately and combined to render a new image. This method models sharp shadows and specularities, while preserving the structural relief and surface color. Thus rendered image have enhanced photorealism as compared to images rendered by existing single pixel models such as PTMs. We then look at separating an image based on its sources of illumination or albedo variations for the purpose of scene text segmentation. Extracting text from scene images is a challenging task due to the variations in color, size, and font of the text and the results are often affected by complex backgrounds, different lighting conditions, shadows and reflections. A robust solution to this problem can significantly enhance the accuracy of scene text recognition algorithms leading to a variety of applications such as scene understanding, automatic localization and navigation, and image retrieval. We propose a method to extract and binarize text from images that contains complex background. We use Independent Component Analysis (ICA) to map out the text region, which is inherently uniform in nature, while removing shadows, specularity and reflections, which are included in the background. The technique identifies the text regions from the components extracted by ICA using a simple global thresholding method to isolate the foreground text. We show the results of our algorithm on some of the most complex word images from the ICDAR 2003 Robust Word Recognition Dataset and compare with previously reported methods.

Abstract

Biometrics have been established to be extremely reliable at the task of identifying individuals and thus are at the core of several real-world systems ranging from employee attendance to access control systems in the military. With growing computing resources available to individuals, biometric authentication systems are being deployed in even wider range of commercial applications. The permanent nature of biometrics raises serious security concerns with these deployments. Also, losing one's biometric trait can compromise that individual's identity in all the systems he is enrolled in. Biometrics are of non-rigid nature, requiring a fuzzy matching process, thus making it difficult to directly borrow popular security techniques used elsewhere with passwords and key-cards. Thus, the research interest received by this field attempts to develop efficient and reliable biometric authentication systems while addressing the issues of security and privacy. Binary biometric representations have been shown to provide significant improvement in efficiency without compromising the system performance for various modalities including fingerprints, palmprints and iris. Hence, this thesis is focused on developing secure and privacy preserving protocols for fixed-length binary biometric templates which use hamming distance as the dissimilarity measure. We propose a novel authentication protocol using a extit{somewhat} homomorphic encryption scheme that provides template protection and ability to use masks while computing the hamming distance. The protocol operates on encrypted data, providing complete biometric privacy to individuals trying to authenticate, only revealing the final matching score to the server. It allows real-time authentication and retains matching accuracy of the underlying representation as demonstrated by our experiments on iris and palmprints. We also propose a one-time biometric token based authentication protocol for widely used banking transactions. In the current scenario, the user is forced to trust the service provider with his sole banking credentials or credit card details for availing desired services. Often used one-time password based systems do provide additional transaction security, however the organizations using such systems are still incapable of differentiating between a genuine user trying to authenticate or an adversary with stolen credentials. Involving biometric security would certainly strengthen the authentication process. The proposed protocol upholds the requirements of secure authentication, template protection and revocability while providing user anonymity from the service provider. We demonstrate our system's security and performance using iris biometrics to authenticate individuals.

Abstract

An e-contract is an electronic version of the conventional contract and provides automated support for e-contracting. More formally, an e-contract is a contract specified, modeled and executed by a software system. Government (large organizations) contracts evolve due to changing context. Workflow management systems proposed for individual process simulations are restricted in their applicability to e-contracts because of their rigid pre-defined process definition and process execution frameworks. Current e-contract enactment systems lack context-awareness and face difficulties in supporting context based changes in workflow specification and execution procedures. Workflow management system needs necessary infrastructure to support contextual enactment of e-contract and exceptions handling that arise during enactment. Meta model based systems proposed provide a guided approach to conceptual modeling and facilitate the design of models for specific domains, such as e-governance, banking, and healthcare. However, most of the proposed meta models are not context based and only parametric driven template based meta-models. These models lack flexibility to adapt to changes to mini-world or run-time changes as well as the capabilities of modeling the exceptions. This necessitates context based meta-model driven approaches that should allow flexibility to suit the needs of modeling specific e-contracts. In this thesis work, we developed a context-aware e-contract enactment system for monitoring and enactment of government contracts. It consists of Context model for easier management of context information. Context model processes context data and provides context information during workflow specification and workflow execution. We develop context driven meta-models, which generates context-based meta execution workflows to drive the execution of e-contracts according to the current context information. Other major components of our system such as contract enactor, contract workflow, and workflow views also help in providing smooth enactment of e-contract by coordinating among themselves. As part of our case study, we have used the e-Government contract for modeling our context-aware e-contract system. We have implemented a prototype based on the architecture and consequently provided the implementation details of the system.

Abstract

Advancement in FPGA technology has enabled deployment of large complex FPGAs in the heart of modern high performance systems as compared to few years back when they were just used for glue lo gic, bridging applications. While custom IPs (Intellectual Property) both soft and hard are commonly used on FPGA to develop system designs, processor based systems are not commonly used or explored enough due to concerns about meeting a right trade -off between area usage, achievable performance, and the required design time. FPGA based designs are challenging as discussed in this thesis especially when the design sizes are big and performance expectations are high. Processor based systems on FPGAs can overcome these challenges if at all they can address the issue of low performance. This work showcases how to develop a multiprocessing system on FPGA using multiple light weight soft processors (LWP). These processors take very less resources, consume less power and are high in performance. They make use of abundantly available hard ened DSP48 blocks on the FPGAs to extract performance and also provide 2 nd level programmability to the designer. The processors can also work in conjunction with a custom hardware to achieve much higher system performance. As an example a TDEA (Triple Data Encryption Algorithm) cryptographic algorithm has been implemented on a multiprocessing system that uses 2.5 x lesser area, is 40% higher in performance, and requires 20% less er power as compared to equivalent solution implemented using a commercial soft processor.

Abstract

Problem of spectrum scarcity has not only affected cellular communication bands but is continuously pushing freely available ISM bands to its limits. Devices which work in ISM band were developed without the consideration of co-existence and interoperability. Proliferation of cheap wireless devices and systems utilizing the ISM band is creating spectrum scarcity in the band which is nonetheless severe compared to cellular communication spectrum scarcity. WSN is one of the systems whose performance is being severely affected by other ISM band systems such as Wi-Fi, Bluetooth etc. Concept of cognitive radio has been applied to WSN in order to opportunistically utilize the freely available licensed bands. This gave origin to cognitive radio based wireless sensor networks (CRWSN). But, existing cognitive radio algorithms such as spectrum sensing, spectrum prediction and spectrum monitoring etc. cannot be applied to CRWSN in their existing forms because of the inherent limitations of CRWSN such as limited battery life, less computational power and implementation issues. In this thesis, we address three problems (i) Efficient Spectrum Sensing Technique for CRWSN (ii) Real Time Spectrum Monitoring technique for CRWSN & (iii) Testbed Development for CRWSN In first part of the thesis, we present an energy and time efficient method of spectrum sensing technique for CRWSN using doubly cognitive architecture (DCA). DCA is based prediction followed by sensing. It predicts not only with respect to time but space also. Hence for CRWSN, which can be highly mobile in nature, DCA is well suited for the task of spectrum sensing. Apart from predicting the primary user spectrum usage pattern, DCA assigns the order of spectrum sensing in case multiple channels are required to be sensed for their vacancy and channel characteristics. We, further enhanced the DCA by adaptive FFT resizing to make it faster and more energy efficient. Adaptive FFT resizing assigns proportionate FFT points to the channels in accordance with their probability of vacancy, while performing the spectrum sensing operation. Our experiments on the CRWSN testbed show that DCA is more efficient with 42% and 19% of average normal spectrum discovery time. In the second part of the thesis, we present a novel method to detect the reappearance of primary user in real time. This method senses a part of the bandwidth of interest in order to capture the primary user reappearance immediately without any significant lag compared to contemporary state of the art methods. Contemporary spectrum monitoring methods suffer from real time detection requirement, unreliable prediction and inefficient bandwidth utilization. Our proposed method of partial sensing based spectrum monitoring successfully addresses all these issues. Additionally, our method is computationally simpler and does not require any additional hardware or software add-on in the existing system in order to deploy it in real time. Our experiments on the CRWSN testbed show that partial sensing-based spectrum monitoring outperforms periodic spectrum monitoring with average PU detection time (3sec.) and variance (1.85), which are significantly reduced to 0.27 and 0.12 times the average of 11 seconds and variance of 15.42 of periodic spectrum monitoring. Time-bandwidth-product of partial spectrum monitoring is found to be 50% more than periodic spectrum monitoring leading to higher bandwidth efficiency.

Abstract

Structural damage during recent earthquakes in India like in Bhuj, Chamoli, Koyna, Uttarkashi, Killari and Jabalpur demonstrate the need for developing a comprehensive model for seismic risk assessment. The Bhuj earthquake clearly demonstrates that the vast extent of damage and the consequent loss of life associated with these events are due to poor construction practices. According to the Indian Seismic Code IS: 1893-2007, about 60% of India’s land area falls under the threat of moderate-to-severe earthquakes. Also according to Census 2011, the number of houses exposed to such high hazards is almost 80%. Many cities in India fall under the high seismic zones and have huge population and also there is a trend of increasing due to lack of employment opportunities in rural areas. This lead to uneven distribution of population across the country. Many people in these areas live in low to high rise building. Unfortunately these existing buildings are not earthquake resistant, and they did not follow the existing building code. This is because of poor construction practices and lack of awareness about earthquakes. These buildings are currently operational and need to be assessed and upgraded to minimize seismic damage and improve life safety for future earthquakes. As a case study, Nanded Waghala, which is the second largest city in the Marathwada region of Maharashtra after Aurangabad was chosen. The city is the largest urban centre and the administrative headquarters of the Nanded district. It is known as a holy place for the Sikh faith and it is situated on north bank of the river Godavari. According to 2011 Census it has a population of 5,50,564. This city falls under seismic zone-II (IS 1893-2002) in Penninsular India (stable continental region). This city is in the safe zone but close to Latur and Jabalpur. The earthquakes in Lature (1993) and Jabalpur (1997) caused a lot of damage in the past. Many of the towns in the state have a number of recorded earthquakes in the last 200 years (records available from 1800 onwards). However the major urban centers that suffered more than 2 earthquakes in the last 200 years are Latur, Jabalpur, Pune, Mumbai, Marathwada, and Koyna areas. Some of the major earthquakes that occurred around Nanded are Parsipada-Kaa Khurd earthquake of 1935(Ms 5.0), Bhusawal-Sawada earthquake of 1938 (Mw 6.3), Mahad-Goregaon earthquake 1967(Mw 5.6), Koyna Earthquake 1967(Mw 7.0), Latur earthquake 1993 (Mw 6.1) and Jabalpur earthquake1997 (Mw=6). Apart from these earthquakes, a series of minor tremors were felt in south-central Maharashtra, in the town of Nanded from 13 November 2006 and until 2010. The strongest tremors were felt on 31 March 2007, 12 November 2007 and 14 December 2007 causing widespread panic. Over 500 people have felt the tremors since late 2006. Since the first tremors, brontides (natural explosive sounds) have been heard in the town of Nanded with or without being accompanied by felt tremors. Minor damage and a few injuries were reported as a result of these tremors. In view of these events, it is very essential to realistically x estimate the earthquake hazard associated with this shield region and also develop a seismic risk model to help in identifying the vulnerable areas and population groups that will require the most assistance in the aftermath of a damaging earthquake. In order to find out the potential risk to housing for this city, it is necessary to evaluate the Hazard (H), Exposure (E) and Vulnerability (V). Over the last thirty years, several seismic risk assessment studies have been carried out around the world but the type of method chosen depends on the objective of the assessment and the availability of data. This thesis addresses a new approach for studying the seismic risk methodology and it has been implemented in the GIS environment for expected earthquake scenarios in the future the city of Nanded. The main objective of this study is to estimate the casualty and injuries that may be caused by future earthquakes in Nanded city and this is very useful for policymaking and the preparation of disaster management plans. These results are shown in the GIS environment at the ward level. In this thesis, three expected earthquake scenario have been generated using synthetic ground motion and Probabilistic Seismic Hazard Analysis (PSHA). Data has been obtained from the Municipal Corporation and given in terms of ward wise building stock, and the building typology and construction practices were identified through a field investigation. In this study, two typical building types have been considered i.e., Reinforced concrete and Brick Masonry buildings and other typologies were not included because of numerical limitation. Fragility curves of each building typology have been developed using Applied Element Method (AEM). These fragility curves are not available for the Indian condition, so our own

Abstract

Optical Character Recognition (OCR) problems are often formulated as isolated character (symbol) classification task followed by a post-classification stage (which contains modules like UNICODE generation, error correction etc. ) to generate the textual representation, for most of the Indian scripts. Such approaches are prone to failures due to (i) difficulties in designing reliable word-to-symbol segmentation module that can robustly work in presence of degraded (cut/fused) images and (ii) converting the outputs of the classifiers to a valid sequence of UNICODES. In this work, we look at two important aspects of word recognition -- word image to text string conversion and error detection and correction in words represented as UNICODES. In this thesis, we propose a formulation, where the expectations on the two critical modules of a traditional OCR (i.e, segmentation and isolated character recognition) is minimized. And the harder recognition task is modelled as learning of an appropriate sequence to sequence transcription scheme. We thus formulate the recognition as a direct transcription problem. Given many examples of feature sequences and their corresponding UNICODE representations, our objective is to learn a mapping which can convert a word directly into a UNICODE sequence. This formulation has multiple practical advantages: (i) This reduces the number of classes significantly for the Indian scripts. (ii) It removes the need for a word-to-symbol segmentation. (ii) It does not require strong annotation of symbols to design the classifiers, and (iii) It directly generates a valid sequence of UNICODES. We test our method on more than 5000 pages of printed documents for multiple languages. We design a script independent, segmentation free architecture which works well for 7 Indian scripts. Our method is compared against other state-of-the-art OCR systems and evaluated using a large corpora. Second contribution of this thesis is in investigating the possibility of error detection and correction in highly inflectional languages. We take Malayalam and Telugu as the examples. Error detection in OCR output using dictionaries and statistical language models (SLMs) have become common practice for some time now, while designing post-processors. Multiple strategies have been used successfully in English to achieve this. However, this has not yet translated towards improving error detection performance in many inflectional languages, especially Indian languages. Challenges such as large unique word list, lack of linguistic resources, lack of reliable language models, etc. are some of the reasons for this. In this thesis, we investigate the major challenges in developing error detection techniques for highly inflectional Indian languages. We compare and contrast several attributes of English with inflectional languages such as Telugu and Malayalam. We make observations by analysing statistics computed from popular corpora and relate these observations to the error detection schemes. We propose a method which can detect errors for Telugu and Malayalam, with an F-Score comparable to some of the less inflectional languages like Hindi. Our method learns from the error patterns and SLMs.

Abstract

Online advertising is evolved as a major form of advertising in this century. It uses internet as a medium to provide advertisements to consumers. The major problem in online advertising is to provide advertisements to relevant set of users. Sponsored search, contextual advertising, behavioral targeting and banner advertising are different modes of online advertising. Banner advertising is one of the important mode of online advertising. The three major entities involved in banner advertising are advertiser, publisher and visitor. Advertiser is interested in endorsing his products through banner advertisements. Publisher manages a website by selling the advertisement space to multiple advertisers. Visitors visit web pages of their interest containing banner advertisements. The aim of an advertiser is to spread his advertisement to a certain percentage of relevant visitors. On the other hand, to generate more revenue for a given website publisher has to manage coverage demands of multiple advertisers by providing appropriate sets of relevant web pages. The major issues in banner advertising are efficient auction system to sell advertisement space, scheduling banner advertisements on a web page for maximizing the revenue, pricing models to be followed for banner advertisements, targeted banner advertisements based on the user behavior, matching banner advertisements with the web pages, allocating relevant sets of web pages to multiple advertisers with corresponding coverage demands and finding appropriate set of users interested in particular content of web pages. In this thesis, we focus on extracting relevant sets of web pages for efficient placement of banner advertisements based on the click-through data of a website and key words describing every web page assuming similar visitors behaviour. The following two factors are important in placing banner advertisements on web pages of a website. a) Percentage of users visiting a web page. b) Relevance of banner advertisement to the content of web page. In the literature, model of coverage patterns and algorithms to mine coverage patterns from transactional data are proposed. The usefulness of these patterns is demonstrated by applying it to banner advertisement placement problem. For a given website, coverage pattern is a set of web pages visited by certain percentage of visitors. Publisher can extract these patterns from the click-through data of a website to meet the demands of multiple advertisers. However, the model of coverage patterns does not consider the relevance of web pages to the advertisement. This may lead to placing banner advertisement on irrelevant web pages. In this thesis, we propose a model of content-specific coverage patterns to capture the relevance of advertisement to web pages along with the percentage of visitors. In general a web page contains content related to multiple topics and different users visit the web page with varied topics of interest. The research issue here is to find the percentage of users interested in particular content of web pages of the pattern. In this thesis, we propose a notion of topic coverage which captures the fraction of visitors interested in particular topic/keyword of web pages in the pattern. If every web page is labelled with all the keywords relevant to the content of web page, topic coverage of every keyword can be computed. As the coverage patterns are extracted based only on the percentage of visitors, most of them are irrelevant to the advertiser. The research issue is to extract the patterns of web pages with certain percentage of visitors and are relevant to the advertiser. In this thesis, we propose the notion of content-specific coverage patterns which defines the set of web pages visited by certain percentage of users interested in particular content of the web pages. We also propose the methodology to extract content-specific coverage patterns from the click-through data given keywords describing every web page. Experimental results on real world datasets show that the proposed model of content-specific coverage patterns extracts relevant set of patterns efficiently over the model of coverage patterns. The results also show that the proposed approach generates all the patterns relevant to the topics given by the advertiser while the model of coverage patterns generates some irrelevant patterns. Finally, we conclude that by bidding for slots on the web pages of content-specific coverage patterns, advertisers will have relevant set of expected number of visitors.

Abstract

The computing industry has undergone several paradigm shifts in the last few decades. Fueled by the need of faster computing, larger data and real time processing needs parallel computing has emerged as one of the dominant paradigms. Motivated by the success achieved in distributed computing models and the limitations faced by single core processors, parallel computing is the only alternative for building faster computers. Parallel computing is one of the most challenging areas computer science in the present and developing algorithms and optimization techniques for utilizing the processing power present in a current generation parallel computer is still a very exciting area for research. The parallel computing industry underwent a massive shift with the conventional sequential computers hitting the power wall. It led to the development of multicore and many-core computing chips that had multiple sequential computing cores packed into a single chip. The immediate impact was the need for (re)designing sequential algorithms in order to utilize the computing power of such chips. Combined with the intricate memory and cache structures, parallel algorithms require a higher degree of engineering for the most optimal performance. The many-core revolution started with the release of Graphics Processing Units (GPU) which had a large number of compute cores and offered massive parallelism. With the evolution of the many-core chips, the GPUs found application in graphics, gaming as well as general purpose computation. In the same time frame, the Central Processing Units (CPU) too under went a sea of innovation and emerged as more powerful and mature computing machines. However, the multicore CPUs were mostly ignored in its initial days. With the advancement of accelerator platforms, the CPUs and GPUs are now able to communicate in a more efficient manner. In the recent times there has been quite a few works such as the ones in [79, 91, 43] that shows that hybrid algorithms actually provide better performance and efficiency over conventional accelerator based computing. In this thesis we work towards the development of hybrid multicore computing. Hybrid multicore computing is developing algorithms and optimization strategies for popular computing primitives on an hybrid platform. A hybrid platform is one which contains two or more multicore or many-core devices. There are several challenges towards the efficient algorithm design on hybrid platforms such as that of communication bottlenecks, load balance and synchronization. In this thesis we work towards developing algorithms for some computing primitives such as that of list ranking, sorting and pseudorandomness and some graph algorithms. We experiment on a hybrid platform consisting of a 6-core Intel CPU and Nvidia GPUs of broadly two generations. In our first work we work towards the development of hybrid algorithms for List Ranking. To this end, we explore the algorithmic and analytical issues in hybrid multicore computing. Our case studies involve two different ways of designing hybrid multicore algorithms. The main contribution of this work is to address the issues related to the design of hybrid solutions. We show our hybrid algorithm for list ranking is faster by 50% compared to the best known implementation [139]. This work is followed by a hybrid implementation of comparison sorting. Sorting has been a topic of immense research value since the inception of Computer Science. In this work, we present a hybrid comparison based sorting algorithm which utilizes a many-core GPU and a multi- core CPU to perform sorting. The algorithm is broadly based on splitting the input list according to a large number of splitters followed by creating independent sublists. Sorting the independent sublists results in sorting the entire original list. On a hybrid platform, our algorithm achieves a 20% gain over the current best known comparison sort result that was published by Davidson et. al. [32]. On the above experimental platform, our results are better by 40% on average over a similar GPU-alone algorithm proposed by Leischner et. al. [81]. Our results also show that our algorithm and its implementation scale with the size of the input. We also show that such performance gains can be obtained on other hybrid platforms. The use of many-core architectures and accelerators, such as GPUs, with good programmability has allowed them to be deployed for vital computational work. The ability to use randomness in computation is known to help in several situations. For such computations to be made possible on a general purpose computer, a source of randomness, or in general a pseudo random generator (PRNG), is essential. However, most of the PRNGs currently available on GPUs suffer from some basic drawbacks. It is of high interest to develop a parallel, quality PRNG that also works in an on demand model. In this work, we investigate a hybrid technique to crea