Abstract

The penetration of Internet over the last two decades has witnessed contributors from all around the world. This has led to a vertical expansion of information in different languages. There has been tools developed to handle content in many languages independently. However, when a user wants to view content from several different languages as a search request, the existing tools doesn’t suffice. Studies reveal that the number of users requesting multilingual information in their search results is on raise. Information Retrieval (IR), is a field in computer science that deals with information available in huge volumes, like on Internet, to retrieve and display the information need of an user. This concept can be extended to the domain of high volumes of multilingual information. When a user requests for an information need in this collection of multilingual information, the task of retrieving the exact information is very challenging. It has inherent issues of structuring the content, to understand the user information need, to fetch relevant documents, to retrieve similar documents from other languages and finally to rank all documents irrespective of their language as per their relevancy to the query. One possible solution is to retrieve a result list separately in each language requested by the user and finally merge them to produce a single multilingual result list. This thesis attempts to solve the problem of merging the intermediate result lists by ranking all documents as per their relevancy to the query irrespective of the language. The task is challenging because merging result lists need the understanding of the content of all documents across languages and ranking them according to their relevancy to the query. Existing several approaches make an extensive use of language resources and tools in achieving this task. However, such approaches are limited across languages, because of their dependency on the resources and tools. Many languages, like Hindi, suffer from the limited availability of the language resources/tools. Developing a language-independent approach is highly crucial for many such languages. The central theme of this thesis is to develop a language-independent approach which is also efficient to merge several monolingual result lists to form a multilingual result list. A learning-to-rank framework is the proposed solution for this problem. In this framework, for every query-document pair a relevance judgment will be given, indicating if the document is relevant to the query or not. Features will be extracted from the content of query and document. Ranking algorithms will be used in training a model so as to assign a relevancy to a new unseen query-document pair. These relevancies are used in ranking multilingual documents. In this thesis, we propose certain simple and efficient features that enhances the performance of ranking. All the calculations are performed without using any language tools. To achieve language-independent approach, several alternative methods have been introduced to replace the usage of existing language tools, like lemmatizer, etc. One of the proposed features involve computing similarity between two different language documents. Comparing multilingual documents is not a trivial task. Bilingual dictionaries are usually used in translating a document before comparing. In this thesis, a new dimension of document representation is explored. Instead of representing documents with words, we attempt to represent documents as a mixture of the topics/themes inherent in the document. Latent Dirichlet Allocation (LDA), a topic modeling algorithm, is availed to achieve that. However, to represent multilingual documents as a mixture of topics, a new mathematical formulation is derived over the existing LDA model, we call it MultiLDA. This MultiLDA model has the potential to be applied elsewhere. Various experiments have been performed to validate each and every concept introduced in this thesis. The results reveal the significance of the proposed solutions.

Abstract

Keyword search is the most popular way to search content on the web, however, in specific applications it might fail to capture a user’s information need. For example, in domains like patents and biomedical text retrieval, a set of keywords as a query may not be sufficient but a document as a query would be more useful. Documents, as a medium to search for information will become necessary in different scenarios such as blogs, posts, resume or related news search. The objective of this thesis is to explore and evaluate models for ”Query by document”, i.e. search a corpus with a document as a query, with their application to the corpus of legal documents. In the legal domain, patent search is a routine task for a patent examiner. Depending upon the search type (invalidity or prior art search), the examiner may have a patent application at hand to find similar patents. Thus, a document, i.e. a patent application is often a starting point to find similar inventions. Presently, the success of patent search relies on the queries created from a patent application by the examiner. Since a lot of time is spent in constructing relevant queries, transforming the patent into a query automatically would save the examiner a lot of effort. We focus on two ways of constructing a query from an input patent application - relying on its text to form a query and using its meta-data (class- information) and information from the corpus (citations) for representing patents and retrieving similar patents to improve retrieval accuracy. We test both the approaches with our participation in CLEF-IP track, where teams investigate information retrieval techniques in Intellectual Property (IP) domain. The empirical analysis of both approaches and their combination indicates that results are best when combination of both approaches is used. The first approach focuses on extracting key phrases from a patent and their weights in the query. This query is then used to retrieve similar patents. Since a patent may contain information that is both diverse and dense in nature, entire content as a query will not be feasible as the results might be noisy and irrelevant. An optimal query can be formed by extracting important keywords, phrases or concepts from a patent by using Key Phrase Extraction (KPE) techniques. Several KPE algorithms have been proposed in the literature but their performance on query construction for patents has not yet been explored. We systematically evaluate and analyze the performance of queries created by using stateof- the-art KPE techniques for invalidity search task. The key phrase extraction techniques are used to construct queries from patents for Invalidity Search task. Experiments on a collection of USPTO Patents show that queries formed by KPE approaches perform better than those formed by selecting phrases based on term frequency based measures - tf and tf-idf scores. At the same time, keyword search for similar patents requires significant domain expertise and may not fetch relevant results. Thus, in the second part of this thesis, we focus on reducing the dependency on keywords, by exploring an alternative representation for patents using only the meta-information present in a patent and its citations. We propose a novel representation for patents and use a two stage approach to find similar patents. Each patent is represented as an IPC class vector. Citation network of patents is used to propagate these vectors from a node (patent) to its neighbors (cited patents). Thus, each patent is represented as a weighted combination of its IPC information as well as of its neighbors. A query patent is represented as a vector using its IPC information and similar patents can be simply found by comparing this vector with vectors of patents in the corpus. Text based search is used to re-rank this solution set to improve precision. We experiment with various similarity measures and re-ranking methods to empirically show that our representation is effective in improving both precision and recall of queries of CLEF-IP 2011 dataset. Large scale evaluation of both key phrase extraction and meta-data based representation of patents was done by participating in CLEF-IP track. The results of proposed approaches were also combined with rule based citation extraction from query patent. We submitted six runs to the track, with two runs achieving significant Recall and highest MAP (Mean average precision) amongst all participants. Results show that the proposed meta-data based representation for patents, combined with queries formed with extracted key phrases from the query patent outperforms the runs with either approach. The results of both the models on large datasets indicates that significant improvement can be achieved if patent text is used with other data like class information and patent citations. We believe that a richer language independent representation could be proposed in th

Abstract

Hindi is an Indian language which is relatively rich in morphology. Few morphological analyzers of this language have been developed. However, they do only inflectional analysis. None of them give the derivational analysis of the language. In this thesis, we present our Hindi derivational morphological analyzer which gives us derivational morphological analysis of Hindi. The construction of the tool took place in three phases. All the three phases are crucial for the development of the tool. The first step in building a derivational analyzer is identifying the derivational variants. The derivational variants in the language must be identified and then they must be studied in order to obtain important properties of the derived words in the language. So the main aim of the first phase was to build a tool for identifying Hindi derivational variants. For this, we followed an approach which was supervised in nature. First, we used 11 productive derivational suffixes of the language which participate only in verb to noun derivations. Then 454 derivational variants of these 11 suffixes were acquired manually. Finally we created an SVM classifier with 7 features. We used the 454 variants as a training data for our classifier. This classifier is a tool meant for identifying derivational variants. A total of 170 derivational variants were identified using this tool. The scope for adding more number of pairs was less. Some of the important features did not influence the performance of our classifier to a great extent. But 11 new suffixes were considered after this phase. These 22 suffixes along with 624 derivational variants formed the basis of our work in subsequent phases. 624 is a small number. Many more derivational variants must be identified for obtaining the rules of the suffixes and other important properties. Even suffixes that participate in other kinds of derivations must be studied. Their derivational variants must also be obtained. Hence in our second phase, our main aim remained identification of Hindi derivational variants. We used a graph based approach for achieving the goal. This approach is unsupervised in nature. We used the three metrics of semantic relatedness, phonological similarity and suffix presence for identifying the derivational variants. First, we built a graph based model and incorporated these three metrics in that model. This model was built using resources like Hindi Wikipedia and C++ boost graph libraries. As the last step, we ran the page rank algorithm on the graph model for identifying the derivational variants. A total of 2800 derivational variants were identified in this phase. So a total of 22 derivational suffixes and 3000 derivational variants were obtained from the first two phases. Now the final step is to provide derivational analysis. This is the aim of the third phase. The properties of these 22 suffixes and their derivational variants were studied. An algorithm was designed using the results of this study. The algorithm used by us upgrades an existing inflectional analyzer to a derivational analyzer. Our algorithm primarily achieves two goals. First, it successfully incorporates the derivational analysis in the inflectional analyzer. Second, it also increases the coverage of the inflectional analysis of the existing inflectional analyzer. Finally, the goal of building a Hindi derivational morphological analyzer was accomplished in 3 phases.

Abstract

Question Generation is the task of generating questions from various inputs such as raw text or semantic representations. It is an attempt towards structuring the potential educational text which is available everywhere on the Internet. Generating questions manually on these large amounts of varied text is a tedious task. Hence, there is a need for generating questions automatically from these texts. The present work generates questions automatically from a given document. The aim is to build a system which can be used for different domains in various languages. Questions can be broadly classified into Subjective Questions and Objective Questions. The work mainly focuses on generating two types of objective questions, (i) Cloze Questions and (ii) Open-cloze Questions. To present the method, English language texts have been used. A cloze question contains a sentence with one or more blanks in it and four alternatives are given to fill those blanks. One of the four alternatives is correct and the others are wrong. The wrong alternatives are called distractors since they distract a student from choosing the correct answer. Cloze question generation is a three stage process, (i) Sentence Selection, (ii) Keyword Selection and (iii) Distractor Selection. In the presented system, all the three stages use heuristically weighted features to select relevant sentences, keywords and distractors. Finding three relevant distractors corresponding to each selected keyword is the most difficult task. Therefore in the next attempt, a rule based open-cloze question generation system has been developed. Open-cloze questions are similar to cloze-questions without alternatives, which make them more difficult to solve. As it is difficult to evaluate the quality of questions generated automatically, this work also provides guidelines for the manual evaluation of automatically generated cloze and open cloze questions. The present work generates questions that assess the content knowledge that a student has acquired upon reading a text rather than vocabulary, grammar assessment or language learning. There are only a few previous works under the area of QG, and this is the first attempt ever to generate cloze and open-cloze questions on content knowledge. Hence, a comparison between this system and the previous systems using a common dataset will not fetch any results. However, different individual stages of this method have been compared with previous approaches. In the comparison, it has been shown that the presented method covers more types of sentences to generate good quality questions. In addition, the method does not use any external resources unlike previous works and that makes it both domain and language independent.

Abstract

Modelling and simulation of a robot on uneven terrain is of importance as it provides a basis to know about the robots position and its state. In this work we present a simulation framework and dynamic state space realisation for evolution on uneven terrains for a wheeled mobile robot such as a synchronous drive robot. The framework lends itself as a tool capable of solving various problems, such as forward kinematic based evolution, inverse kinematic based evolution, path planning and trajectory tracking. This framework becomes particularly useful when we understand that the evolution problem (and hence the various associated problems based on evolution) is particularly challenging on uneven terrain. Specifically it is entailed to bring in the contact constraints posed by the interaction of the wheel and the ground as well as the holonomic constraints as the problem is formulated in a DAE setting (Differential Algebraic Equation). The problem becomes all the more crucial as vehicles moving on uneven terrain are becoming the order of the day. Nonetheless there has not been much literature that deals in length the various aspects that go into the framework. This work elaborates on the various aspects of the framework, presents simulation results on uneven terrain, where the vehicle evolves without slipping and also presents substantial quantitative analysis in regard to wheel slippage. Dynamic model which ensures no slip and permanent contact on uneven terrain and which satisfies holonomic and non holonomic constraints simultaneously is also proposed. For a 3 wheeled WMR a generalised state space is derived and is used to find the dynamic equations of motion as a second order constrained Differential Algebraic Equations (DAE). Dynamic equations are represented using lagrangian formulation where all the matrices and constraints are represented in the generalised state space representation. Constraint satisfaction is achieved by using Baumgarthe stabilisation for the equivalent second order holonomic and non holonomic constraints and in calculating the Lagrangian multipliers as part of the DAE which is unique. The main contributions of the thesis is to realise a system for uneven terrain navigation and to simulate it using both kinematic and dynamic equations to get feasible paths on uneven terrains.

Abstract

Crystal structures of drug molecules complexed with their target RNAs are being widely studied today, particularly in the context of the importance of the ribosome as a potential drug target, and the notable discriminatory ability of recognition and binding of cognate ligands by RNA aptamers. However, the molecular level understanding of the role of ligand binding interactions in RNA functions, require the analysis of stabilities and interaction energies of RNA-drug interactions. The present work deals with a detailed analysis of the structural and energetic features of these drug-nucleobase pairs and pseudo pairs using quantum chemical methods.
Previous studies on RNA base pairing interactions have demonstrated that gas phase quantum chemical calculations can be used to analyze the intrinsic stabilities of non-covalent interaction in RNA. In line with these studies, here we report the results of analysis of geometries and interaction energies of base pairs and pseudo pairs observed in experimental structures of different classes of drug molecules interacting with RNA, which include aminoglycosides, oxazolidinones, tetracyclines and lincosamides. Geometry optimizations of studied nucleobase-drug pairs have been carried out at B3LYP/6-31G (d,p) level, while the interaction energies have been evaluated at the RIMP2 (using aug-cc-pVDZ and RIMP2/aug-cc-pVTZ basis sets which has been further extrapolated to CBS limit), DFT and DFT-D (using TPSS functional and aug-cc-pVDZ basis set). Further, interaction energy decomposition has been carried out using Morokuma method performed at the HF/6-31G (d,p) level. Our studies show that on full geometry optimization, these pairs tend to achieve greater stability compared to that in their respective experimental geometries. The gas phase interaction energies of RNA-drug pairs compare well with those of standard Watson Crick base pairs. Except for the Puromycin - Guanine pair involving sugar edge-sugar edge interaction, the Hartree Fock component dominates the interaction energies in all fully optimized geometries. The comparison of EDFT and EDFT-D interaction energies suggest that the interaction between the RNA-Drug pairs is further stabilised due to dispersion.
In context of RNA-drug interactions involving multiple bases forming base pairs with single drug molecule, we also report detailed studies on the discriminative ability of the theophylline RNA aptamer with respect to its cognate ligand. Unlike in the context of purine riboswitches observed earlier, cooperativity between different RNA-base pairs is found to be negligible in multiple base-ligand interactions studied in case of Theophylline interacting with its aptamer. In addition, the binding affinities of theophylline, caffeine and theobromine with the theophylline aptamer correlates well with the experimental data with high binding affinity for theophylline and least for caffeine.

Abstract

Information explosion on the internet popularly known as the web has led to a phenomenon of the user unable to find the information relevant to him or her. There is plethora of information available and thousands of pages are being added everyday. Hence more and more information is available on each and every subject. Hence, it has become increasing difficult for users to remain up to date on one’s own areas of interest. This has increased the need for indexing of documents drastically. Indexing can take place at the user end or at the search engine end. However traditionally, indexing used to take place at the middle level by authorities or librarians. With the vast amount of content available on the internet, it is practically impossible for any authority to index the data. This led to the evolution of social bookmarking systems where users are able to maintain individual collections of resources and index them using tags for retrieval purposes. This model has evolved into a collaborative model where users share their resource collection and tags with others leading to the emergence of collaborative tagging systems. These systems are also referred to as “Folksonomies”. Due to the flexibility and ease of use, the usage of these systems has increased very rapidly. Many tagging systems like Delicious, Flickr, Bibsonomy, Citeseer etc. have evolved and became very popular. This has created a new form of rich user generated content which can be exploited to good use in a wide range of applications. The data in these systems typically consists of three dimensions - resources, users and tags. In this thesis, we have focused on some of the basic metrics for extracting information from folksonomies - Tag weight and Tag similarity and the usage of them in applications like Tag Search and Web document summarization. First, we propose a model of tag weighting extending the traditional Vector Space Model for term weighting. We show how tag weighting can be used in tag similarity and also show how we compute tag similarity. We evaluate our proposed tag similarity measure by grounding them against semantic lexicon WordNet using correlation measures - Kendall’s tau and Spearman’s rho correlation coefficients. We further demonstrate the application of our tag weighting in summarization of web documents. We have proposed a summarization feature based on tag weights which can be used with some of the existing features in generating summaries. We have evaluated the generated summaries by comparing them with manually generated summaries to find how close they are to the manual summaries and hence more readable. Further, we also demonstrated the application of our tag similarity in tag search. Our experimental results proved that our proposed approaches are able to achieve good improvement over our baselines.

Abstract

A question may be either a linguistic expression used to make a request for information, or else the request itself made by such an expression. This information may be provided with an answer. Asking questions is a fundamental cognitive process that underlies higher-level cognitive abilities such as comprehension and reasoning. The ability to ask questions is the central cognitive element that distinguishes human and animal cognitive abilities. Questions are used from the most elementary stage of learning to original research. Question Generation (QG) is the task of automatically generating questions from various inputs such as raw text, database, or semantic representation. Ultimately, QG allows humans, and in many cases artificial intelligence systems, to understand their environment and each other. Research on QG has a long history in artificial intelligence, psychology, education, and natural language processing. The present work describes automatic Question Generation Systems that take natural language text as input and generate questions of various types and scope for the user. Our aim is to generate questions that assess the content knowledge that a student has acquired upon reading a text rather than vocabulary or grammar assessment or language learning. In this work, we have described two automatic question generation systems. Both these systems factor the QG process into several stages, enabling more or less independent development of particular stages. The QG system, described in chapter 2, generates questions automatically using discourse connec- tives for different question types. We described an end-to-end system that takes a document as input and outputs all the questions for selected discourse connectives. The selected discourse connectives include four subordinating conjunctions, since, when, because and although, and three adverbials, for example, for instance and as a result. Our system factors the QG process into two stages: content selec- tion (the text selected for question generation) and question formation (transformations on the content to get the question), Question formation module further has the modules of (i) finding suitable question type (wh-word), (ii) auxiliary and main verb transformations and (iii) rearranging the phrases to get the final question. The system has been evaluated for syntactic and semantic soundness of the question by two evaluators. The overall system has been rated 6.3 out of 8 for QGSTEC development dataset and 5.8 out of 8 for Wikipedia dataset. We have shown that some specific discourse relations are important, such as causal, temporal, result, etc., than others from the QG point of view. This work also shows that discourse connectives are good enough for QG and that there is no need for full fledged discourse parsing. We have generated questions using discourse connectives paving way for medium and specific scope questions. Cloze question generation (CQG) system, described in chapter 3, takes a document as input and outputs the important cloze questions. Our system factors the CQG system into three stages: (i) Sen- tence selection, (ii) Keyword selection and (iii) Distractor selection. A domain dependent approach is described for the distractor selection module of CQG system. The system is implemented for and tested on examples from the cricket sports domain. The system is evaluated using the guidelines described in this work. The accuracy of the distractors is 3.05 (Eval-1), 3.14 ((Eval-2) and 3.5 (Eval-3) out of 4. Main focus being on distractor selection, we have shown the influence of domain on the quality of distractors.

Abstract

After microprocessor clock speeds have levelled off, general purpose computing on Graphics Pro- cessing Units (GPGPUs) has shown some promise for the future High Performance Computing (HPC). This can be largely attributed to the performance per unit cost, performance per unit watt and CUDA, a programming model for GPU. For instance, for under $400, one can buy a GPU that can deliver more than a TFLOP of computing power while requiring less than 250 Wof power. It is therefore no surprise that 3 out of the top 5 supercomputers [71] use GPUs along with other computing elements. However, this comes at the expense of reinterpreting applications in a highly multithreaded manner. GPUs are good at exploiting massive data parallelism, and are well-suited for applications with regular memory access patterns and high arithmetic intensity. For several regular applications, this approach has been very successful [63, 48]. For example for dense matrix multiplication GPUs can perform upto 838GFlops/s. However, most applications in high performance computing are irregular in nature. Examples include list ranking [81], graph algorithms [53], sparse matrix computations [22], among others. Viability of using GPUs for accelerating these irregular workloads needs to be explored. In recent works, efforts are on to arrive at efficient implementations of irregular algorithms on the GPUs [81, 6], and on other recent multi-core architectures such as the Cell [4, 59, 51]. In this thesis we first accelerate Lanczos method for large sparse matrices, an algorithm for finding eigenvectors corresponding to least eigenvalues. We then use this in accelerating two important ap- plications namely spectral graph partitioning and image segmentation. For these applications our GPU imlementation shows a speedup upto 2.9 and 3.27 respectively when compared to highly optimized Intel MKL library implementation on multi-core. We then investigate sparse matrix routines from sparse blas level 2 and level 3. The investigated routines include sparse matrix multiplied with a dense vector / sparse matrix / dense matrix. Sparse Matrix Vector Multiplication (spmv) is the heart of many numerical computations and is notorious for sustaining low fractions of peak performance. This operation finds applications in solving system of linear equations, finding eigenvalues of a matrix to name a few. spmv becomes bottleneck in many of these methods. spmv performance is limited by the available memory bandwidth due to the low computation per data accessed. spmv further suffers from the memory access and thread execution constraints posed by the gpu and also from load balancing among threads. To address some of these challenges we proposed a run-time methodology to choose the right data structures to represent sparse matrices. Our methodology uses parameters that attempt to balance the load amongst threads and also identify the right kind of representation to use for storing the sparse matrix. Experimental results show that our technique improves the performance of the spmv kernel by an average of 25% when compared to the library implementation of spmv on GPU (cusp library). Sparse matrix-sparse/dense matrix multiplications, spgemm and csrmm, among other applications find usage in various matrix formulations of graph problems. GPU based supercomputers are presently experiencing severe performance issues on the Graph-500 benchmarks, a new HPC benchmark suite focusing on graph algorithms. Considering the difficulties in executing graph problems and the duality between graphs and matrices, computations such as spgemm and csrmm have recently caught the attention of HPC community. These computations pose challenges such as load balancing, irregular nature of the computation, and difficulty in predicting output size. It is even more challenging when combined with the GPU architectural constraints in memory accesses, limited shared memory, and thread execution. To address these challenges and perform the operations efficiently on a GPU, we evaluate three pos- sible variations of matrix multiplication (Row-Column, Column-Row, Row-Row) and perform suitable optimizations. Our experiments indicate that the Row-Row formulation outperforms the other formu- lations. Our row-row formulation of the spgemm operation performs up to 6x faster when compared to the highly optimized multi-core implementation in Intel MKL library. In a similar fashion, our GPU csrmm operation performs up to 5x faster when compared to corresponding implementation in the cusparse library, which outperforms the Intel MKL library implementation.

Abstract

In the last few decades there has been a tremendous increase in the infrastructure related to computing and collection of data. Tools such as sensors for moving objects, GPS (global positioning systems), satellite data and imagery, internet and web technologies are some of the many entities which have led to an exponential increase in the amount of data being collected these days. According to a recent study (http://tinyurl.com/2frbdeu), the total volume of electronic data stored worldwide reached 1.2 billion terabytes (a growth rate of 62% from 2009). At the same time there has also been an increase in the computing power of our systems. In particular, this information overload calls for new methods for querying large spatial datasets, since users are often not interested in merely retrieving a list of all data items satisfying a query, but would, instead, like a more informative “summary” of the retrieved items.
Orthogonal range searching has been a widely studied problem in the field of computational geometry and databases. In this problem, we need to preprocess a set S of n points lying in a d-dimensional space into a data structure so that given an axis-aligned orthgonal query box q (i.e. a rectangle and a cuboid in 2- and 3- dimensional space, respectively), we need to efficiently report (or count) the points of S lying inside q. For example, the set S could represent all the villages of India. A natural query would be to specify a region (which could be a district, a state etc.) on the map and to find out all the villages lying inside it. This is nothing but a range query. Traditionally, the researchers in computational geometry have been interested in building solutions for this problem which aim at coming up with worst-case efficient query time solutions, i.e., ensuring that the query time is low for all possible values of the query. Range trees are an extremely popular example. On the other hand, the researchers in database community try to come up with practical solutions which are optmized to work well for the average case queries (with the assumption that the worst-case query will occur rarely). R-trees and R*-trees are commonly used structures in the database literature.
In many applications a more general form of a range searching problem arises: Here the points in S come aggregated in disjoint groups and of interest are questions regarding the intersection of q with the groups rather than with the points itself. q intersects a group if and only if it intersects some point in the group. For convinience, each group is associated with a different color and all the points in the group are imagined to have that color. Then, in the colored reporting (resp., colored counting) problem, we want to report (resp., count) the distinct colors intersected by q. In the dynamic setting, a point of some (possibly new) color is inserted in S or a point in S is deleted. In this thesis we shall consider the query region q to be an axis-aligned orthognal query region and label the problem as orthogonal colored range searching (OCRS). Note that the colored problem reduces to the standard range searching problem when each color class has cardinality 1. This query has applications in various diverse fields, most notable being databases and GIS. For instance, in an SQL database, a GROUP-BY query is one of the most useful queries and OCRS is a geometric representation of a GROUP-BY query.
Till now most of the work on OCRS and related geometric problems has been done by the computational geometry researchers. The issue with those solutions is that the space occupied by the data structures increases exponentially in terms of dimension size. In an internal memory setting the amount of free space available is the main constraint, so these solutions might not scale up well for large datasets with high dimensionality. Therefore, the objective in this thesis is to answer OCRS query on internal memory by building a near-linear space data structure while maintaining low query time. We also handle insertion and deletion of points.
In this thesis we propose a new technique named BB K-d technique to answer OCRS query on internal memory. The space occupied by the data structure is O(n log ), where  is the number of unique colors in the dataset. We considered K-d tree and augmented with additional information to speed up the query. The performance of the proposed algorithm (query response time and space occupied) has been evaluated through extensive experiments and comparison with two base-line brute-force algorithms is presented. All the factors affecting the query time of the BB k-d technique have been thouroughly tested experimentally (such as number of colors, size of query box, data distribution). Real world and synthetic datasets have been used to perform these experiments. The query time of the BB K-d technique varies minimally irrespective