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.

Abstract

With the advancement of the internet, more and more content is becoming available in digital form on a regular basis. Such overwhelming amount of available data has lead to the problem of information overload. Various research efforts have been going on to develop improved methods to automatically search and analyze such large amount of information on the internet. Most of the data on the internet is in textual form, hence text mining and text analytics, particularly information extraction has become an active research area in recent years, to extract interesting and useful information. In this thesis, we have made an effort to propose improved information extraction approach for better resume processing. One of the areas of interest in recent years, to both corporate and research community, has been information extraction from resumes. In the current scenario, big enterprises and corporations receive thousands of resumes on a regular basis. Currently available techniques or services filter thousands of resumes to some hundred potential ones based on the requirement of the available job position. Since these filtered resumes are similar to each other as per the filtering criteria, they have to manually look through each of the hundred resumes to select the appropriate candidate for the job. Hence, there is a need to automatically extract data from resume and mine information from it to help in selection process. We have investigated the problem of resume election from set of similar resumes and proposed an efficient framework to solve the same. We have extended the notion of special features employed in product selection environment and proposed improved information extraction approach for resume processing. A special feature is a feature of a given product which distinguishes it from other products. Normally a resume is a semi-structured document and contains sub-sections. Each sub-section contains information in different format. For example, the skill information exists as a set of skill names whereas experience section contains a paragraphs describing different types of jobs/projects. A resume may have specialty in skills and specialty in experience. We have made an effort to extract special features from the resumes and have proposed approaches to extract special skills and special experience. At first we improved the special feature extraction algorithm and extended it to skills sub-section of the resume. To extend the notion of special features to experience section, we first proposed a short-text labeling agorithm and used the proposed algorithm to label each paragraph for capturing the nature of experience. Next, we used the labels as features and find special experience information and organized the labels. We have performed experiments on real world data-set of resumes and obtained encouraging results. Overall, information extraction from resume is a complex task. Even though several products are available, not much related work is available. The proposed work is a part of initial effort.

Abstract

The genome of eukaryotes is packaged in the form of chromatin where DNA is coiled around nucleosomes. The cell type specific complex packaging of genome and regulation of gene expression is established by several factors like histone variants, post translational modification of histone tails and DNA methylation. The higher order genome packaging is established, interpreted and also recreated dynamically by several transacting protein and RNA factors. The interpretation and establishment of these events are also associated with the non coding functional elements like enhancers, repressors, boundary elements, hormonal and environmental stress response elements. The complex packaging of genome and differential expression of genes has evolved from yeast to human. During this process the number of protein coding genes was expanded to a lesser extent compared to the non-coding part of the genome. The evolution of complexity is parallel with two aspects of genome evolution. The expansion of the non-coding portion of genome from lower to higher organisms and also the protein and RNA factors that are associated with the non coding functional elements involved in genome packaging and regulation. We studied two such factors, Polycomb protein which is involved in maintenance of genes in silent state and Simple Sequence Repeats which are shown to be essential for genome organization and regulation.
Polycomb group (PcG) proteins maintain expression pattern of genes set early during development. Although originally isolated as regulators of homeotic genes, PcG members play a key role in epigenetic mechanism that maintains the expression state of a large number of genes. Polycomb (Pc) is conserved during evolution and while invertebrates have one Pc gene, vertebrates have five or more homologues. It remains unclear if different vertebrate Pc homologues have distinct or overlapping functions. We have identified and compared the sequence of Pc homologues in various organisms to analyze similarities and differences that shaped the evolutionary history of this key regulatory protein. Comparative analysis of these sequences led to the identification of a novel insect specific motif and several novel and signature motifs in the vertebrate homologues. Unique motifs acquired by each homologue have been maintained for more than 500 million years indicating their functional relevance in boosting the epigenetic ‘tool kit’. To support our bioinformatics findings we performed functional characterization of the homologues. Each homologue has a unique nuclear localization pattern indicating the functional diversity among the homologues. The transgenic expression of mouse Cbx2, Cbx4, Cbx6, Cbx7 and Cbx8 in Drosophila showed discrete effects. This study indicates that Cbx7 is the functional homologue of Drosophila Polycomb. Our functional studies on the conserved motifs indicated that the functional diversity of the homologues is achieved through the motifs that are uniquely conserved among each Cbx protein.
Simple Sequence Repeats are the major component of non-coding region of the genome. We studied the distribution of 501 possible perfect SSRs from monomers to hexamers. The genome sequences of 19 different organisms ranging from E.coli to human were analyzed. We observed a selective enrichment of repeats specific to eukaryotes, while some are enriched in lineage and some in a species specific manner. Some SSRs have unusual enrichment of longer size repeats in vertebrates. We also analyzed SSRs distribution in the context of different functional compartments of the genome and we found that ACG and CCG repeats are enriched around transcriptional start site (TSS). Selective enrichment of a minority of SSRs in lineage and species dependent manner indicates their association with evolutionary conserved factors and indicates that these elements are evolving like any other functional element. Our study helped us to understand the evolution of factors associated with complexity.

Abstract

Abstract Window in a building provides daylight, ventilation and the outside view. A well designed fenestration system usually provides sufficient daylight during the day but there is a problem of glare and heat. Usual glare control strategies deploy blinds or curtains which are not automated and these systems block the outside view when they are controlling the excess daylight. Emerging technologies such as electrochromic windows satisfy the purposes of glare protection and clarity of outside view but these systems are expensive. The developed system which is a multiple film based daylight control system for window is a cost effective solution which has been developed to maintain the illuminance level at task plane without blocking the outside view and to achieve energy saving by utilization of natural light. The developed system consists of three tinted films with visual transmittivities (Tvis) of 0.50, 0.20 and 0.02 which are stitched together to form a long sheet rolled over two motorized rollers mounted on top and bottom of window. This sheet operates in synchronization with a 2x55W dimmable compact fluorescent lamp (CFL) fixture place above the task plane. The system works on the principle of feedback control, which records the changes in light intensity on the task plane with the help of photo sensor placed on the ceiling, facing the task plane and accordingly adjusts the film-position as well as the control voltage of dimmable CFL to maintain the task plane illuminance within a tolerance of -10%, +25% of set point. Optimized use of solar illuminance saves energy used for the task lighting for the period from 8:00 to 19:00, which was found to be about 70% without occupancy sensor and 80% by using mobile phone as occupancy sensor. The experiment has been performed to work out practical problems and refine design to increase acceptability of the system for real-world applications. As the sheet is in between the two pans of the double glazed window by using reflective films, the amount of heat entering the room can be reduced. The corresponding results were calculated by developing a simulation model of proposed system. Along with HVAC energy savings, annual energy savings were calculated by simulation method. The simulation shows that developed system improves the total energy consumption. Overall, the developed system is a cost-effective solution for smart fenestration systems which not only provides dynamic sunlight control with glare reduction but also saves energy.This thesis report describes the design, implementation of the proposed system and the preliminary results for task light illuminance and energy savings achieved in laboratory setup. Also, it discusses the annual savings achieved due to use of proposed control system with the help of simulation results. Keywords: Daylight control, Dynamic envelope, Energy saving, Fenestration, Multiple film