Abstract

Visual representations are ubiquitous in modern day science textbooks and have become an object of much research in recent years. Since textbooks are a primary source of content information in most science classrooms it is therefore particularly important to understand how students integrate words and figures in textbook style learning materials. The quality and utility of visual representations has been subject to much debate. In order to improve design of the instructional material visual representations which make up one third to one half of every page in a science textbook need to be studied in greater depth so that the these visual representations are productive to the learning of scientific ideas.
The research in this dissertation is centered on three parameters of visual representations. The text that is present within visual representation, and how color plays a vital role in information recall. The second parameter studied is the various categories of the visual representations and their effect on different types of learning outcomes. This study focuses on what type of visual representation should accompany the text so that it provides the best support for the learning of scientific ideas. The third study focuses on the placement of the visual representation with respect to the corresponding text. Studying the text –illustration proximity to find out if learning outcome is effected by the placement of the visual representation helps provide insight about learning behaviors and leads to an improved design of instructional material. The results from the three empirical studies help provide useful recommendations to instructional material designers. Modest modifications in the ways that visual representations are presented in textbooks could greatly improve students’ comprehension.

Abstract

Severe Acute Respiratory Syndrome is a respiratory illness that affected more than 8000 patients and caused around 774 deaths in 26 countries, within its first year of emergence. This disease has an average mortality rate of 10% and is caused by an enveloped, single-stranded positive sense RNA (Ribose Nucleic Acid) Corona-virus (Co-V) known as Severe Acute Respiratory Syndrome Corona-virus (SARS-CoV) that has the capacity for human-to-human transmission. In April 2003, the genome of this virus was completely sequenced. The 29.7 kb long genome reveals that the SARS-CoV bears no resemblance to any existing corona-virus, and contains 14 putative open reading frames (ORFs) out of which 6 major ORFs encode the two replicase poly-proteins and four structural proteins; the spike glycoprotein, envelope protein, membrane protein and helical nucleocapsid protein, and the remaining 8 ORFs for unknown proteins. Though the lifecycle of the SARS-CoV is believed to follow that of other corona-virus i.e., release of genetic material into the cytoplasm of the host cell where it directs the production of new virus genetic material and virus proteins, the exact steps and details of the proteins involved are largely unknown. Identification and characterization of new functional proteins from the ORFs will be helpful for understanding the pathogenesis of SARS-CoV. Up till now there are no effective drugs or vaccines against SARS-CoV. The identification of new viral proteins and the understanding of their functions will provide potential targets for design of drugs or vaccines against SARS. The detection of the 3a gene product in SARS-CoV infected cells and in the lungs of SARS patients confirms that the ORF 3a of the SARS-CoV encodes an accessory protein consisting of 274 a.a. that lacks any significant similarities to any known protein. Though the putative full length sequence of 3a protein lacks sequence homology to any other known proteins, topology prediction of 3a proteins based on amino acid (a.a.) sequences suggests that 3a is a type-III transmembrane protein with multi trans-membrane domains. The interaction of the 3a protein with the spike protein suggests that one of the intracellular roles of 3a is to mediate intracellular trafficking of the spike protein in SARS-CoV infected cells. Although the biological role of the 3a protein remains unclear, it is known that 3a also interacts with the membrane protein, envelope protein and genes that are involved in multiple cellular processes. This suggests that the 3a protein functions as both a viral regulatory protein and as a structural protein in infected cells and mature viral particles respectively. Though a contemporary work showed that 3a is a trans-membrane protein that is capable of forming an ion-channel, the exact structure or the process of homo-merization is unknown. The functions of ion-channels vary among one another and a deeper understanding of the ion-channel activity of 3a proteins will help in elucidating its role in viral lifespan and pathogenesis. Further studies on modulation of virus release mediated by 3a protein will provide new prospects to the understanding of the pathogenesis of the SARS-CoV (and other corona-viruses) as well as can serve as a potential target for therapeutic developments. Protein modelling studies have been carried out on the 3a protein. Three-dimensional structures were modelled from the primary sequence of the 3a protein and then evaluated based on non-bonded interactions, RMSD calculations and solvent accessible surface area computations. These studies help in understanding the possible structure of 3a and its ability to function as an ion-channel. The reliability of the structures was also evaluated using graph spectral analysis (Generally mutation studies are conducted on individual amino acids to identify the critical residues that significantly contribute to the structure and thus function of the protein). Centrality measures of a vertex (i.e. amino acid residue) helps in determining the relative importance of a vertex within the graph (protein structure). Degree centrality, betweenness, eigenvector centrality and graph density were calculated for the proposed models to understand their compactness and to identify the critical residues within a model and common to all models. These critical residues can serve as sites for drug targeting.

Abstract

Present day computing systems deal with calculations involving large range of numbers. One of the ways by which such a wide number range can be provided is through the use of floating point format for number representation. Among the floating point operations, floating point multiplication has been a very power hungry operation, having the maximum share in the power consumption in most of the applications. With the advent of mobile devices which have a fixed power budget, there is a need for investigation of low power designs for a floating point multiplier to trim down the power consumption of the whole system. The work presented in this thesis aims at exploring techniques which can be used to reduce the power consumed in a single precision floating point multiplier. We apply a combination of truncation and voltage scaling in the mantissa multiplier to achieve power savings and implement redundancy in the exponent calculation to attain error resilience. With the scaling of technology and the supply voltage of CMOS transistors, it has been predicted that noise will affect the correct functioning of circuits in the future technology nodes. This will lead to computations which may not be deterministic but probabilistic. In such a scenario, the technique of voltage scaling will lead to increased errors due to further reduction of the noise margin. One of the methods by which the effect of the reduced noise margin can be modeled is through introduction of random or Gaussian noise along with the signals. This noise introduction results in erroneous calculation which is referred to as probabilistic computation in this thesis. Each of the low power techniques used (truncation and voltage scaling) lead to power savings at the cost of errors in the computations. Hence, we apply these low power techniques in the mantissa calculation of the floating point multiplier because it is less significant as compared to the other calculations (exponent and sign) and is also the most power consuming calculation of the floating point multiplier. This is done to achieve maximum power savings at the cost of introducing some errors as far as the multiplication result is concerned. We also make the exponent calculations less error prone by implementing redundancy in the exponent block. This leads to substantial error reduction with very nominal increase in power, thereby keeping the overall error in the results low. By the low power techniques and redundancy we realize a multiplier design with error tolerance and considerable power savings. It is then demonstrated that sizeable amount of power savings can be achieved in a Ray Tracing application by replacing a subset of the deterministic multiplications by probabilistic multiplications. This was achieved at the cost of negligible degradation in the quality of the output image generated.

Abstract

Computational Geometry has grown into an independent field in the last two decades. It deals with design and rigorous analysis of sophisticated algorithms for problems which involve geoemtric objects. Apart from trying to come up with efficient algorithms and data structures, a lot of focus is on mathematical analysis for proving the efficiency of the solutions. Computational Geometry problems find a lot of applications in the field of VLSI, Geographic Information Systems (GIS), graphics and databases. In a class of problems named ‘geometric intersection searching problems’ (GISP) orthgonal range searching, halfspace range searching, orthogoanl point enclosure have been some of the most widely studied problems. The inherent beauty in these problems and their applications in various domains have motivated researchers to explore these problems. GISP can be simply stated as follows: Let S be a set of objects in IRd (d-dimensional space). Given a query region q, report or count the number of objects in S q. The objective is to come up with data structures which uses minimal space (ideally linear space) and query algorithms which answer queries fast ! In many applications (which shall be discussed later), it is not sufficient to merely report or count the objects of S intersecting with the query range q. Some form of aggregation (or summarization in some cases) needs to be done on the objects in S q to present the user with more useful information. Range-Aggregate queries are a step in that direction and are the focus of this thesis.A range-aggregate query can be formally defined as follows: Let S be a set of n objects in IRd, where each object p may have a real-valued weight w(p). We would like to preprocess S into a suitable data structure so that for any given query range q  IRd , a certain aggregation function that operates on the objects of S0 = S q can be performed efficiently and output-sensitively. Existing techniques in the literature cannot be directly applied to answer these queries efficiently. Therefore, in each chapter we consider a unique aggregation function and study them in detail. In many applications reporting all the points in S q is not a user-friendly experience since jS qj can be very huge and hence, unmanagable. Therefore, we use the aggregation operator ‘top-k’ to report only the k most significant points based on the weights associated with each point. In many scenarios, the points in S are classified into disjoint groups. We associate a unique color with each group and all the points belonging to that group also inherit that color. Given a query region q, a straightforward query is to report the unique colors of the points in S q. In the range-aggregate versions we considered, additional information would be reported along with each color c such as the point of color c in q with the maximum weight or the sum of the weights of all the points of color c in q. In short, a useful summary of each group is reported. Geometric aggregation functions are relatively more difficult to handle than the regular aggregate functions. We consider some geometric aggregation problems and improve upon the existing solutions in the literature. Finally, we consider a boolean yes or no query asking if jS qj > 0 or not. Though existing structures in the literature can answer this query in reasonable query time and space we made an attempt to further improve them. We come up with efficient data structures and query algorithms to solve these problems. Mathematical analysis is done to show the efficiency of our solutions in terms of space occupied and query time. Real world applications of each type of range-aggregate query is explained as well.

Abstract

Text mining is a subeld of data mining that, in turn, is a component of a more general category of Knowledge Management (KM). In the real world, knowledge is represented not only by the structured data found in traditional databases, but in a wide variety of un-structured sources such as books, research papers, word documents, letters, digital libraries, e-mail messages, news feeds, Web pages, and so forth. Text mining is particularly relevant today because of the enormous amount of knowledge that resides in unstructured collection of text documents. It uncovers relationships in a text collection, and leverages the creativity of the knowledge worker to explore these relationships and discover new knowledge. In recent years, we have witnessed a tremendous growth in the volume of text documents available on the internet, digital libraries, news resources and so on. With the dramatic growth of text information, there is an increasing need for powerful text mining systems that can automatically discover useful knowledge from text. The digital data has become one of the most important resources for information. But the fact that more data is available does not necessarily mean that it is being used in ecient manner. It has been observed that no one is willing to or capable of manually browsing through large data collections. To satisfy user's information need, a system should list a precise and small subset of the data collection. People often interact with these document collections and thus may be interested in methods to help them better use the documents or retrieve the useful knowledge. For retrieving individual documents, search engines have already been very successful. Other methods such as topic modeling can provide a coarse overview of the topics in a document collection. While information retrieval and topic modeling methods have been widely applicable and useful, current methods for drilling deeper to understand the structure and development of research areas in terms of topics and their relationships with each other and their originating documents for each of those topics in a corpus as a whole could still be improved. In this thesis, we provide methods for a set of tasks that seek to identify the important or new keyphrases and corresponding rst originating document, known as Landmark Paper. These methods focus on supplying a ne-grained picture of development of keyphrases over time to help users grasp the keyphrase collection's development as a whole. We focus on the problem of nding novel keyphrases within the document collections, and their originating documents through the multiple conferences with respect to the conference year. In addition to this, we also consider that it is insucient for new researchers who are exploring a research area. It is much more helpful to be able to see the related research areas based on proximity and importance of keyphrases and their originating documents. We investigate the system where the user can enter a set of keyphrases and the system recommend a set of top k - keyphrases by using knapsack approach, corresponding to the user's query and also show the relationships of these topics to each other and nally outputs the landmark paper for each of those topics. This will essentially provide all the material required for the researcher to exhaustively understand the foundations of that research area. This thesis explores text-based approaches for these tasks. For wide applicability, the methods use only document text. We evaluate our methods experimentally on actual research publications from the dierent Data Mining and Databases conferences proceedings available on the Digital Bibliography Library Project (DBLP) website1. We have prepared a cleaned-up dataset with the text proceedings to conduct this evaluation. In addition to the above tasks, we have develop an approach by using knapsack based solution as discussed above in a dierent domain i.e. to recommend set of items to the customers in retail stores such that the prot of the store is maximized.

Abstract

The present day world is becoming more and more information based. At present, the data which is generated and stored at a rapid rate has exceeded the human comprehensibility and also, there is a huge amount of information stored in the databases which is potentially important and needs to be discovered. The process of extraction of previously unknown and potentially useful information from large data sets is known as data mining. It is considered as an increasingly important tool to transform data into useful information giving an informational advantage. The data which is associated with the time at which it is generated is known as the time series data. It captures the characteristics of events with respect to time. Recently, analyzing time series data has acquired prominence as many of the real world phenomena deal with time series data. In addition, time series data is a valuable resource for many business organizations and financial markets. Furthermore, several emerging applications in the information providing services, such as on-line services and the World Wide Web call for various data mining techniques to better understand the user behavior to increase the business opportunities. In recent times, data mining is used in several domains like natural sciences, environmental study, network monitoring, genomics, financial markets study. In this thesis, we have made two contributions, we proposed an approach for the efficient placement of the banner advertisements for a web site by analyzing the click stream data generated by the web site visitors. In addition, we proposed a framework to identify the changes in the suitable crop cultivation period over the years by analyzing the past temperature values of a region. E-commerce, web services as well as online advertising can greatly benefit from the insight gained from knowledge discovery of transactional data which include click streams. In an online banner advertising scenario, an advertiser expects that his/her banner advertisement should be displayed to a certain percentage of web site visitors. In this context, to generate more revenue for a given web site, the publisher has to meet the demands of several advertisers by providing appropriate sets of web pages. To help the publishers and advertisers, in this thesis, we propose a model of coverage patterns and a methodology to extract the potential coverage patterns by analyzing the click stream data. Given web pages of a web site, a coverage pattern is a set of web pages visited by a certain percentage of visitors. The proposed approach has the potential to enable the publisher in meeting the demands of several advertisers. The experimental results indicate that the proposed approach is efficient and practical from both publisher and advertiser’s perspective. In the area of crop production, the crop is cultivated in a certain time period in a year based on the favorability of weather conditions. However, in the recent years there is ongoing debate about the climate change and also its impact on crop productivity. In general, the crop productivity is influenced by weather factors like rainfall, humidity, wind velocity, solar radiation and temperature. Temperature is one of the important factors. For any crop, its productivity is influenced by fluctuations in the temperature values during its cultivation period. In this thesis, an effort has been made to propose a framework to understand the changes in the suitable time period for crop cultivation by analyzing the temperature data. For this, we have introduced a notion called penalty matrix which contains penalty values. A penalty value indicates the negative effect on the crop productivity for the given temperature deviation. Using the proposed framework, we have reported some observations by computing suitability score for the rice crop for two regions by assuming the penalty values. The proposed framework is generic and can be used for any crop and region.

Abstract

The World Wide Web (WWW) is a huge, widely distributed global source of information to web users. Web documents are broadly classified into: unstructured and structured documents. Users prefer structured documents when looking for a piece of information. Hence, in the past decade research community focused on mining structured information from unstructured documents and attempted to preserve them in the form of attribute-value pairs, tables, flow charts etc. But, the focus has been only on extracting information at document level or on particular domains like disaster, finance, medicine etc. The techniques never attempted to integrate the extracted information to common knowledge repositories like Wikipedia, DBPedia etc. Structured databases like Wikipedia, DBPedia etc are created through collaborative contributions from volunteers and organizations. Since they rely heavily on manual effort, the process of updating these databases is not only tedious and time consuming but is also fraught with many drawbacks. Hence, automatic updation of structured databases has become one of the hot topics of research in the past few years. Automatic updation of structured databases can be broken down into two sub problems: Entity Linking and Slot Filling. In this thesis, we address Entity Linking. Entity Linking is the task of linking named entities occurring in a document to entries in a Knowledge Base. This is a challenging task because entities can not only occur in various forms, viz: acronyms, nick names, spelling variations etc but can also occur in various contexts. Once named entities from documents are linked to entries in a knowledge base, information can be integrated across them. Current IE techniques can be used to extract information from documents. Person named disambiguation and Co-reference Resolution are two tasks that share a lot of similarities with Entity Linking. These tasks have attempted to link entities across documents but never attempted to integrate them into a common Knowledge Base. Our approach to Entity Linking begins with building of an Entity Repository (ER). ER contains information about different forms of named entities and is built using Wikipedia structural information like redirect pages, disambiguation pages and bold text from first paragraph. Our core algorithm for Entity Linking can be broken down into two steps : Candidate List Generation (CLG) and Ranking. In the CLG phase, we use the ER, Web search results and a named entity recognizer to identify all possible variations of a given named entity. Using these variations we obtain an unordered list of candidate nodes from the KB which can be linked to the given named entity in a document. In the ranking phase, we rank the unordered list of candidate nodes using various similarity techniques. We calculate the similarity between the text of the candidate nodes and the document in which the named entity occurrs. We experiment ranking using various similarity functions like cosine similarity, Na¨ıve Bayes, maximum entropy, Tf-idf ranking and re-ranking using pseudo relevance feedback. Our experiments show that cosine similarity and Na¨ıve Bayes perform close to state of the art and the Tf-idf ranking function performs better in some cases. Our approach was tested on a standard Entity Linking dataset provided as part of Text Analysis Conference (TAC) for Knowledge Base Population (KBP) shared task. We evaluated our approach using Micro-Average Score which is the standard evaluation metrics. We achieved very impressive MAS of 83% and 85% on TACKBP, Entity Linking 2009 and 2010 data sets, which secured top spot in these shared tasks respectively.

Abstract

Real-life city-traffic simulation presents a good example of multi-agent simulations involving a large number of agents (each human modelled as an individual agent). Analysis of emergent behaviors in social simulations largely depends on the number of agents involved (more than 100,000 agents at least). Due to large number of agents involved, it takes several seconds or even minutes to simulate a single second of real-life. Hence, we resort to distributed computing to speed-up the simulations. We used Hadoop to manage and execute multi-agent application on a small cloud of computers and used CUDA framework to develop an agent-simulation model on GPUs.

Abstract

In the internet environment, computers-based information systems are being employed to maintain large amounts of information to meet different users’ information requirements. The users interact with the system by inserting/updating/querying the required information. The information systems process the user requests by executing the update transactions (UTs) for inserts/updates and readonly transactions (ROTs) for queries. An ROT contains only read operations whereas an UT contains both read and update operations. Processing of ROTs in a correct and efficient manner is a research issue. Efforts are being made in the literature to propose improved approaches. The main issues in processing ROTs are correctness (serializability), ensuring data currency and high performance. Even though the popular two-phase locking (2PL) protocol processes ROTs correctly with no data currency related issues, its performance deteriorates with data contention. Snapshot-based algorithms have been proposed to improve the performance by compromising both data currency and correctness aspects. Recently, two speculative locking-based (SL-based) approaches have been proposed in literature for improving the performance of ROTs. In these protocols, UTs are processed with 2PL and ROTs are processed with SL. One is synchronous SL-based approach in which speculative executions are carried out in synchronous manner and another is asynchronous SL-based approach in which speculative executions are carried out in asynchronous manner. Overall, the SL-based protocols for ROTs improve the performance without compromising both correctness and data currency. However, the SL-protocols follow 2PL to process UTs. Under SL-protocols UTs are blocked if they conflict with ROTs. Semantics-based protocols have been proposed in the literature for improving the performance without blocking UTs if they conflict with ROTs. The notion of compensability of ROTs is being exploited to improve the concurrency. The SL-based approached have been proposed by considering centralized database environment. In this thesis, we have extended SL-based approaches for processing ROTs in distributed database system (DDBS). In addition, we have analyzed the performance of semantics-based protocols by considering TPC-C and TPC-W benchmarks. We have extended both synchronous SL-based as well as asynchronous SL-based locking, protocols to process ROTs in DDBS. While extending SL-based protocols, it has been identified that an ROT under SL-based protocols requires an additional commit phase and requires single round of communication. In addition it has been found out that, additional messages are required for making speculative versions available to ROTs during the execution phase of an update transaction. In spite of these overheads, the performance results show that the proposed protocols significantly improve the performance over 2PL and SI-based protocols. Similar to centralized case, the proposed protocols do not compromise both correctness and data currency aspects. The analysis of semantics-based protocol with TPC-C and TPC-W benchmarks has been carried out by identifying various types of conflicts among the pair of transactions in both benchmarks. The analysis showed that six out of the eleven cases are compensatable in TPC-C and eleven out of twelve UT-ROT conflicts are compensatable in TPC-W. The analysis indicates that semanticsbased protocol has a potential to improve the performance in a realistic scenario.

Abstract

Every data set has a story to tell and has a unique set of characteristics depending on various factors like (a) the domain of the data, (b) external factors forcing the data to follow some pattern, (c) data instances, (d) various dimensions and their data types, (e) interactions between the instances and the dimensions and (f) most importantly, the underlying patterns in the data set. Interactions are the various types of relationships that the instances and dimensions share; for instance, similarities, dissimilarities, nearest neighbor relations, or any other semantic relation defined over data instances and dimensions. Various knowledge discovery techniques aim to obtain these characteristics of data or parts of it - by analyzing the data, identifying common patterns (like classes, clusters and frequent itemsets) and anomalous patterns (i.e., outliers). With very large data sets, the summarized characteristics could also be large, in contrast to the small size they should ideally represent. Effective presentation of the summary of data is a great utility for the end-user. The aim of this dissertation is to capture data’s characteristics with the underlying patterns as clusters and outliers. And later, present a visual information thumbnail of the data’s characteristics for the user to analyze and understand the data and patterns. Capturing data’s underlying patterns is achieved with data clustering and outlier detection algorithms based on the concept of reverse nearest neighbors. This dissertation elaborates on the properties and behavior of reverse nearest neighbor sets useful in the process of detecting outliers and identifying clusters. We propose a suite of techniques to: (i) identify candidate outliers, (ii) identify clusters, (iii) identify local outliers, (iv) rank outliers, (v) obtain agglomerative clustering and finally (vi) obtain a stable clustering result. We also propose two cluster validity measures based on proximity graphs to evaluate the “goodness” of the clustering results. Visual information thumbnail is generated by using the results obtained from the clustering algorithm and the subspace data analysis done using nearest neighbors. The information thumbnail incorporates various levels of detail, displayed on-demand to the user.