Abstract

The rapid expansion of the Internet is receiving a great deal of attention world-wide. The technological developments and the increase in online communications have played a vital role in revolutionalizing the Information Age. There is a tremendous growth of online applications to manipulate the user’s personal data, which has resulted in the widespread availability of the user’s personal data in the digital form. This raises the issue of privacy protection against potential misuse of this data by legitimate service providers or intruders. Without proper countermeasures to thwart the attacks, security problems become a major threat and a serious impediment to further development of business applications on communication systems. Many of the current solutions provides information security by assuming a level of trust among the parties. The leakage of the critical data to third parties is prevented by applying cryptographic primitives as a secure layer over the standard algorithm. On the other hand, privacy preservation computation is more closely related to Secure Multiparty Computation (SMC). SMC enables two parties; one with the function f() and the other with the input x; to compute f(x) without revealing them to each other. 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. In this dissertation, we focus on development of ‘highly-secure’, ‘comunication and computationally efficient’ algorithms to problems with ‘immediate impact’ in the domain of computer vision and related areas. Security issues in computer vision primarily originates from the storage, distribution and processing of the personal data, whereas privacy concerns with tracking down of the users activity. The primary challenge is in providing the ability to perform generic computations on the visual data, while ensuring provable security. In this thesis, we propose lightweight encryptions for visual data, such that the server should be able to carry out the computations on the encrypted data and also store the stream if required, without being able to decipher the actual contents of the image. Moreover, the protocols are designed such that the interaction and the data communication among the servers is kept to a minimum. It has been proven before that the best way to achieve secure computation on a remote server is by using the cryptographic protocol of SMC. Thus, a method that provides provable security, while allowing efficient computations without incurring either significant computation or communication overhead has remained elusive till now. We show that, for designing secure visual algorithms one can exploit certain iii iv properties such as scalability, limited range etc, inherent to visual data to break this impenetrable barrier. We study and propose secure solutions for applications such as Blind Authentication, i.e. blindly authenticating a remote-user using his biometric. Subsequently, we present a highly secure framework for carrying out visual surveillance on random looking video streams at remote servers. We then propose a simple and an efficient cloud-computing based solution using the paradigm of secret sharing to privately cluster an arbitrary partitioned data among N users. The solutions we propose are accurate, efficient and scalable and has potential to extend over to even more diverse applications. In our first work, blind authentication, we propose private biometric authentication protocol which is extreamly secure under a variety of attacks and can be used with a wide variety of biometric traits. The protocol is blind in the sense that it reveals only the identity, and no additional information about the user or the biometric to the authenticating server or vice-versa. The primary advantage of the proposed approach is the ability to achieve classification of a strongly encrypted feature vector using generic classifiers such as Neural Networks and SVMs. Our proposed solution addresses the concerns of user’s privacy, template protection, and trust issues. And captures the advantages of biometric authentication as well as the security of public key cryptography. We then present an efficient, practical and highly secure framework for implementing visual surveillance on untrusted remote computers. To achieve this we demonstrate that the properties of visual data can be exploited to break the bottleneck of computational and communication overheads. The issues in practical implementation of certain algorithms including change detection, optical flow, and face detection are addressed. Our method enables distributed secure processing and storage, while retaining the ability to reconstruct the original data in case of a legal requirement. Such an architecture provides us both security as well as computation and communication effic

Abstract

Repeats are ubiquitous in DNA sequences. When these arise in the coding regions, the proteins encoded by these genes exhibit various types of periodic patterns of amino acids, ranging from runs of single amino acids, e.g., polyglutamine tracts in the protein huntingtin, to short tandem peptide repeats, e.g., tandem octapeptide repeats in prion proteins and tandemly repeated domains, e.g., ankyrin domain in cytoskeletal protein titin, to periodic occurrences of single amino acids, e.g., glycines repeated at every third position in collagen proteins. Since the order of amino acids in a polypeptide sequence plays an important role in the fold and function of the protein, it would be interesting to understand the structural and functional role of the repeated sequence in proteins. Hence for the investigation and analysis of repeats in proteins, we have proposed a computationally efficient approach for identifying the periodic repeats and implemented it in a web-server, PEPPER [http://ccnsb.iiit.ac.in/nita/PEPPER/]. The first step in understanding the functional and evolutionary analysis of the protein repeats would be to identify them among homologous sets and organize them in a database. With this objective we also developed a database of repeats, DRiPs [http://ccnsb.iiit.ac.in/nita/PEPPER/PTRDB/], by scanning the complete protein sequence database, Swissprot, using PEPPER. A large number of novel periodic repeats, not reported in SwissProt, have been identified using PEPPER and can be accessed through the DRiPs database. A detailed analysis of the distribution of the three types of periodic repeats in terms of its dependence on the protein length, the repeat length, and the copy number of the repeat and their distribution across kingdoms has been carried out. From this analysis we observe that there is a high incidence of repeats in eukaryotic proteins compared to prokaryotic proteins and this cannot be attributed only to longer lengths of protein sequences in eukaryotes. This led us to identify the functions of eukaryotic proteins containing proteins and we observed that these proteins are involved in complex cellular functions unique to eukaryotes. To understand the occurrence of repeats in evolution, an analysis of the copy number of the repeat pattern across homologs was carried out to see if the repeats are conserved over evolution or is there a random gain or loss of repeat copies in homologous proteins. In most cases conservation/gain in the copy no. of the repeat was observed giving a clear indication of the possible function role of repeats. We also investigated the disease association of the repeat patterns using OMIM databases and Trbase databases, wherein the annotations were manually checked to see if the disease association reported is due to the repeat expansions or due to the protein misfold/aggregation.

Abstract

With the advent of the Internet/WWW and the proliferation of textual news, richmedia, social networking, et cetera. there has been an unprecedented surge in the content on the web. With huge amount of information available on the world wide web, there is a pressing need to have ‘Information Access’ systems that would help users with an information need in providing the relevant information in a concise, pertinent format. There are various modes of Information Access including Information Retrieval, Text Mining, Machine Translation, Text Categorization, Text Summarization, et cetera. In this thesis, we study certain aspects of “Text Summarization” as a technology for Information Access’. Majority of the recent work in the area of Text Summarization addresses the subproblems like Ranked Sentence Ordering, Generic Single Document Summarization, Generic Multi-Document Summarization, Query-Focused Multi-Document Summarization, Query-Focused Update Summarization. In this thesis we focus on two tasks, specifically “Query-Focused Multi-Document Summarization (QFMDS)” and “Query-Focused Update Summarization (QFUS)”. The QFMDS task has generated a lot of community interest for obvious reasons of being closer to a real world application of open domain question answering. Given a set of N relevant documents on a general topic and a specific query (or information need) within the topic, the task is to generate a relevant and fluent 250 word summary. The focus of this thesis lies around four issues dealing with query-focused multi-document summarization. They are: 1. Impact of query-bias on summarization 2. Simple and strong baselines for update summarization 3. Language modeling extension to update summarization 4. An automated intrinsic content evaluation measure In this thesis we identify two dependent yet different terms ‘query-bias’ and ‘query-focus’ with respect to the QFMDS task and show that most of the automated summarization systems are trying to be query-biased rather than being queryfocused. In the context of this problem, we show evidence from multiple sources to display the inherent bias introduced by the automated systems. First, we theoretically explain how a na¨ıve classifier based summarizer can be enhanced greatly by biasing the algorithm to use just the query-biased sentences. Second, on an ‘information nugget’ based evaluation data, we show that most of the participating systems were query-biased. Third, we further build formal generative models, namely binomial and multinomial models, to model the likelihood of a system being query-biased. Such a modeling revealed a high positive correlation between ‘a system being query-biased’ and ‘automated evaluation score’. Our results also underscore the difference between human and automated summaries. We show that when asked to produce query-focused summaries humans do not rely to the same extent on the repetition of query-terms. The QFUS task is a natural extension to the QFMDS task. In update summarization task a series of news stories (news stream) on a particular topic are tracked over a period of time and are available for summarization. Two or more sets of documents are available: an initial set, followed by multiple updated sets of news stories. The problem is to generate query-focused multi-document summaries for the initial set and then produce update summaries for the updated sets assuming the user has already read the preceding sets of documents. This is a relatively new task and our work in this context is two fold. First, we defined a sentence position based baseline summarizer which is genre dependent. In the context of the new task, we argue that current baseline in the update summarization task is a poor performer in content evaluations and hence cannot help in tracking the progress of the field. A stronger baseline such as the one based on “sentence position” would be robust and be able to help track the progress. Second, we describe a generic extension to language modeling based approaches to tailor them towards the update summarization task. We showed that a simple Context Adjustment (CA) based on ‘stream dynamics’ could help in generation of better summaries when compared to the base language modeling approach. In Text Summarization, like in any other Information Access methodologies, evaluation is a crucial component of the system development process. In language technologies research, Automated Evaluation is often viewed as supplementary to the task itself since knowing how to evaluate would lead to knowing how to perform the task. In the case of summarization, knowing how best to evaluate summaries would help in knowing how best to summarize. Usually, manual evaluations are used to evaluate summaries and compare performance of different systems against each other. However, these manual evaluations are time consuming and difficult to repeat, hence infeasible. Keep

Abstract

Proteins are the most complex organic compounds synthesized in nature and are an important class of biomolecules that serve as essential building blocks of the body. Proteins are organized into structural/functional units like motifs, domains and folds. So far, efforts to understand protein evolution and its functions have focused on domains that can fold into a stable threedimensional structure independent of the rest of the protein chain and perform a unique function conserved over the evolution. Genetic recombinant techniques allow reorganization of domains at the amino acid sequence level (such as circular permutations). This along with swapping and insertion of domains are responsible for new protein functions and evolution. Protein domains are very useful in analyzing the mechanisms of protein folding and their stability and structural transformations in various conditions. This can be done reliably if a multi-domain target is considered only in terms of its constituent domains. The underlying goal is to reduce a complex protein structure to a set of simpler yet structurally meaningful units, each of which can be analyzed independently. Being the basic units of protein folding, function and evolution, the identification and analysis of domains forms the first step in understanding the protein functional and structural aspects. Although the boundaries of a domain can be determined by visual inspection, there is an urgent need for the development of accurate methods for automatic domain identification as the number of solved protein structures is increasing rapidly. This problem of dividing a protein structure into domains is not yet solved efficiently due to the lack of an unambiguous definition of a domain. Existence of noncontiguous domains adds to the difficulty in developing an automated solution for domain partitioning. Though several methods have been proposed to predict domains they all have notable limitations. Even current reliable methods such as DomainParser, based on graph partitioning approach, do not distinguish between single and multi-domain proteins. Another recent graph-spectral approach by Sistla et al is unable to identify noncontiguous multi-domains and also does not distinguish between single and multi-domain proteins. With about 25% of multi-domain proteins being noncontiguous, there exists a need for reliable domain identification methods. Here we present a simple method based on graph spectral properties for automatic domain prediction from its 3-dimentional structure. We show that graph properties such as density and interaction strength apart from spectral analysis helps in domain identification. Since most single domains are typically less than 300 amino acids long, our first screening for single domain proteins is done on the basis of length. Next we show that the density shows a gradual decrease with the increase in the length of the protein, thus providing a useful parameter for domain identification. It is a common observation that the interactions between the amino acids are higher within a domain (intra-domain interactions) than across the domains (inter-domain interactions). We exploit this feature for identifying the domain boundaries and also for distinguishing between single and multi-domain proteins. In general, domains are identified either by: (i) Top-down approach, i.e., starting with the whole structure partition it iteratively into smaller units. (ii) Bottom-up approach, i.e., defining very small structural units and assembling them into domains, or (iii) a combination of both. In the proposed approach for domain identification, both, top-down and bottom-up approaches are implemented. The algorithm proceeds by first decomposing the protein contact network into compact structural modules and then assembling them into domains. These interactions and the topological details of protein structures can be effectively captured by a protein contact network, constructed by considering each amino acid as a node, and with an edge drawn between two nodes if the Cα atoms of the amino acids are within 7Å. Newman’s community detection approach proposed for social networks is employed here to identify domains in protein structures as we observe similarities between the two problems. It is particularly suitable for domain identification problem as one may not have a priori knowledge of the number of structural domains in a protein. The basic principle of this approach is to divide the vertices into two groups so as to minimize the number of edges running between the groups, which is in agreement with the basic feature of domains that inter-domain connections are more in number than connections across domains. We have implemented this approach on protein contact networks and analyzed the eigenvectors of the largest eigenvalue of the modularity matrix (which is a modified form of the Adjacency matrix). First, a given pr

Abstract

In today’s world, Information Retrieval (IR) systems play a significant role in facilitating users to access their desired information on the web. Current IR systems have come a long way in retrieving the most relevant results by using sophisticated ranking algorithms, relevance feedback, efficient indexing techniques etc. As a substantial amount of the web content is in English, current IR systems do a fair job of fulfilling users information needs. On the other hand, Non-English web content has also seen tremendous growth in the recent years. Content from local or native languages originates mainly in the form of news portals, blogs, social networking web sites, etc. The surge in such web content can be attributed to major factors like users interests to read and express thoughts in their local languages, availability of sophisticated input methods for local language text entry, and robust technologies to handle such Non-English content. From the users perspective, IR systems that can retrieve relevant local language search results in addition to the search results in English would be more useful. This aspect of information need has given rise to the field of Cross Language Information Retrieval (CLIR). CLIR deals with retrieval of documents present in one language using user queries in another language. CLIR systems either translate the queries to the documents language during input processing or translate the documents to the language of the queries during indexing for efficient retrieval. In this thesis, we focus on exploring efficient ways to translate user queries for cross language retrieval involving Indian languages. To build an effective query translation process, we need to find answers for some interesting questions pertaining to queries like What does a general user query consist of? What are the ways to translate user queries from one language to another? A typical web query consists of three to four words with most of them as named entities. Studies have shown that more than 80% of the query terms are Out Of Vocabulary (OOV) words. Generally, these OOV words are not present in bi-lingual thesaurus. Hence they cannot be translated using bi-lingual dictionaries similar to other content words present in the query. They have to be transliterated either phonetically or orthographically or combining both based on the source and target languages. The content words in the query can be translated using several approaches including bi-lingual thesaurus, Ontologies, parallel or comparable corpora, using web and other related resources. As one could infer, some form of “external resources” is needed for translating queries across any two languages. Firstly, we try to address the problem of translating OOV words in the context of English-Indian language and Indian language-English cross language retrieval. In our analysis, we found that most of the transliteration errors are due to ambiguities in the usage of “vowels” either in the source side or in the target side word. To address this issue, we introduce a mapping based approach of transliterating named entities that generates “consonant skeleton” for the given source word and map it to the right target side word equivalent based on phonetically modified Levenshtein distance. Our method requires very minimal training data and yet achieves significant improvement in performance when compared to another statistical based technique. Initially, we evaluated the algorithm for English-Tamil transliteration. The transliteration accuracy of our algorithm is 91%, 96% and 99% for top-1, top-3 and top-8 transliteration candidates, when compared to 42%, 62% and 77% of the statistical system on a given standard test data. We have also extended the algorithm for English-Hindi and Hindi-English transliteration of named entities in the cross language retrieval scenario. Our algorithm proved to be effective in the cross language retrieval context and our systems have achieved state-of-the-art performance. Secondly, as mentioned earlier, most of the current CLIR systems use some form of external translation resources for translating queries. However if such resources are scarce or not available across any two languages, query translation becomes rarely feasible. In the second case, we address this particular issue in the context of CLIR across Indian languages. We propose an approximate, fuzzy string matching technique that exploits the presence of common origin words and similarity across the writing systems between Indian languages for query translation. We have implemented our technique for query translation on top of existing CLIR systems. Our method performs reasonably well for CLIR across all the six bi-lingual language pairs comprising of Hindi, Bengali and Marathi. We have also tested the significance of our obtained results and have shown that they are statistically valid.

Abstract

This thesis is an investigation into Indian language information access. The investigation shows that Indian language information access technologies face severe recall problem when using conventional IR techniques (used for English-like languages). During this investigation we crawled the web extensively for Indian languages, characterized the Indian language web and in the process came up with some solutions for the low recall problem. We focused our investigation on the loss of recall in monolingual and cross-lingual based IR and text summarization. The following are some of the major contributions of this thesis. We built a language focused web crawler that can optimally find and fetch pages of a given language using syllable based IR index model. We conducted a language focused crawl for a period of 6 months to analyze the characteristics and distribution of Indian language content on the web. We crawled the web for a continuous period of 2 years to collect a large corpus of Indian language web pages, which was used to build IR and summarization evaluation datasets. We showed that Indian language information access technologies that use state-of-the-art technologies used by English like languages, face low recall. We observed the recall loss to be relatively higher when the target language corpus is English. We came up with a semi-automatic method of converting proprietary encoded text into UTF-8 which otherwise was causing low-recall in document retrieval. We came up with a unied information access framework which can address the problems of Monolingual and Cross-lingual Information Retrieval and Text Summarization. We dened a single index model that can be used for many scoring functions used in our Monolingual and Cross-lingual IR and Summarization. This index model can help in identifying languages of a document, handling morphological variations, spelling variations, co-occurrence based query term expansion and weighted term dictionary translation. The score of each document or sentence (in the case of summarization) is viewed as a joint probability of multiple IR events occuring in sequence. Assuming each event to be independent of each other, we multiply the scores of each intermediate IR event, thereby weighting the query terms. For example, Monolingual IR with morphological variation handling is broken down as two sequential events. The first event is the generation of multiple morphological variations using syllable-term model, then multiplying these weights with the term score in each document. We modeled the stemming problem as an IR problem and came up with a syllable based model to retrieve and rank the morphological variations of a given word. This ordered set was used to generate a weighted query for retrieval of documents. We showed that, word spelling normalization is an essential component of Indian language information access systems. We proposed a linguistically motivated rule based approach and showed that this approach works better than the various approximate string matching algorithms. We modeled the problem of Dictionary based query translation as an IR problem. This helps us to automatically generate a weighted query when used in combination with query expansion techniques. We attempted cognate identication among Indian languages and evaluted their role in Telugu-Hindi CLIR using many approximate string matching algorithms. We found that Jaro-Winkler technique to identify cognates can provide reasonably good performance even without a dictionary for Telugu-Hindi CLIR. We also observed that using the available dictionary did not improve the performance much above the cognate based approach. Since most of the search queries are usually nouns, cognate based translation seems to work well. We modeled the problem of Text summarization as an IR problem. This helps us to overcome the sparseness problem of sentences while scoring them using the term collocation model. We showed that query independent scoring of sentences contribute a lot towards the quality of the summary. This type of scoring that we used for the first time in a query-focused summarization, helps in providing background information about a topic. This helps in improving readability and provides information to the user without losing the context. We modeled automatic transliteration of text from one language to another language as a sequence labeling problem. We used Conditional Random Fields to generate possible transliterations of text from one language to another. This model outperforms the HMM based model which is widely used. We dened and explored the problem of cross-lingual query based text summarization for Indian language queries. To the best of our knowledge this is the rst work in cross-language query based text summarization. We showed that the performance of a cross-lingual query focused summarizer does not degrade as much as a CLIR system

Abstract

With vast amount of data available electronically, there has been an ever increasing need to readily sort out and extract only the chief and pertinent sections from the data sources to present to the user. Time and space being critical constraints in this electronic era, it is indispensable to provide a mechanism to locate and browse required information quickly to avoid information overload. Automatic multi-document text summarization fulfills this need by presenting user with desired information in the form of a quick summary. Given a collection of documents related to same topic, the goal of multi document summarization system is to generate a short and concise summary that can be read in lieu of the original document collection. In multi-document summarization, sentence extraction is a critical phase in the formation of useful summaries. where the task is to pick a subset of sentences from the document cluster to form the summary giving an overall sense of the document’s content. Developing a principled sentence extraction mechanism that also performs empirically well is a big challenge in itself. This thesis presents a new sentence extractive summarization framework based on Information Loss. We treat summarization as a decision making problem. Given a set of documents, either to a human or system, the selection of few sentences as a representative to whole document set is a critical decision making problem. As per decision theory we derive a general extraction mechanism for picking sentences based on an ascending order of the expected risk of information loss. We propose to use an intrinsic loss function to compute this information loss and to make a decision on picking a sentence as a part of summary. Sentences and documents are considered as different text units and are represented by probabilistic language models to estimate their distributions. In this inferential setting we use entropy based intrinsic loss function (relative entropy) to measure the discrepancy between the sentence and document model. Relative entropy loss function measures how bad a sentence distribution is in modeling the documents distribution. By doing this we are able to capture the amount of information loss in picking a sentence to represent the whole document cluster. The selection of a sentence in summary is not by a set of features but only the measure of loss. A large document set is divided into smaller text units (sentences), each of which tries to approximate the document set variationally, yielding an overall variational approximation. Sentences which are the candidates of summary act as a surrogate for document set in a larger inference process. This decomposition strategy leads us directly to a new sentence extraction algorithm. With a simple redundancy identification and text reformulation mechanism, we come up with a lightweight summarizer to generate more informative summaries. The proposed algorithm generates the extracts on the fly without extensive computation or training which seem to be used in various state of the art algorithms. Furthermore, we consider different information theoretic divergence measures and loss functions to estimate loss between sentence and document distribution, and analyze their performance. In order to evaluate the performance of our approach, we have used DUC (Document Understanding Conference) and MSE (Multi-Lingual Summarization Evaluation) dataset that have been widely used in recent document summarization evaluations. We have applied ROUGE (Recall-Oriented Understudy for Gisting Evaluation) as the automatic summary evaluation metric which is the standard way of evaluation of summaries. It essentially calculates n-gram overlaps between automatically generated summaries and previously-written human summaries. A high level of overlap indicates a high level of shared concepts between the two summaries. Our overall results are the best reported on the DUC-2004 summarization task for all three metrics ROUGE-1 ROUGE-2 and ROUGE-SU4, and are the best, but not statistically significantly different from the best system in MSE-2005. Results on DUC-2007 dataset supports our results on DUC-2004 and MSE-2005. Our system is also substantially simpler than the previous best systems. Furthermore, we go beyond the traditional notion of generic relevance and incorporate a user factor as sentence extraction criteria. Here we treat summarization process as not only a function of the input text but also of its reader. We believe that a good summary should change in accordance to preferences of its reader. For this purpose we model the user in the proposed information loss based framework to extract user specific personalized summaries by creating web based profiles using the personal data available online. To evaluate personalized summaries, a controlled user-centered qualitative evaluation was carried out on news articles of science and technology domain. The results indi

Abstract

With the rapid spread of Indian language content on the web, user input oriented applications in Indian languages are also becoming popular. There is an increasing need for efficient and user friendly input interfaces to type in Indian languages. However, despite the obvious need and significance, text input has not been studied and researched so far, in the context of Indian languages. In this thesis, we study the problem of text input for Indian languages, by taking Telugu as the test case. Owing to the similarity among Indian languages, the results of this work can be applied with necessary changes, to other Indian languages as well. We have first classified data input systems in to four categories - keyboard layouts, input method editors, prediction systems and soft keyboards. In the first category, we have designed some keyboard layouts for Telugu, based on a set of design principles formed after a study of the relevant literature. We have then evaluated them based on the set of evaluation measures and concluded that our designs work better than the existing solutions, thereby providing efficient alternatives to the present day Telugu keyboard. In the context of input method editors, we have studied the different mappings available to convert between Indian languages and Roman script, and compared them with our new mapping, in an attempt to find out a mapping closest to human intuition. We have concluded that though there is no significant difference in performance with different mappings, Rice Transliteration Scheme has a better ease of remembrance compared to other mappings. We have studied the problem of text prediction for Indian language input and proceeded towards developing transliteration based prediction approach to text input in Telugu. We have proved that a simple approach like edit-distance based text prediction works very well as a text input method and offers a light weight and efficient system. Finally, we have worked on the design and evaluation of soft keyboards for Telugu. Our designs worked better than the existing soft keyboards for Telugu. Thus, we have successfully proposed efficient text input methods for Telugu which can be good alternatives to existing input methods.

Abstract

The present growth of digitization of books and manuscripts demands an immediate solution to access them electronically. This will enable the archived valuable materials to be searchable and usable by users in order to achieve their objectives. This requires research in the area of document image understanding, specically in the area of document image recognition as well as document image retrieval. In the last three decades signicant advancement is made in the recognition of documents written in Latin-based scripts. There are many excellent attempts in building robust document analysis systems in industry, academia and research labs. Intelligent recognition systems are commercially available for use for certain scripts. However, there is only limited research eort for the recognition of indigenous scripts of African and Indian languages. In addition, diversity of archived printed documents poses many challenges to document analysis and understanding. Hence in this work, we explore novel approaches for understanding and accessing the content of document image collections that vary in quality and printing. In Africa around 2,500 languages are spoken. Some of these languages have their own indigenous scripts in which there is a bulk of printed documents available in the various institutions. Digitization of these documents enables us to harness already available language technologies to local information needs and developments. We present an OCR for converting digitized documents in Amharic language. Amharic is the ocial language of Ethiopia. Extensive literature survey reveals that this is the rst attempt that reports the challenges toward the recognition of indigenous African scripts and a possible solution for Amharic script. Research in the recognition of Amharic script faces major challenges due to (i) the use of large number of characters in the writing and (ii) the existence of large set of visually similar characters. Here we extract a set of optimal discriminant features to train the classier. Recognition results are presented on real-life degraded documents such as books, magazines and newspapers to demonstrate the performance of the recognizer. The present OCRs are typically designed to work on a single page at a time. We argue that the recognition scheme for a collection (like a book) could be considerably dierent from that designed for isolated pages. The motivation here is therefore to exploit the entire available information (during the recognition process), which is not eectively used earlier for enhancing the performance of the recognizer. To this end, we propose self adaptable OCR framework for the recognition of document image collections. This approach enables the recognizer to learn incrementally and adapt to document image collections for performance improvement. We employ learning procedures to capture the relevant information available online, and feed it back to update the knowledge of the system. Experimental results show the eectiveness of our design for improving the performance of the recognizer on-the- y, thereby adapting to a specic collection. For indigenous scripts of African and Indian languages there is no robust OCR avail- able. Designing such a system is also a long-term process for accessing the archived document images. Hence we explore the application of word spotting approach for retrieval of printed document images without explicit recognition. To this end, we propose an eective word image matching scheme that achieves high performance in presence of script variability, printing variations, degradations and word-form varia- tions. A novel partial matching algorithm is designed for morphological matching of word form variants in a language. We employ a feature extraction scheme that ex- tracts local features by scanning vertical strips of the word image. These features are then combined based on their discriminatory potential. We present detailed experi- mental results of the proposed approach on English, Amharic and Hindi documents. Searching and retrieval from document image collections is challenging because of the scalability issues and computational time. We design an ecient indexing scheme to speed up searching for relevant document images. We identify the word set by clustering them into dierent groups based on their similarities. Each of these clusters are equivalent to a variation in printing, morphology, and quality. This is achieved by mapping IR principles (that are widely used in text processing) for relevance ranking. Once we cluster list of index terms that dene the content of the document, they are indexed using inverted data structure. This data structure also provides scope for incremental clustering in a dynamic environment. The indexing scheme enables eective search and retrieval in image-domain that is comparable with text search engines. We demonstrate the application of th

Abstract

Keywords: Personalized Search; Personalized Web Search; Web Search; Re ranking; User Modeling; Improving Web Search; User Profiling; Improving Ranking; Query Log Analysis; Simulated Feedback The main problem with web search is as follows : There is too much information available on the web; query words used by users often are confusing, ambiguous (a query “Java”can mean the Java island in Indonesia or the Java programming language), and some times are poor descriptors of information need (‘SBH” can mean “State Bank of Hyderabad” or “Syracuse Behavioral Healthcare” among others) ; users are often not patient enough to see long list of results given by search engines to find relevant information. It has been observed that users typically view top few results, usually top 5 or 10, some times 20 and much fewer times 30 and so on. In this scenario, web search can be made more useful, effective and less burdensome to users by - trying to infer what would be relevant for the current user for a given query considering individual users’ interests and provide those results on the top so that the user does not have to scroll down a long list of results. The problem of Personalized Search aims to customize search results according to each individual user for him to find the most relevant documents to him on the top by considering his idiosyncrasies. This would possibly satisfy them and help in finding relevant information easily and quickly. The major challenges for personalized search are two fold. The first is, modeling appropriate user context and learn a user model. The second is, how to utilize the user model to improve search accuracy. Another important challenge is evaluation of experiments. There are no standard and bench mark datasets available on which experiments can be performed. This makes comparison with earlier work in the litera- ture and replicating their results difficult. There are also no standard metrics available to effectively evaluate personalized search algorithms. Some commonly used metrics used to evaluate Information Retrieval systems are usually used. We propose three approaches for personalized web search. Our first approach is based on Statistical Language Modeling techniques. In spite of the progress made in language modeling and IR recently, there has not been much work applying language modeling techniques to personalized web search. In this approach, we learn a user model by capturing statistical properties of text from his past searches. We explored different contexts. The different contexts include using single word and two adjacent words (Simple N-Gram based method) and capturing relationship between query and document words (Noisy Channel model based method). Our second approach is based on Machine Learning algorithms which show an interesting and promising framework for learning user profiles. We make use of ranking SVM, a variation of the classification support vector machines for learning the user model. The above two approaches are a class of approaches that have exploited user feedback data either explicit or implicit. The third approach is another interesting approach, where, we attempt to model a particular user based on only past queries posed by corresponding user. The basic idea is to see if there is enough information available in just the previous queries without having to use teh clickthrough data made by the user. We have employed simple approaches based on language modeling to learn the user model from the previous queries of the user. We propose three approaches for personalized web search. Our first approach is based on Statistical Language Modeling techniques. In spite of the progress made in language modeling and IR recently, there has not been much work applying language modeling techniques to personalized web search. In this approach, we learn a user model by capturing statistical properties of text from his past searches. We explored different contexts. The different contexts include using single word and two adjacent words (Simple N-Gram based method) and capturing relationship between query and document words (Noisy Channel model based method). Our second approach is based on Machine Learning algorithms which show an interesting and promising framework for learning user profiles. We make use of ranking SVM, a variation of the classification support vector machines for learning the user model. The above two approaches are a class of approaches that have exploited user feedback data either explicit or implicit. The third approach is another interesting approach, where, we attempt to model a particular user based on only past queries posed by corresponding user. The basic idea is to see if there is enough information available in just the previous queries without having to use teh clickthrough data made by the user. We have employed simple approaches based on language modeling to learn the user model fr