Abstract

In recent years, graph theory is being extensively used to study large scale and complex systems from diverse disciplines, viz. physical, biological, computer and social sciences. Various models viz. scale-free, small-world, etc. apart from random graph and regular graphs have been proposed. In this thesis, we present a detailed analysis of topological and structural properties of two air transportation networks, airport network of India (ANI) and world airport network (WAN) using graph theoretic approach. These air transportation networks have been constructed by considering airports as nodes, direct flight routes between them as edges and number of flights on each route as the weights. The heterogeneity in connectivity and long-range couplings observed in these networks suggest that certain nodes may play an important role in maintaining the stability and efficient flow through the network. Identification and analyzing the impact of targeted removal of such “critical” nodes on the network is the major focus of this thesis. This has been carried out by analyzing various graph centrality measures, viz., degree, strength, betweenness and closeness in the context of air-traffic flow. Such an analysis would not only enable us to improve the infrastructure and air connectivity and help in promoting tourism, but also help in identifying crucial airports and routes to regulate traffic in emergencies such as accidental failure of an airport, diverting traffic to avoid congestion and delays during unexpected climatic changes, etc. In the last few decades, we have observed the main cause of the epidemic turning into pandemic of an infectious disease is its transmission over the densely connected air transportation services. Using a simple SIR (Susceptible-Infected-Recovered) compartmental model for disease spread, our analysis of graph centrality measures suggests that by reducing flights on important routes, the spread of the disease can be curtailed. We observe that though these air transport networks exhibit small-world and scale free behaviour, the preferential growth Barabasi-Albert (BA) scale free model fails to explain the growth and certain topological properties of these networks. We carried out a comparative study of various scale-free models with the actual airport networks and propose a model which captures the evolution of these transportation networks.

Abstract

Hierarchical Ring Networks constitute an interesting class of networks, from the point of view of their range of applications and their design considered as a graph theoretic problem. They are widely used in logistics, communications sytems and the design of shared multiprocessors. In logistics, the distribution network comprising of manufacturing centres, warehouses and retail outlets can be modeled as Hierarchical Ring Networks (HRNs). In the context of processor design, shared memory multiprocessors face the problem of scaling due to the fact that the CPU-to-memory connection becomes a bottleneck, with multiple processors vying for the available RAM. The inherent structure of HRNs has been shown in literature to help scale these systems. In communications systems, they can be used to have equitable distribution of load in flat architectures that are prevalent in new generation communication systems. It is imperative that efficient design of these structures has to be carried out, to reduce costs of their installation and help increase their ease of management. In this thesis, we look at methods to design low cost HRNs. This np-hard problem is stated in the context of Euclideancosts of the links and the cost of the capacity to be installed on these links to help put up these networks. Extensive work has been done in literature for the design of 2-level HRNs only. Further, most approaches to a solution deal with the problem in a series of chronological steps, which will end up giving us sub-optimal solutions. We first present methods to design 2-level HRNs. Following this, we solve the generic, k-level HRN design problem. We provide formulations of the problems and present heuristics based on Simulated Annealing and Genetic Algorithm. Our algorithms provide a holistic approach to the problem at hand and we have used them to design networks containing upto 1000 nodes, where previous methods only solved for nearly 120 nodes. Our results show that our algorithms consistently perform better than CPLEX – which we have used for comparison. We then proceed to show one important application of HRNs in 4th generation Radio Access Networks. We try to understand the performance of a topology based on HRNs in the Evolved Universal Terrestrial Radio Access Network or EUTRAN – the radio access network of LTE systems.

Abstract

Domain Name System(DNS) is an inevitable component of the critical infrastructure of the Internet. It is a hierarchical distributed database system which provides a crucial service for the internet i.e. the mapping of human-friendly domain names to their respective machine-friendly IP addresses and vice versa. Almost all internet-based applications including http, ftp and email, need to resolve a given domain name to its respective IP address prior to establishing connections. DNS provides the mapping service which is fundamental not only to the health of the Internet but also to the protection and integrity of the data. In case, mapping of a domain name to an IP address in the system gets corrupted, the system would no longer be acceptable. Being probably the most valuable infrastructure in the Internet, its security is of utmost priority. The domain names in a DNS database are stored in the form a hierarchical tree structure which is known as domain name space. Each node in the tree contains zero or more resource records which hold information associated with a domain name. DNS cache these resource records for a specific time period, i.e., TTL (Time-To-Live). TTL too plays an important role in maintaining the consistency of the cached resource records. Short TTL reduces the likelihood of getting old information but increases the DNS utilization whereas long TTL decreases the DNS utilization but at the same time increases the chance of retrieving outdated information. DNS was not earlier designed to save itself against different kinds of attacks such as cache poisoning, rebinding attacks etc. This is the reason that DNS servers have been manipulated by attackers to launch phishing attacks, to commit click-frauds and to drive traffic to malicious websites. Among all the different kinds of attacks on DNS, DNS cache poisoning is the prominent one. DNS cache poisoning refers to the cases where the cache of a DNS server gets corrupted due to the injection of false mapping in the server which affects the accuracy of DNS lookups. Consequently, when queries arrive at the DNS server, inaccurate and probably malicious replies are sent as the response. False mapping can be injected into a DNS in many ways i.e. by dns spoofing, dns forgery etc. After one poisoned record is injected into the cache, it can spread to other parts of the cache or other servers through query/response between servers. DNS cache poisoning could be used by an attacker to redirect the querier to a non-existent IP address, thus causing Denial-of Service or the querier can be redirected to a malicious website which drops Malware/Spyware or s/he could even be redirected to attacker’s website, causing phishing attack. Till date, many different solutions have been proposed to overcome the problem of cache poisoning but none has been deployed successfully. Certain proposed solutions like DNSSEC, DNSCurve etc, found to be efficient against cache poisoning but they have not been successfully deployed primarily because of the complexity involved in key management. Certain other solutions were neglected because either they required changes in the DNS protocol or they introduced considerable latency in the system making them an undesirable solution. Hence, in spite of all the solutions proposed till date to mitigate cache poisoning attacks, the problem still persists. To mitigate cache poisoning attacks, we have proposed an approach - Domain ConsistencyManagement system (DCMS) which makes the use of response delays for a specific resource-record type between a DNS client and a DNS server. Our approach is similar to stimulus-response model in which a response is expected for a specific stimulus within a specific period of time. If the response is received out of the period then it could be the result of some flaw in the system. Similarly in our approach we expect the response of a DNS query for a specific resource-record type to be received within a certain period of time. In case the DNS response is received out of period we suspect an attack on the system and perform a check to ensure the consistency of the response received. The significant feature of our approach lies in its self-learning that in parallel it updates its database of response delays for a specific resource- record type between specific DNS client and DNS server, thereby helping the system not only in proper functioning, even it enhances its performance. DCMS makes cache poisoning attacks, almost infeasible, even for motivated and powerful attackers. The biggest advantage of our approach is that it does not require any change in the DNS protocol, hence it could be deployed on a large scale within a short period of time. It does not even require any changes at the server side as inWSEC-DNS to ensure the consistency of the responses. Since it does not involve any cryptography technique, hence any sort of key management is not re

Abstract

Biomolecules are the building blocks of life that regulate the biological processes within the organisms. The interplay of just three classes of biomolecules: DNA, RNA and proteins provide complexity to the biological world. Their structures, stabilities and dynamics are keys to understand the working of Nature. Advanced biophysical and biochemical techniques have proven useful to study the structure, dynamics and local flexibilities within the biomolecules. However, most of these sophisticated experimental techniques are complex and time consuming, apart from being expensive. Also, they do not always directly provide an atomistic picture of macromolecular dynamics in situ with sucient time resolution. In current scenario of enhanced computing power, computer simulations have emerged as a useful tool to not only better interpret experimental results; in several ways they complement experimental investigations. We have used simulation methods to probe some contemporary issues related to structural stability and functional dynamics of biomolecules, with focus on nucleic acids and proteins. This thesis describes investigations using simulation techniques as applied to three dierent systems, in order to address three types of issues related to biomolecular dynamics: functional behavior of purine (adenine, guanine) and lysine riboswitches; folding of small mitochondrial subunit binding protein and modeling the structure and possible functional dynamics of a drug target enzyme. The studies address a wide range of contemporary issues related to the compatibility between simulation methods used and scientific questions asked. Thus, wherever possible, the work involves benchmarking of simulation conditions and analysis methods and attempts at reconciliation of available experimental data with the interpretation of trajectory analysis results.

Abstract

Signal processing applications such as ones dealing with image/voice have an inherent capability to tolerate noise. These applications are primarily judged by human perception which can ignore certain inaccuracies in image/voice applications. Probabilistic computing is a form of computing that trades tolerable errors for large amounts of gains in terms of energy, area and speed in the underlying hardware for these applications. With the stringent requirements on energy consumption, size and processing speed through modern day computing devices, there is a need to evaluate what trade-offs can be made with respect to the quality of the application for gains in terms of energy, area and delay of the computing circuit. Motion estimation, computationally the most intensive portion of the video encoder, is a suitable candidate to be considered as an application for probabilistic computing. With a plethora of video applications that video compression caters to, motion estimation is also a widely used application necessitating research on energy, delay and area optimized circuit design for motion estimation. The focus of this research is mainly to optimize energy and processing speed of the motion estimation architecture using probabilistic computing. The term probabilistic computing encompasses various techniques out of which two have been considered in this thesis. These techniques are Probabilistic Complementary Metal Oxide Semiconductor (PCMOS) and probabilistic pruning. PCMOS is a model for CMOS emulating the erroneous nature of future technology nodes. CMOS design is continuously faced by the challenge of achieving low-energy computation, which is addressed by technology scaling accompanied by voltage scaling. Voltage scaling in turn affects the noise immunity of the device, which is predicted to result in erroneous nature of future CMOS technology nodes. The PCMOS model is used to build circuits for motion estimation algorithms. Motion estimation is established to have a high resilience towards PCMOS based computing and energy savings to the tune of 40% to 57% are seen. Furthermore, algorithmic modifications for motion estimation are suggested that further increase the achievable energy savings sizably (13% to 23% increase) at the target degradation allowed. Probabilistic pruning works towards removal of parts of the circuit that contribute least to the quality of the application, thereby, optimizing the circuit gains for tolerable amounts of error. The overall savings for motion estimation through probabilistic pruning are found to be 27% to 65% in energy, 14% to 30% in delay and 29% to 54% in area consumption of the motion estimation circuit. Probabilistic pruning is compared with bit-width reduction of the circuit for motion estimation proposed in past research. Probabilistic pruning is found to increase the processing speed via motion estimation circuit considerably (6% to 18%) for a minor increase in area consumption (3% to 5%) when compared with bit-width reduction at approximately same quality reduction and energy consumption through the motion estimation circuit.

Abstract

The amount of information available on the web is steeply increasing. We need efficient techniques to analyze such large data. Frequent itemset mining play an important role in analyzing such data. Frequent itemset mining, which extracts frequently occurring group of items, has many applications like Association rule mining, Correlations, Dimensionality Reduction, Clustering and Classification. In this thesis, we show how frequent itemsets handle the problems of evolutionary clustering and summarization of scientific articles. Evolutionary clustering is an emerging research area addressing the problem of clustering dynamic data. An evolutionary clustering should take care of two conflicting criteria: preserving the current cluster quality and not deviating too much from the recent history. We propose an algorithm for evolutionary clustering using frequent itemsets. A frequent itemset based approach for evolutionary clustering is natural and it automatically satisfies the two criteria of evolutionary clustering. We provide theoretical as well as experimental proofs to support our claims. We performed experiments on our approach using different datasets and the results show that our approach is comparable to most of the existing algorithms for evolutionary clustering. We also present a novel unsupervised approach to the problem of multi-document summarization of scientific articles, in which the document collection is a list of papers cited together within the same source article, otherwise known as a co-citation. At the heart of the approach is a Frequent Itemset based clustering which clusters fragments extracted from each co-cited article and relevance ranking using a query generated from the context surrounding the co-cited list of papers. This analysis enables the generation of an overview of common themes from the co-cited papers that relate to the context in which the co-citation was found. We present a system called SciSumm that embodies this approach and apply it on a large collection of scientific articles. We evaluate this summarization system for relevant content selection using gold standard summaries prepared on principle based guidelines. Evaluation with gold standard summaries demonstrates that our system performs better in content selection than an existing summarization system (MEAD). We present a detailed summary of our findings and discuss possible directions for future research.

Abstract

3-D medical images such as Computed Tomography(CT), Positron Emission Tomogra- phy(PET) and Magnetic Resonance Imaging(MRI) are commonly used for diagnosis. Tomo- graphic reconstruction is the underlying technique for all these images. It is often of interest to increase the resolution of these images. Some of the possible solutions for increasing the resolution are: increasing the number of detectors, changing the detector material/geometry, increasing the excitation energy level or scanning time. These solutions are limited in terms of practical implementation. Hence, nding solutions at the processing level (post data ac- quisition) is of interest. This thesis focuses on the problem of preserving details and quality of tomographic images after upsampling. We have explored two dierent approaches for generating higher resolution images. These are based on re-examining the lattice geometry for reconstruction. We oer two novel solutions, one which uses a hexagonal instead of the conventional square lattice and a second one based super resolution strategy which combines samples drawn from two lattices. In the rst solution, we reconstruct the image onto a hexagonal lattice. These samples are then interpolated to nd the samples on the desired higher resolution square lattice. In the super resolution (SR)- based solution we reconstruct the images onto 2 low resolution lattices. The lattices are rotated versions of each other which provide a 'dierent view' of an object/scene. For generating low resolution images both square and hexagonal sampling have been considered. The two solutions have been implemented and tested using a variety of test objects. These objects which are called phantoms were chosen to be of 2 types: analytical and real. Three analytically generated phantoms used were Concentric rings, dots and lines. Two real PET phantoms were Nema and Homan Brain phantoms. The results were benchmarked against upsampled images generated by: Direct upsampling and an existing super resolution technique which uses Union of Shifted Lattice (USL) samples. The evaluation results show a qualitative and quantitative improvement over results obtained by direct upsampling. The SR-based results are comparable to that obtained with USL in quality. However, the main strength of the proposed SR-based solution is the computational savings and a reduced number of required images for a given upsampling factor. i

Abstract

Previous works have used word alignments in parallel corpora to transfer information like POS tags, syntactic trees, named entities and word senses from source to target sentences. In this thesis, we worked on the problem of transferring syntactic relations from English to morphologically rich Hindi parallel text. Since the size of the parallel corpus is small and considering the presence of inflectional variations in Hindi pose data sparseness problem. We reduce these complexities to some extent using Local Word Groups (LWGs) and show their effectiveness in simplifying alignments as well as in transferring syntactic dependencies by building an alignment model with LWGs as base units and training a dependency parser on the relations projected using these LWGs. The LWG alignment model using GIZA++ scores decreases the Alignment Error Rate (AER) by 1.16 points when compared to the best GIZA++ model trained on lemmas. We also show that a dependency parser trained on the syntactic relations projected using LWGs obtained statistcal significant improvements over the relations projected using lemmas by a margin of 3.49% in terms of Unlabeled Attachment Score (UAS).

Abstract

The world of academia is growing at a tremendous rate with thousands of research papers being published every year. For a researcher looking for new dimensions of research, it is becoming an increasingly difficult task to identify the relevant yet novel domains of research from amongst the host of varied domains. There is a definite need of a system that could help the researchers in their decision making by interacting with large academic information space. Recommender systems are aimed at performing this very task. They help the researchers to overcome the information overload problem by exposing them to the most interesting results and by offering novelty, surprise and relevance. The ever-changing research fields and the increasing complexity in the relationships within the academia have therefore made such a system an essential tool in a researcher’s quest for expanding his research base. In this thesis, we propose a novel and efficient approach for author and topic recommendation to an author in a bibliographic dataset that exploits the hidden relationships in such datasets as well as addresses the issues of scalability and sparsity. Existing recommender systems largely work by creating a neighborhood of similar users and use their preferences to generate recommendations for the active user. In this thesis, we also rank the items to determine their importance in the dataset and use the ranks of the items of interest for the active user in the recommendation process. Our topic-based author recommendation algorithm aims at suggesting latent yet relevant authors to a researcher based on his research topics. For a pair of authors, their shared research interests as well as the relative diversity between their research interests forms the basis of the similarity measure in our algorithm. The objective of our topic recommendation algorithm is to suggest a set of relevant topics to a researcher based on the research interests of similar authors. The recommendation algorithm considers the importance of a topic as well as the importance of the suggesting authors to assign authoritative scores to the recommended topics. We also exploit the hierarchy of topics and their temporal property to prune the irrelevant topics for the task of recommendation. We test our algorithms on the DBLP dataset. Our experiments produced a ranked set of recommended authors and topics that on examination by field experts and based on our study were found to be relevant and fairly accurate. We study our algorithms on various parameters and validate our experiments by dividing the dataset into training and test portions. We also do a comparative study of our author and topic recommendation algorithms with popular recommendation techniques. We also discuss the system called Research Patterns built to facilitate the accessibility and visualization of the results produced by our algorithms and the possibility of extending our algorithms to other domains. Our algorithms have a host of applications like author and topic recommendation, retrieval of authors for a given topic query and vice-versa, building communities of similar authors, research paper recommendation, etc.

Abstract

The automation of activities in all areas, including business, engineering, science, and government, produces an ever-increasing stream of data. Especially, the amount of multimedia content produced and made available on the Internet, both in professional and personal collections is growing rapidly. Equally increasing are the needs in terms of efficient and effective ways to manage it. And why is that so? Because, people believe that data collected contains valuable information. But, extracting any such information/patterns is however an extremely difficult task. This has led to a great amount of research into content based retrieval and visual recognition. The most recent retrieval systems available extract low-level image features and conceptualize them into clusters. A conventional sequential scan on those image features would approximately take about a few hours to search in a set of hundreds of images. Hence, clustering and indexing forms the very crux of the solution. The state of the art uses the 128-dimensional SIFT as low level descriptors. Indexing even a moderate collection involves several millions of such vectors. The search performance depends on the quality of indexing and there is often a need to interactively tune the process for better accuracy. In this thesis, we propose a visualization-based framework and a tool which adheres to the it to tune the indexing process for images and videos. We use a feature selection approach to improve the clustering of SIFT vectors. Users can visualize the quality of clusters and interactively control the importance of individual or groups of feature dimensions easily. The results of the process can be visualized quickly and the process can be repeated. The user can use a filter or a wrapper model in our tool. We use input sampling, GPU-based processing, and visual tools to analyze correlations to provide interactivity. We present results of tuning the indexing for a few standard datasets. A few tuning iterations resulted in an improvement of over 5% in the final classification performance, which is significant. vi