Abstract

Today, our daily lives are constantly driven and influenced by services like social networking, personalized advertisements, cloud infrastructure etc. This makes any form of personal or professional data vulnerable to both security and privacy threats. User looses control over the data as soon as its published on the Internet. Recently, popular photo sharing service Instagram tried to change its privacy policy, giving itself the right to sell users’ information including their photographs to advertisers without any notification or compensation. With incidents like AOL and Netflix debacle, organizations are refraining from releasing customer data even after anonymization. This hinders future research and developments in many ways due to unavailability of customer data, behavior and patterns. Techniques like k-anonymity and l-diversity help to preserve user privacy to some extent but fails to provide any solid guarantees. Recently proposed, differential privacy provides promising results in this area with theoretical bounds on information leak and preservation of privacy even against the auxiliary information. However, differential privacy considers individual’s record independent of other data and can not be applied to linked data like social graph, time series etc. Furthermore, all these techniques compromise utility of the data while maintaining privacy. At present, two approaches are widely used to ensure security of the data. First one is based on SecureMultiparty Computations (SMC), where users communicate with each other using SMC protocol to securely evaluate any function on their data. SMC gives provable security without compromising utility of the data. However, the solutions based on the general protocol of SMC requires enormous computational and communication overhead, thus limiting the practical deployment of the secure algorithms. The second approach is to encrypt the data at the user end and perform any operations in the encrypted domain to preserve the confidentiality of the data. This leads to difficulty in performing various operations like search, retrieval and computations. Homomorphic encryption allows secure computations over encrypted data but its impractical due to high computational cost. In this thesis, we focus on developing privacy preserving, communication and computationally efficient algorithms in the domain of Data Mining and Information Retrieval. Specifically, we design efficient privacy preserving solutions for two widely used tasks - outlier detection and content based similarity search over encrypted data. Private computation of outliers among data collected from different sources has many applications in the area of data mining. First, we propose a novel algorithm of distance based outlier detection using Locality Sensitive Hashing (LSH) in a distributed setting where data is horizontally partitioned among data owners. We show that the proposed algorithm is scalable in case of large datasets with high dimensionality. Then, we extend our distributed outlier algorithm to propose an algorithm for private outlier detection that broke the previous known bounds of quadratic cost. We compare our algorithm with the state of the art technique and show that our algorithm is better both in terms of computational as well as communication complexity. Next, we explore the properties of hierarchical index structures and propose an algorithm for content based similarity search over encrypted data that do not reveal user query to the server. To the best of our knowledge, we are the first one to propose a definition and a scheme for the problem of Content Similarity Searchable Symmetric Encryption (CS-SSE). Finally, we extend our CS-SSE scheme for Private Content Based Image Retrieval, which is essential for many applications like searching health records using CT scans and patent search for logos. We also show that our algorithm achieves optimal computational cost with similar accuracy and privacy when compared to the existing techniques.

Abstract

E-commerce, buying and selling of products by electronic means, has become popular due to the emergence of World Wide Web. One of the vital components of e-commerce systems is recommender systems (RSs). The RS is employed as a part of e-commerce system to help users in finding products of their interest from a huge number of available products. The Collaborative filtering (CF) approach is one of the popular approaches employed to build recommender systems. The neighborhood formation is one of the key steps in collaborative filtering and influences the performance of recommender systems. In this thesis, we have made an effort to improve the performance of recommender systems by proposing two improved neighborhood formation methods. At first, we have extended the notion of lower-bound similarity to improve the performance of neighborhood formation in CF-based recommender system. For neighborhood formation, k-nearest neighbor (kNN) approach is followed to find k neighbors of a target user. Given a fixed k value, the approach finds k nearest neighbors using different similarity methods. We identified the following issue with the kNN approach. Due to fixed value of k, the users who have rated few products may get less-similar neighbors and the users who have rated more products may miss the genuine neighbors. In the literature, the notion of lower-bound similarity has been proposed as an alternative to the popular k-means approach to improve the clustering performance in which the clusters are extracted by fixing the similarity threshold. By extending the notion of lower-bound similarity, we have proposed a neighborhood formation approach by fixing the similarity threshold instead of k. With this approach, it was proposed that it is possible to get appropriate number of neighbors of a target user. The experimental results on real-world dataset, show that the proposed approach improves the performance over the existing kNN-CF approach.

Abstract

Cloud Computing is the technology that enables users to host their applications or subscribe to computing resources on remote servers in a pay-as-you-go model. The users access these applications and computing resources in the form of web services. These services offered by the Cloud providers can be broadly classified as: Software-as-a-Service (SaaS), Platform-as-a-Service (PaaS) and Infrastructureas- a-service (IaaS). The pricing models for different types of services vary from provider to provider. With massive improvement in the internet connectivity in recent years, many users and enterprises are favouring these kind of services as they save a lot of infrastructure and maintenance cost. MapReduce framework has received a wide acclaim over the past few years for large scale computing. It has become a standard paradigm for batch oriented workloads. It is usually run on large number of physical machines called as ‘nodes’ which are collectively termed as ‘cluster’. MapReduce framework suits very well to develop applications that can rapidly process huge amount of data in a distributed fashion over large clusters. This framework is widely used in the industry to analyse log files, index files, crawl the web, social media monitoring, data mining etc. MapReduce is fairly simple framework which only takes the code that needs to be executed and the data to be processed as input, while the rest of the processes is handled transparently from the user. Though there are many distributed paradigms, MapReduce has seen a wider scope in industry and academia because of its simplicity. It works on a simple master-slave architecture, where the jobs are submitted to the master, which divides them into smaller units and schedules them across the cluster. MapReduce is mostly used to run data intensive jobs which are usually very long and sometimes even run from days to months. Since the jobs may be very long, intelligent scheduling decisions help in reducing the overall runtime of the jobs. Given the scale at which the MapReduce applications work, reducing the overall runtime would have a direct impact on minimizing power consumption of the cluster. Since the cluster is comprised of heterogeneous commodity hardware, the scheduler has to face another challenge of scheduling tasks effectively on a limited diverse resource pool. The first problem that we address in this thesis is: Reduce the overall runtime of MapReduce jobs by intelligent scheduling. We propose an approach which tries to maintain harmony among the jobs running on the cluster, and in turn decrease their runtime. In our model, the scheduler is made aware of different types of jobs running on the cluster. The scheduler tries to allocate a task on a node if the incoming task does not affect the tasks already running on that node. From the list of available pending tasks, our algorithm selects the one that is most compatible with the tasks already running on that node. We bring up heuristic and machine learning based solutions to our approach and try to maintain a resource balance on the cluster by not overloading any of the nodes, thereby reducing the overall runtime of the jobs. We evaluate our algorithm on a variety of workloads and our results show that the proposed algorithm achieves substantial savings in runtime of the jobs when compared to Yahoo!’s Capacity scheduler. Our approach takes into account of the interoperability of MapReduce tasks running on a node of the cluster and ensures that a task running on a node would not affect the performance of other tasks. This requires the scheduler to be aware of the resource usage information of each task running on the cluster. The second problem that we address in this thesis is: Energy efficient and SLA aware scheduling of virtual machines in a data center. We propose algorithms which try to minimize the energy consumption in the data center duly maintaining the level of service that is formally agreed between the service provider and the user, termed as Service-Level Agreement (SLA). The algorithms try to utilize least number of physical machines in the data center by dynamically rebalancing the virtual machines based on their utilization. The algorithms also perform an optimal consolidation of virtual machines on a physical machine minimizing SLA violations. Our algorithms make sure that the physical machines are utilized to the maximum extent and put the low utilized physical machines to standby mode, by intelligently migrating the load on to other physical machines. In this part of work, we try to utilize least number of physical machines in the data center, there-by conserving energy. The virtual machines are consolidated on a physical machine based on the resource usage patterns in order to avoid any race condition for resources. To achieve close to perfect consolidation we follow a similarity model and the virtual machines are consolidated based on this similari

Abstract

The need for low power integrated circuits is well known because of their extensive use in the electronic portable equipments. On chip SRAMs (Static Random Access Memory) determine the power dissipation of SoCs (System on Chips) in addition to its speed of operation. Hence it is very important to have energy efficient SRAMs. This Thesis proposes energy efficient SRAM cells (6T and 5T) based on adiabatic principles and design modifications. Bulk of the energy in SRAMs is wasted during charging of the bit lines and discharging it to the ground during read and write operations. It is proposed to use adiabatic approach to collect this energy and recycle it. Based on this thought process a separate and simple adiabatic driver circuit has been designed and used for bit line charging. It is shown that in 6T SRAM, a total energy of the order of 50% over a given period and around 80% during write cycle can be saved by the help of this driver. With this adiabatic driver circuit working in conjunction with conventional 6T SRAM cell other performance characteristics like read stability, write ability, read and write delay etc have been found by simulation in addition to energy saving under varied conditions of memory operations. The effect of device parameters of the driver on total energy of the SRAM cell has been investigated. Further studies covered proposed SRAM cell arrays. With a view to increase energy saving further, the possibility of having adiabatic SRAM with single bit line for reading and writing is examined. This architecture improves the total energy saving further (90%). Feat SRAM is designed to get better speed of operation along with energy saving. All these investigations have been carried out by simulations using HSPICE with 65nm PTM models and JUN-CAP1 level 4 for diodes. Thus the thesis describes the investigations that are carried out to arrive at energy efficient adiabatic SRAM cells.

Abstract

Molecular dynamics simulations of water permeation through multi-walled nanochannel is an important topic of reasearch in nanotechnology. Carbon nanotubes (CNT) are molecular-scale carbon fibres with a graphitic structure. They have significant mechanical, electrical and chemical propeties and have applications in nanotube based biosensors. The study of dynamics of water permeation across nanochannels has applications in feilds related to nanofluidic devices. In the present work, we have carried out molecular dynamics simulations to study the effect of external structure on water permeation across a Double-Walled Carbon Nanotube. Six different types of systems were prepared by altering its external structure. Remarkbly, it was found that the ratio of maximal flux to minimal flux varies by a factor of 2 for two different structures. It was understood that if more number of water molecules surround the carbon nanotube more will be the flux. This is attributed to interactions between the water molecules that are inside and outside the channel. Further, it was understood that the water molecules outside the region of nanopore, are driven along by the water flowing inside the tube, which affects the movement of the water inside. These findings are helpful in designing of high flux nanochannels. The behaviour of water molecule inside the nanochannel is studied with the the parameters like orientation of water molecule with nanotube axis, energy of water molecule traversing from bottom to top and top to bottom and probability distribution of water molecule with time spent inside the nanotube. It is observed that water dipole flips continously and the average energy remins same when it is traversing through the open channel in both the directions. It was observed that water molecules are well ordered inside the nanotube and two molecules will not possess the same average value of energy while traversing inside the nanotube.

Abstract

With the development of computer technology, storage has become more affordable. So, all traditional libraries are making their collections electronically available on internet or digital media. To search in these collections, better indexing structure is needed. It can be done manually or automatically. But manual indexing is time consuming and expensive. So, automation is the only feasible option. First approach in this direction was to convert document images into text by OCR and then perform traditional search. This method works well for European languages whose optical character recognizers (OCRs) are robust but did not work reliably for Indian and non-European languages like Hindi, Telugu and Malayalam etc. Even for European languages, OCRs are not available in the case of highly degraded document images. To overcome limitations of OCR, word spotting was emerged as an alternative. In word spotting, given word image is represented as features and matching is done based on feature distance. Main challenges in word spotting are extraction of proper features and feature comparison mechanism. Profile feature is one of the popular ways to represent word image and Euclidean distance is used for comparison. To overcome word length, all images are scaled to same size, due to which lots of information is lost. Later, DTW based approach was proposed for matching which does not require scaling of images. The problem with DTW based approach is that it is very slow and can not be used for practical and large scale application. In first part of this thesis, we explain a Bag of Visual Words (BoVW) based approach to retrieve similar word images from a large database, efficiently and accurately. We show that a text retrieval system can be adapted to build a word image retrieval solution. This helps in achieving scalability. We demonstrate the method on more than 1 Million word images with a sub-second retrieval time. We validate the method on four Indian languages, and report a mean average precision of more than 0.75. We represent the word image as histogram of visual words present in the image. Visual words are quantized representation of local regions, and for this work, SIFT descriptors at interest points are used as feature vectors. To address the lack of spatial structure in the BoVW representation, we re-rank the retrieved list. %This significantly improves the performance. This provides significant improvement in the performance. Later, we have also performed enhancements over BoVW approach. Enhancements are in terms of query expansion, text query support and Locality constrained Linear Coding (LLC) based retrieval system. In query expansion, we have used initial results to modify our initial query and obtained better results. In BoVW model, query is given by example but users are generally interested in query as text like ``Google'', ``Bing'' etc. Text query is also supported by same model as BoVW. Later, LLC is used to achieve high recall. LLC scheme learns a data representation using nearest codeword and achieves improvement over performance. In most of the scalable document search, features like SIFT, SURF are used. These are originally designed for natural images. Natural images have lots of variation and extra information in terms of gray images. Document images are binary images, so need features which can be specifically designed for them. We have proposed patch based features using profile features. We have compared our proposed feature with SIFT and obtained similar performance. Our feature has advantage that it is faster to compute compared to SIFT, which makes our pre-processing step very fast. We have demonstrated that recognition free approach is feasible for large scale word image retrieval. In future work, similar approach can be used for hand written, camera based retrieval and natural scene text retrieval etc. Also, a better and efficient descriptor is needed specifically designed for document words.

Abstract

With the advent of high performance (in terms of speed, power and area) digital circuits, the need for data converters with high accuracy and speed for various kinds of applications, has attracted the attention of scientists and technologists all over the world. Constant efforts are being put in to miniaturize the data converters from the point of low power and less area. The existing literature indicates that there is a need to have a very highly stabilized power supply for data converters to achieve these goals. It is really difficult to achieve a global power supply with high stability (temperature stability of the order of few ppms/‰ and voltage stability of few parts in ten thousands). In view of this, an attempt has been made to develop a digital to analog converter (DAC) integrated with a highly stabilized power supply. The whole architecture may be operated with a power supply of poorer quality. Literature survey on DACs has indicated that segmented architectures can reduce the need for having large variations in the widths of current source transistors. The current steering DAC architectures help in keeping the load current (i.e. current drawn by the DAC) constant, and in achieving a higher speed of operation. The power drawn can be minimized by choosing a low value of current for LSB. Keeping these considerations in view, an 8-bit segmented current steering DAC has been attempted. The DAC has been divided into two segments of 4-bits each. One segment caters to lower 4-bits of input digital word and the other segment caters to higher 4-bits. This methodology has resulted in a maximum required ratio of widths of transistors to be 8, in each segment. This ratio can perhaps be achieved in any technology with reasonable accuracy. The technology used in the design of this DAC is UMC 0.18 µm CMOS. In this, it has been possible to achieve a reasonable accuracy with a LSB current of 2 µA. This has resulted in low power operation of the DAC. With these considerations, a design for current steering DAC has been arrived at and simulated using Synopsys H-Spice. It has been found that this DAC needs a power supply of 1.8 V with a stability of ±1 mV to result in a change of less than 1 µA (less than 0.5 LSB) at the output of the DAC. Further, the current that is to be supplied is about 1.78 mA. This has led to the specifications of the power supply to be integrated with the DAC. The supply voltage for this power supply has been chosen to be 5 V. This would enable the development of a proper voltage reference of the required quality and the interface circuit that may be needed between the reference and the DAC. Literature reveals that it is the bandgap reference which yields good temperature and voltage stability. A detailed study has revealed that the conventional bandgap reference circuits generally give a voltage reference of about 1.2 V with a temperature stability of around 25-50 ppm/‰. In view of this, bandgap reference has been modified, incorporating additional elements to provide a feedback from the output to the input which leads to higher stability. The proposed voltage reference has been found to give temperature stability of the order of 1 ppm/‰. The voltage stability is near about 0.02% of supply voltage. Further, it has been found possible to vary the output voltage of voltage reference from a low value of 0.7 V to 2.6 V. It has also been possible to reduce the lower end from 0.7 V to 0.3 V by replacing the silicon junction diodes with schottky diodes. A source follower has been used to isolate the DAC from the reference and provide the required amount of current for DAC. The DAC and the power supply have been integrated and the INL, DNL of the DAC are found to be within ±0.5 LSB and ±0.8 LSB respectively. The maximum speed of operation of the DAC is 500 MHz with a power consumption of about 13 mW . This thesis indicates the effort put in to visualize and realize the 8-bit DAC with integrated power supply. The thesis has been organized into 6 chapters.

Abstract

Risk to manmade structures due to seismically induced ground deformation has been evident from past earthquakes. Influence of site effects on strong ground motions has been ascertained by many seismologists and earthquake engineers. Mechanisms related to the local soil and rock properties have the capacity to influence ground motions. Depending on the ground characteristics, the ground shaking is influenced, which may result in the amplification (causing resonance) or attenuation. Amplification mechanisms control the frequency content of ground motions. Though direct waves were used for the study of ground motion, source, path and site characterization were recognised as the prime factors that affect earthquake ground motion. Nonlinear amplification at soft deposits sites are more pervasive than seismologists perceived. Site effects are also causative of Liquefaction. Liquefaction is a phenomenon in which the strength and stiffness of a soil is reduced by earthquake shaking or other rapid loading. Liquefaction and related phenomena have been responsible for tremendous amount of damage in historical earthquakes around the world (Borcherdt, R.D., 1991; Dobry, R., 1981). Soil failure due to liquefaction may trigger landslides, lateral spreading, or large ground settlement. Hence, estimation of site effects could be consequential in assessment of the sesmic hazard of an area. Seismic hazard assessment studies are based on seismic characterization of the site and ground response analysis. Geographical statistics of India show that almost 60% of the land is vulnerable to earthquakes of MSK intensity VII or more. Macro zoning of the country offers a very vague idea of the earthquake hazard in any particular region due to insufficient historical database of the earthquakes. In this study, Vijayawada city (16.52°N Latitude 80.62°E Longitude) which falls in zone III (IS 1893: 2002) has been considered for detailed seismic study. Listed as the 34th largest town in India (population wise), and the 3rd largest town in Andhra Pradesh, Vijayawada is one of the important urban agglomeration and a major business centre. The city is located on the banks of Krishna which accounts for the presence of large amounts of alluvium and also it is characterised by low range hills of Eastern Ghats. About 26 seismic sources are located within 300km radius of the city out of which few are active. Though there has been no evidence of earthquakes but far field effects were prevalent during major earthquakes that occurred near the coast and in peninsular India (1969, 2001, 2008, 2009 and 2010). Frequent tremors (19th July, 11th April and 26th January) were observed in this year (2012) which is instinctive of a probable seismic event in near future. Geotechnical characterisation of the site has been instigated with the collection of large amount of borehole data from different sources. Using the data 1D and 2D soil profiles were generated. The predominant soil in the northern, eastern, western and southern part of the city has been identified. Due to the lack of deep boreholes, the bedrock depth could not be known but traces of rock encountered in the collected data suggest rock outcrops in this region. Water table levels were also collected and least water table has been mapped. Grain size distribution curves have been developed to understand the particle size distribution of the alluvium present. These curves were further used for preliminary assessment of liquefiable areas. From geotechnical characterisation, it has been observed that the soil profile in the city is dominated by silty clay, especially in western region. Eastern and southern parts of city consist (apart from silty clay) of seams of clayey sand; sandy silt is present in the top 5m and is occupied by silty sand in the latter layers. Northern region of the city consists of silty clay and silty sand. Ground response analysis has been carried out both by instrumental and experimental methods. For estimating peak ground acceleration DEEPSOIL (Hashash, Y.M.A. et al., 2011) has been used. With soil layer depth, bulk density, shear wave velocities (obtained from attenuation relationship) and damping as inputs, peak ground acceleration by equivalent linear analysis has been estimated. PGA map at surface level has been developed for the city. The PGA map developed is useful for the analysis for liquefaction potential. The identification of peak frequency of ground has been done using microtremor (MR2002-CE) testing at 74 locations. Microtremor is one of the recent advances in geophysical survey techniques. Analysis has been done at all test sites using microtremor records and predominant frequency and H/V amplitude map were generated which reflect the fundamental characteristics of possible site effects. Liquefaction hazard assessment was carried out using available SPT data. Empirical methods based on SPT are used for the evaluation of factor of safety against liquef

Abstract

Displays have seen many improvements over the years. With advance- ments in pixel resolution, color gamut, vertical refresh rates and power con- sumption, displays today have become more personal and accessible devices for sharing and feeding information. Advancements in computer human interaction have provided novel interactions with current displays. Touch panels are now common and provide better interaction with the cyberworld shown on a device. Displays today have many shortcomings still. These include a rectangular shape, low color gamut, low dynamic range, lack of simultaneous focus and context in a scene, lack of 3D viewing, etc. Eorts are being made to create better and more natural displays than 2D at rect- angular screens we see today. Much research has gone into designing better displays including 3D displays, focus and context displays, HDR displays, etc. Such displays enhance a display directly using device level technologies such as physical, chemical and metallurgical means. This approach has been taken in the past but proves expensive and is hard to scale to better standards that may be needed in color, refresh rate, spatial and intensity resolution in the coming future. New paradigms must be explored to generate better displays that may provide better user experiences and are easy to view and interact with. The conventional direct approach requires new physical properties to be constantly discovered in order to push the envelop in display design. Such technologies are hard to come by and may take years to prove their merit, for them to be acceptable in the display design pipeline. An alternate is to use computation to enhance displays. Today compu- tation is easily available and cheap. CPUs follow the Moores law for their ever expanding compute capabilities. Multi-core CPU architectures are now common - even in hand held devices. GPUs consisting of 1500 cores deliver 1:5Tera FLOPS for $500 today. This abundance of compute capability has been applied to various systems with much success. Many areas including computational photography, computational biology and human computer in- teractions take advantage of computation to enhance a base system. Displays too have been shown to benet from such an approach. Fish tank virtual reality is an example of this, 3D viewing can be enabled for a head tracked viewer using standard displays in conjunction with computer graphics. Com- putation can thus be used to enhance displays or remove their shortcomings. Many displays are underway that combine computation with other means to provide better and natural user experiences. These may combine computa- tion with optics, display arrangement, metallurgy, sensors, etc. to bring out more than what is available on existing displays. Such displays can collec- tively fall under the term Computational Displays. There are two aspects to enhance displays using computation: using hard- ware modications and/or using algorithmic design. Computational displays, as a subject, covers both these grounds. While hardware modications can range from a simple arrangement of display elements to designing a com- pletely new hardware unit for a display system, the cost factor must be considered along with display applicability. Algorithmic design outshines hardware modication in this regard as it allows the use of any hardware and holds no bound on the design. Due to easy availability of computational devices much work can be ported to computational elements with limited dependence on hardware modication. We follow this line of thought in this thesis. We propose computational displays which employ computation to economically alleviate some of the shortcomings of todays displays us- ing algorithmic modication with limited use of hardware modication. We demonstrate the idea using four prototypes, which collectively demonstrate how computation can be used to enhance displays. Specically we propose solutions to the 3D viewing, the focus+context and the limited color resolu- tion problems in this thesis. We create four systems to this end, two dealing with rendering view-dependent 3D scenes to piecewise planar and non-planar surfaces, another giving a framework to render massive environments inter- actively to a tiled display wall, achieving focus and context for the scene, and the last providing better intensity resolution using three mixing meth- ods. The systems work on top of existing display methodologies and are independent of any specic display technology. This makes our systems scal- able to any displaying method and enhances the same using computation. In conclusion, we argue that computation/algorithms should be built into the displays themselves to enhance the visual experience.

Abstract

The rapid evolution of information technology (IT) has prompted a massive growth in digitizing books. Accessing these huge digital collections require solutions, which will enable the archived materials to be searchable. These solutions can only be acquired through research in document image understanding. In the last three decades, many signicant developments have been made in the recognition of Latin-based scripts. The recognition systems for Indian languages are very far behind the European language recognizers like English. The diversity of archived printed document poses an additional challenge to document analysis and understanding. In this work, we explore the recognition of printed text in Telugu, a south Indian language. We begin our work by building the Telugu script model for recognition and adopting an existing optical character recognition system for the same. A comprehensive study on all the modules of the optical recognizer is done, with the focus mainly on the recognition module. We then evaluate the recognition module by testing it on the synthetic and real datasets. We achieved an accuracy of 98% on synthetic dataset, but the accuracy drops to 91% on 200 pages from the scanned books (real dataset). To analyze the drop in accuracy and the modules propagating errors, we create datasets with different qualities namely laser print dataset, good real dataset and challenging real dataset. Analysis of these experiments revealed the major problems in the character recognition module. We observed that the recognizer is not robust enough to tackle the multifont problem. The classier's component accuracy varied signicantly on pages from different books. Also, there was a huge difference in the component and word accuracies. Even with a component accuracy of 91%, the word accuracy was just 62%. This motivated us to solve the multifont problem and improve the word accuracies. Solving these problems would boost the OCR accuracy of any language. A major requirement in the design of robust OCRs is the invariance of feature extraction scheme with the popular fonts used in the print. Many statistical and structural features have been tried for character classication in the past. In this work, we get motivated by the recent successes in object category recognition literature and use a spatial extension of the histogram of oriented gradients (HOG) for character classication. We conducted the experiments on 1.46 million Telugu character samples in 359 classes and 15 fonts. On this data set, we obtain an accuracy of 96-98% with an SVM classier. Typical optical character recognizer (OCR) only uses local information about a particular character or word to recognize it. In this thesis, we also propose a document level OCR which exploits the fact that multiple occurrences of the same word image should be recognized as the same word. Whenever the OCR output differs for the same word, it must be due to recognition errors. We propose a method to identify such recognition errors and automatically correct them. First, multiple instances of the same word image are clustered using a fast clustering algorithm based on locality sensitive hashing. Three different techniques are proposed to correct the OCR errors by looking at differences in the OCR output for the words in the cluster. They are character majority voting, an alignment technique based on dynamic time warping and one based on Progressive Alignment of multiple sequences. In this work, we demonstrate the approach over hundreds of document images from English and Telugu books by correcting the output of the best performing OCRs for English and Telugu. The recognition accuracy at word level is improved from 93% to 97% for English and from 58% to 66% for Telugu. Our approach is applicable to documents in any language or script.