Abstract

Pipelines are common transportation means for oil and natural gas, which always act as an important lifeline facility for any nation. Generally, these pipelines laid underground for safety and economical reasons. While running through the length and breadth of country pipeline expose to diverse soil conditions. Presently India operates and maintains about 25,000km of gas and other petroleum product pipelines, which are expected to be the double in coming years. Because of major port Kandla and other international ports with refineries at Koyali near Baroda and Jamnagar, western state of India, Gujarat have many major pipeline network which run towards other part of the country and boost up after dreamed Iran Pakistan India pipeline. On the other hand, same region is one of the most seismically active regions (equally like plate boundary region) of the stable continental part of the Indian tectonic plate that has many active faults. Many major pipelines of this region are in vicinity of such active faults e.g. Mundra-Panipat pipeline is in vicinity of the Kachhach Mainland fault. Majority of the sub-ducting Indian tectonic plant’s faults are of thrust in nature hence the pipelines crossing such fault are subjected to compression. Contradictory to this previous work for pipeline fault crossing is done for tension case mainly. Vulnerability of the pipeline due to seismic hazards can be divided in to three categories i.e. hazard due to ground vibration, hazard due to faulting and hazard due to permanent ground deformation (PGD). Though there are no severe damage were observed due ground vibration in the modern buried pipeline. In view of the fact that Indian pipeline network has been developed in recent years and there is no synthetic data of pipeline damage, which is recorded for earlier earthquakes, these notify performance of Indian pipeline as well. Though there are many events of pipeline failure all over the world during past seismic events. In 1971 San Fernando earthquake, over 80-transmission line failures occurred due to shaking and approximately 10 failures occur due to PGD. In 1989, Loma Prieta earthquake has resulted in a program of extensive cast iron pipe replacement using Polyethylene. In1994, Northridge earthquake has lead to 209 repairs to metallic distribution lines and 27 to polyethylene lines. During 1999, Chi-Chi (Taiwan) earthquake 2000mm diameter pipe destroyed by rupture at Chelungpu fault. During 1999, Izmit, Turkey earthquake pipe buckled which was crossing the Anatolian strike slip fault. There are many more acknowledged instances of pipeline damages during an earthquake which includes 1906 San Francisco to recent 2010 Haiti earthquakes. Predominant study for seismic hazard of pipeline started after the 1971 San Fernando earthquake. Newmarks and Hall did the pioneer work for pipeline crossing the fault by assuming pipe as cable model in analytical study to determine the axial strain in the pipe crossing strike slip fault. Numbers of modification were further suggested by many authors in past like Kennedy, Wang and Yeh and recently by Karamitros. However, these models gives satisfactory results for the pipeline crossing strike slip fault under tension but cannot incorporates the large geometric changes. With continuous advancement in computation power and the numerical method recently many researchers are using numerical method to simulate phenomena, which can easily takes care the nonlinear material behaviour. Recently, Takada (1998), LIU (2004) et al are used spring-shell element model to simulate the pipeline fault crossing. However, these models are fine to pipeline but too harsh to the soil behaviour, nevertheless the behaviour of soil has significant impact on the pipeline response. Many analytical models were developed for transverse PGD were pipeline modelled with the assumption of small deformation. For the case of transverse PGD pipeline mainly subjected to the bending. While in case of longitudinal PGD pipeline, expose to the longitudinal tension and compression strains, which is less studied in past. Pipeline subjecting to the large ground deformation itself is a problem of large geometric changes. Especially in case of the pipeline under compression cause to undergo the geometric failure in addition to material failure. Generally, Newton-Raphson technique of nonlinear numerical analysis diverges at snap back and snaps through point. Analysis can be extended by using advance nonlinear techniques like Arc-length method; the same is implemented here for analysis. In this study, more significance is given to the understanding pipeline performance in terms of geometric changes with material nonlinearity. Hence, to reduce the computation efforts and complexity in the analysis it is assumed that bond between the pipe and soil is perfect, which can be added in future study. In this work, a numerical study is carr

Abstract

Security experts often say, users are the weakest link in a security system. Users misunderstand how to use security mechanisms and do not realize the protection and are happy to circumvent the security measures, if security measures try to impede their primary tasks. Attackers on the other hand are experts in usability: they exploit user’s lack of understanding and their tendencies not to comply with security protocols and policies by developing simple yet effective social engineering attacks. Below we explain two main important problems the users are facing in the social networking sites. The first one is identifying between strangers and friends and the second one is adding the people who are interested in the community. Current social networking sites protect user data by making it available only to the restricted set of people often friends. However, the concept of ‘friend’ in social networks is illusory. Adding a person to the friends list without verifying her identity can lead to many serious consequences like identity theft, privacy loss, etc. We propose a novel verification paradigm to ensure that the person who sends you a friend request is actually your friend and not someone who is faking her identity. Our solution is based on what a person might know and can verify about the other person. We work on a premise that a friend can say about her friend’s preferences better than the stranger. The preferences include the interests of a particular person and the big five personality traits 1 . To verify our premise, we did a two stage user study. Results of the user study are quite encouraging. The lifeline of a social networking site is its community relationship model. A community is a group of people having similar tastes, interests and lifestyle. Communities can take the form of an online forum, discussion group where the active participation of a user is required. As of now there is no provision in the social networking sites to measure the interest of the members of a particular community. Inclusion of uninterested users into the community will negatively impact the quality of the community and its activities. Often it so happens that attackers disguised as normal users try to join all the communities even if they are not interested in them. These users

Abstract

Two classes of networks that have been extensively studied in the dynamical analysis of spatially extended systems are: (i) regular networks, wherein each node interacts with a specified number of neighbouring nodes on geometrical lattices, and (ii) random networks, wherein each pair of nodes has a fixed probability of interacting with each other. Recently much attention is being focused on a class of network models that are neither strictly regular nor completely random, but are somewhere in between and exhibit properties of both. Such networks are called small-world networks. Examples for small-world networks are found to occur widely across biological (e.g., neural connection patterns), social (e.g., friendship network, co-authorship) and technological (e.g., the World Wide Web) domains. It has also been observed that a large number of real complex systems such as protein contact networks, protein-protein interaction networks, metabolic networks, exhibit power-law behaviour in their degree distribution, i.e., a few nodes have a very high degree. Such networks are referred to as scale-free networks. To model real physical and biological systems governed by dynamical processes, on such networks the nodes are defined by dynamical systems and the connection between them may be fixed or changing in response to the local dynamics of the nodes, e.g., neuronal excitations. Such networks are called ‗Dynamical Networks‘. Thus, from the point of view of dynamical systems, we have a coupled system of dynamical equations, and we are interested in controlling or manipulating the resulting global dynamics of the system emerging from the interactions between the local dynamics of the individual elements. We propose to use concepts from Graph theory to analyze the coupling structure and its influence in attaining global control of the resulting dynamics in the event of the system exhibiting complex chaotic or excitable dynamics. In an earlier study by Parekh et al, robust control (both global and local) of spatiotemporal dynamics on coupled map lattice (CML) models by applying a constant external perturbation or “pinning‖ has been shown. The advantage of this control approach is that neither any a priori knowledge of the system dynamics, such as stable or unstable fixed points and periodic orbits nor any modification/tracking of the system parameters/variables explicitly is required to suppress chaos. In this study we use the same control approach and analyse the role of connection topologies in achieving global control of the dynamics on small-world and scale-free networks. The analyses have been carried out for dynamics on the nodes governed by (a) logistic map (a one-dimensional nonlinear map exhibiting a wide variety of dynamical behaviour including chaos), and (b) neuron map (a two-dimensional nonlinear map modelling an excitable system, e.g., neuron). The two dynamical systems have been modelled on four different network topologies, viz., regular, random, small-world and scale-free. Since it is practically infeasible to pin all the nodes of the network, here we exploit the geometrical/topological properties of networks to choose nodes for exerting control. We observe that in the case of small-world networks, wherein the connection topology is predominantly local, with a few long range interactions, regularly-spaced controllers provide better control for low pinning densities ~ 20% compared to hubs and other centrality measures which require pinning ~ 50% nodes at similar pinning strengths. The long-range connections only seem to have the effect of spatial noise on small-world network. However, in case of controlling dynamics on the scale-free network, centrality nodes do provide significant advantage in achieving global control. We observe that high-betweenness and high-closeness nodes at very low pinning densities ~ 10 – 15% suffice in suppressing spatiotemporal chaos.

Abstract

Hindi is a morphologically rich, free word order language. Parsing morphologically rich, free word order languages (MoR-FWO) is a challenging task. In this work we present our experiments which lead to state-of-the-art dependency parser for Hindi. We do a series of experiments exploring the role of different morphological and syntactic features in Hindi dependency parsing using two data-driven parsers, Malt and MST. With just 1500 sentences training data, we are able to build a dependency parser with state-of-the-art accuracy of 74.5% Labeled Attachment Score (LAS) and 90.1% Unlabeled Attachment Score (UAS). We also do a detailed error analysis and suggest possible remedies for these problems. During the course of experiments, we realized that some of the basic linguistic constraints were violated by these data driven parsers. We built a linguistically sound parser without compromising on the accuracy. Consider a simple linguistic constraint that a verb should not have multiple karta karakas (roughly, subjects) as its children in the dependency tree. We propose two approaches to handle this constraint and evaluate them on the state-of-the-art Hindi dependency parser. After building state-of-the-art inter-chunk dependency parser for Hindi, we also present our preliminary work on sentence level parsing of Hindi. We extract 1000 sentences, which are word level annotated, from a new multi-layered and multi-representational Hindi Treebank which is being developed. We do a step by step analysis of the importance of different features like, Part-Of-Speech, morph and chunk information for sentence level parsing of Hindi. We could achieve 75.4% Labeled Attachment Score (LAS) and 85.5% Unlabeled Attachment Score (UAS), which is the state-of-the-art performance for sentence level parsing. We also propose an new error detection tool for Treebank validation. Majority of the available error detection tools don’t work for small treebanks, or for the treebanks which are under development. But our tool handles the data sparsity issues and also helps in validation of the treebanks which are being developed. Based on the nature of errors, the proposed tool uses either rule-based or hybrid or both systems to detect errors. We present our results on Hindi dependency treebank data. With our preliminary experiments, we are able to detect 75%, 62.5% and 76.63% of errors in POS, chunk and dependency annotation respectively.

Abstract

Advances in medical device technology have resulted in a plethora of devices that sense, record, transform and process digital data. Images are a key form of diagnostic data, and many devices have been designed and deployed that capture high-resolution in-vivo images in different parts of the spectrum. Computers have enabled complex forms of reconstruction of cross-sectional/ 3D structure (and temporal data) non-invasively, by combining views from multiple projections. Images thus present valuable diagnostic information that may be used to make well-informed decisions. Computer aided diagnosis is a contemporary exploration to apply computers to process digital data with the aim of assisting medical practitioners in interpreting diagnostic information. This thesis takes up a specific disease: diabetic retinopathy, which has visual characteristics manifesting in different stages. Image analysis and pattern recognition have been used to design systems with the objective of detecting and quantifying the extent. The quantitative information can be used by the practitioner to stage the disease and plan treatment, track drug efficacy, or make decisions on course of treatment or prognosis. The generic task of image understanding is known to be computationally ill-posed. However adding domain constraints and restricting the size of the problem make it possible to attempt solutions that are useful. Two basic tasks in image understanding : detection and segmentation, are used. A system is designed to detect a type of vascular lesion called microaneurysm, which appear in the retinal vasculature at the advent of diabetic retinopathy. As the disease progresses it manifests visually as exudative lesions, which are to be segmented, and a system has been developed for the same. The developed systems are tested with image datasets that are in the public domain, as well as a real dataset (from a local speciality hospital) collected during the course of the research, to compare performance indicators against the prior art and elicit better understanding of the factors and challenges involved in creating a system that is ready for clinical use.

Abstract

In Very Long Instruction Word (VLIW) processors, based on the available instruction-level parallelism in programs, compilers schedule operations onto different functional units. By assuming all the functional units of same kind and having the same latency, the conventional list-scheduling algorithm selects the first available (free) functional unit to schedule an operation. But, in advanced process technologies due to process variation, functional units of same kind may have different latencies. In such situation, conventional scheduling algorithms may not yield good performance. Process variations in components like adders, multipliers, etc., of different Integer Functional Units (IFUs) in VLIW processors may cause these units to operate at different speeds, resulting in non-uniform latency IFUs. Pessimistic/conservative techniques dealing with the non-uniform latency IFUs may incur significant performance and/or leakage energy loss. In this work, We propose three process variation-aware compile-time techniques to handle non-uniform latency IFUs. In the first technique, namely `turn-off', we turn of all the process variation affected high latency IFUs. In the second technique, namely `on-demand turn-on', we use some of the process variation affected high latency IFUs by turning them on whenever there is a requirement. Our experimental results show that with these techniques, the non-uniform latency IFU can be tackled without much performance penalty. The proposed techniques also achieve significant reduction in leakage energy consumption as some of the IFUs are turned of. In variation affected situation, conventional scheduling algorithms may not yield good performance. We propose third technique, namely `mobility-list-scheduling' algorithm to schedule operations on non-uniform latency functional units and compare our algorithm with the conventional list-scheduling algorithm.

Abstract

Search engines have become a popular medium for people to fulfill their information needs. Studies on search engines reported a high misspelling rate of queries: around 10-15% queries are erroneous. The detection and correction of spelling errors has become an integral part of computer applications since the very beginning; even before the search engines exist. Research on spelling correction has begun in early 1960s. The research focused on correcting the errors in word processors, specifically where errors occurred in well formed sentences. Search engine queries are very short in length; they have about two to three words on average. Moreover, considerable amount of search queries contain valid but Out Of Vocabulary(OOV) terms. Due to this nature of search queries, correcting search engine queries is more complex than correcting errors in word processors. Research on spelling correction for search engines queries began in early 2000s. But, most of the techniques heavily relied on query logs with the intuition that, People who can’t spell a term correctly can be helped by the people who spell it correctly. Moreover, most of the techniques explored till date depend on linguistic resources, training data or hand crafted rules. In this thesis, we explore ways of correcting spelling errors without relying on query logs or linguistic resources. We focused on correcting two types of errors: 1.Isolated-word errors and 2.Context dependent word errors. Our approach to the above two types of errors is handled using a document collection of a search engine. Our approach addresses correction of isolated-word errors in two steps. In thefirst step, candidate suggestions are generated using an Information Retrieval approach. We explain the reasons for failure of traditional tf-idf (term frequency inverse document frequency) ranking and propose to use df (document frequency) instead of idf in the ranking. In addition, we demonstrate the importance of word frequency in the collection. In step two, candidate suggestions are re-ranked using a new string similarity measure that uses the length of the longest common substrings occurring at the beginning and at the end of the words. We obtained very impressive results by re-ranking candidate suggestions using the new similarity measure. The accuracy of first suggestion is 92.3%, 90.0% and 83.5% for Dutch, Danish and Bulgarian language datasets respectively. The system developed for isolated-word errors is extended to address context dependent errors. In case of context dependent errors; we consider each term in query to be a isolated-word and retrieve candidate suggestions for each of those query terms. Candidate suggestions retrieved for all query terms are used to construct a directed acyclic graph with each suggestion as a node and an edge between suggestions of two consecutive query terms. The longest path, computed by adding the weights of its constituent edges, in the graph yields the best correction candidate to misspelt query. We explore how query expansion and pseudo relevance feedback techniques help in improving the suggestion accuracy of the system. Our approach to context dependent errors obtained a first suggestion accuracy of 75.6%, 80.5% and 85.5% for Bulgarian, English and Dutch language data sets respectively. In this thesis we show that, search queries can be corrected even without using any query logs. In order to keep track of newly evolving words we rely completely on document collection of search engine. Moreover, we demonstrate that, tf-df ranking works better than tf-idf when dealing with character n-grams. The results prove that pseudo relevance feedback techniques can be of great help while correcting the spelling errors in search queries.

Abstract

The amount of textual and multimedia information on world wide web has been increasing many folds every year. A user seeking information on the web is often overloaded with colossal amount of related documents by search engines and information retrieval systems to satisfy his information need. In this context, it has become increasingly important to develop information access systems that provide focused and precise answers to the user. Text Summarization is a popular information access solution for information overload problem. Internet allows its users to follow any popular and temporal topic on web. A temporal topic has a lot of publishing sources and the user cannot handle with the huge amount of raw information from news aggregators, blogs. In such scenario it is not sensible to wait for the topic to complete to produce a summary, nor does it make sense to produce an overall summary at every time interval. In this thesis we study a variant of text summarization, “Progressive Summarization”, focusing only on relevant and novel information, and produce an informative, non redundant summary of the topic. We provide progressive summaries at regular time intervals that helps in updating the user knowledge about the topic. In this work we focus only on extractive methods of summarization, where only the text units from document collection are used in producing a summary. Sentence is considered as a basic text unit for the summary. Extractive summarizers generally follow a sequential framework, that include Pre-processing of text for sentence boundary identification and extraction, a Feature Extraction stage where several statistical, linguistic and heuristic models are employed to estimate sentence importance, Sentence Ranking stage that estimates sentence importance through weighted linear combination of the features and finally Summary Extraction, during which a subset of ranked sentences are selected into summary. The most important factor in extracting important items for a progressive summary, is the identification of novel information. Progressive summarization requires differentiating between Relevant and Novel Vs Non-Relevant and Novel Vs Relevant and Redundant information. Since the existing features are successful in capturing only the relevance, We devise multiple new features (NF, NW, HKLID) to capture novelty of a sentence along with its relevance. We build alternative methods to incorporate novelty in conventional summarization framework. We devise a new re-ranking measure, Proximity Re-ranking (ProximRank), that computes the rank of a sentence based on the relevant novelty of its surrounding sentences. We model novelty detection in the context of progressive summarization as an information filtering task. Sentences that possibly contain prior information are filtered out from summary by creating a Novelty Pool (NP). These methods are successfully related to different stages of summarization and evaluated against each other to find the best. In this thesis we also discover the importance of prepositions in determining the salience and relevance of a sentence to the topic. Also, we use a machine learning technique (Regression) to estimate sentence importance from its feature vector. Thus we overcome the problem of determining ideal weight combination that takes ample amount of experiments and human judgment when several features are used. The techniques described in this thesis are used in building a progressive summarization system (Siel 09) that outperformed all other 43 participating systems in Text Analysis Conference (TAC 2009) in manual evaluations.

Abstract

Coloring is an abstraction for partitioning a set of objects into a few independent sets. The notion of independence and the associated coloring rules vary from context to context. In the simplest case, adjacent vertices in a graph are required to receive different colors ( proper coloring). In parallel scientific computing, a proper coloring is used to identify computational subtasks that can be performed concurrently. A proper coloring of vertices of a graph G is acyclic if every 2-colored subgraph of G is acyclic. The acyclic coloring problem arises in the context of matrix partitioning for the estimation of the Hessian matrix associated with numerical optimization problems. The smallest number of colors required to acyclically vertex color a graph G is called its achromatic number and is denoted by a(G). Finding the achromatic number, a(G), of a graph(G) is an NP-hard problem. Several approaches have been used to solve this problem. Some researchers looked at finding the achroamtic number of family of graphs such as planar graphs, planar graphs with large girth, 1- planar graphs, outerplanar graphs, and d-dimensional grids. Another direction of study is finding upper bounds on a(G) in terms of the maximum degree of G. Alon et al. used problabistic arguements and showed that it is possible to acyclically color any graph of maximum degree D , with O(D^{4/3}) colors. Fertin et al. designed a polynomial time algorithm to find upper bounds on a(G) in terms of D. This thesis is dedicated to designing deterministic algorithms to reduce upper bounds on a(G) for bounded degree graphs. By extending/generalizing ideas of Skulrattanakulchai we reduce upper bounds for a(G) for family of graphs of maximum degree five from 9 to 8 and, for the family of graphs of maximum degree 6 from 15 to 12 respectively. We show above result by extending a partial coloring by one vertex at a time. Let v be the vertex that we color during an iteration. During this process, in some scenarios it is required that we recolor some of the vertices already colored so as to make a color feasible for the vertex v, the vertex we try to color. However, note that this recoloring, if required, is limited to the neighborhood of the neighbors of v in all cases. We have presented a polynomial time algorithm to acyclically color the vertices of graphs with maximum degree D using D^2+2D+2/3 colors. The algorithm improves the state-of-the-art by a factor of 3/2 to the best known result till date. Our algorithm is greedy, and at each time we observed up to 3-neighborhood of a vertex even though recoloring is done up to 2-neighborhood of vertex.

Abstract

In recent times the discovery of several ncRNA (non coding RNA which does not code for proteins but directly performs structural and catalytic functions) genes have drawn progressively greater scientific attention to RNA studies and drawn renewed attention to the hypothesis of “RNA world” where RNA potentially has served the dual role as both the genetic material and as the principal biocatalyst. The non covalent interactions, which are responsible for folding of highly flexible and negatively charged sugar phosphate backbone of RNA molecules are far less understood, compared to those involved in protein folding. These interactions are relatively more complex than in regular DNA double helices, which are held together by canonical A:T and G:C Watson-crick base pairing, which is suited for structure and function of DNA molecules. In contrast, single stranded RNA molecules display a richer variety in base pairing patterns, which govern their folding on themselves into complex dynamic structures. Non canonical base pairs, which constitute ~ 40% of base pairing interactions in RNA (Leontis et al, 2001) have been recognized for their role in molecular recognition including proteins, ligands and metal ions and mediating numerous tertiary interactions. (Westhof et al, 2000) High concentration of charges has long since been identified as one of the major features distinguishing nucleic acids from proteins, in terms of their structure, activity and folding dynamics. Neutralization of the negatively charged backbone phosphate groups, involving metal counter ions, has e. g., been shown as one of the primary events in RNA folding in vitro.(Misra et al, 2003) However, there is now a growing acceptance of the fact that, apart from phosphates and metal cations, the nucleobases themselves can acquire charges through protonation. This development indicates a major change in paradigm, particularly with respect to the role of metal cations in nucleic acid folding and catalysis. It may be noted in this context, that the role of nucleobase protonation in nucleic acids goes much beyond general purpose neutralization – something which the metal cations ubiquitously perform. Several studies have pointed towards more specific roles, including the mediation of global conformational changes in DNA as well as in RNA structures, whereby the protonation of nucleobases in specific macromolecular contexts may be important for defining their catalytic roles and folding pathways. In general, nucleobases do not get protonated at physiological pH, since the pKa values for imino nitrogens are ~ 3.5 and 4.2 for adenine and cytosine respectively, and ~9.2 for guanine and uracil. (Saenger, 1984) It is thus important to understand the basis of context dependent pKa shift which leads to protonation of nucleobases in different cases. Based on their occurrence contexts and functional features, protonated nucleobases identified in known structures have been divided into two classes, (Bevilacqua et al, 2005) viz. Class I, for which the loaded proton is sequestered in hydrogen bonding between paired bases, and class II sites, where the proton is not directly involved in base pairing. Of these, we have investigated Class I type of interactions. For the detection of these base pair types, we have extended available methods (Das et al, 2006) of base pair detection for detecting putative protonated base pairs and understand their contexts. We have also used advanced quantum chemical methods, both to confirm their occurrence as well as to study their geometries and stabilities. We have used a non redundant dataset of selected highresolution RNA crystal structures (PDB ids given in Appendix) from Protein Data Bank (PDB) to analyze the geometries and analyze the occurrence contexts of base pairs belonging to protonated base pair. Out of twelve RNA base pair geometric families described by Leontis-Westhof classification scheme (Leontis and Westhof, 2001), we have identified eighteen possible protonated base pairs spanning eight base pair families. In addition, we also report a putative base pair on the basis of modeling. Out of nineteen distinct possibilities studied in this work, as many as six instances needed hypothesis driven manual intervention for addressing ambiguities; which arouse due to variety of factors , and which were resolved to different degrees using quantum chemical methods. Out of nineteen distinct geometries studied in this work, nine base pairing geometries are new, and not previously being detected in nucleic acid structures. These base pairs have potential to nucleate higher order structures and participate in tertiary interactions joining distant regions in RNA structures. The interaction patterns of protonated base pairs are highly diverse, with gas phase optimized interaction energies in the range from -24 to -49 Kcal/mol. The high interaction energy is generally observed for