Abstract

Trust is a complex human attitude that forms a vital, yet common component of nearly every aspect of human social behaviour. As a concept, it has been studied in various disci- plines of humanities in a myriad of different ways, while its use in computer science domains has met with limited degrees of success. Over the years, it has been observed however, that trust-aware models offer relevance, transparency and usability in real-world applications. With computational systems becoming increasingly intelligent, and web-based social networks hav- ing become ubiquitous in today’s global society, contemporary new dimensions of trust have emerged. The transformation of the internet into a social web has made it important to under- stand what trust means in the online world. In this thesis, we aim to extend a formal theory of trust in the context of social media (in an attempt to bridge the gap between its understanding in the humanities and computer science) and explore its viability in designing better socio- technical systems. We first detail the intricate nature of trust based on theories in philosophical literature. We discuss how trustworthiness of the trustee, risks, expectations of the trustor, motives, incentives and skills factor into the attitude that is trust. We discuss ontological and epistemological per- spectives such as where trust exists, how do we know what we trust and where its value comes from. We also study its relation to the utilitarian moral theory to see how we can maximize benefits through good actions. Grounded in these ideas, we argue for the important role played by it in the effective working of large-scale social networks. We outline a novel multi-class taxonomical framework comprising of personal, social and functional elements of trust. We identify how individual traits of users, collective behaviours of communities and the structural capabilities of the technologies, all contribute to the creation of trust. We expound on the in- tricate relationships between these three elements and show how institutions, digital semiotics and value-aligned technologies form strong theoretical and philosophical underpinnings in the design of these systems. vii viii Having built the framework, we then depict its feasibility and relevance to real-world sys- tems through a case study of Wikipedia. We investigate how the different elements of trust manifest themselves in Wikipedia. We illustrate themes such as purpose, content, systems de- sign, tasks, etc. and demonstrate the usefulness of the taxonomy in understanding where and how trust originates, and why readers and editors alike have faith in Wikipedia. And lastly, we use elements of the framework along with machine learning and tensor factorization meth- ods to propose a novel, hybrid, trust-based recommendation model to suggest a personalized list of items to users. We present experimental evaluations of our model on a dataset of TED videos and show that it outperforms standard existing collaborative filtering and trust-based approaches. Moreover, subjectively speaking, it scores high on user satisfaction based on pop- ularity, diversity and freshness

Abstract

Geographical Information Systems(GIS) is a powerful, ubiquitous tool that can be seen in various domains of today's fast-moving and highly technological landscape. With the rising needs and uses of GIS data visualization system, such as smart city planning, environment and climate change monitoring, weather simulation, transportation and so forth, the Geospatial vec- tor visualization research, application and technology has become prevalent. Large amounts of data can be visualized on an interactive platform which is one of the most appealing and useful abilities of GIS. High powered computers can visualize large data sets, change element of the display easily, give any visual effects for better view and also make suitable interpretations. Recent Geospatial data visualization systems have been predominantly through applications that are installed and run in a desktop environment. The drawbacks with the desktop application model is that it is tightly coupled to the desktop environment attributes like operating system and hardware of the system. Desktop applica- tion has the limitations to be used on multiple devices like smartphones, tablets and personal computers simultaneously. Also, it lacks the scope to collaborate with the other users. To solve the above problems a client-server model has been adopted where data on a single sys- tem can be accessed, manipulated and visualised on different clients without any environment dependencies. Over the last decade, this server-client model for data handling, data rendering and visualization has been the most prevalent approach in WebGIS. But the above paradigm of WebGIS gives limited capabilities and functionalities to the client to handle the Geospatial data making it dumb. Although the client-side technologies have become functionally more powerful over the recent years, the above model has largely ignored it and is still in a mode of server-dominant computing paradigm. Given the current scenario of the GIS visualization systems, an attempt has been made to develop and demonstrate LSIViewer - a simple, easy and robust online Geospatial data visuali- sation system for the user's own data that harness the client's capabilities for data rendering and user-interactive styling, with a reduced load on the server. The technologies chosen to build this system makes the application extensible and scalable. The architecture of LSIViewer is based on client-server model where role of the server is to provide the instance of the client ap- plication, act as an adapter and convert the input vector data into a GeoJSON format, compress the GeoJSON encoded data and send it as a response to the client. GDAL/OGR, a popular open source format translator GIS library, is used in conversion of vector format to GeoJSON. The transmission of GeoJSON data between client and server is optimized by reducing the information size using efficient compression method that is supported in all the web-browsers. The client decompresses the encoded response and render the map on HTML5 canvas via JavaScript. The performance analysis on the developed system included various tests that were run on a range of vector datasets. These tests showed that the time taken to render the vector data using LSIViewer is comparable to a desktop GIS application, QGIS, over an identical system con- figuration. All the web browsers that support HTML5 give the capability of rendering vector data to the client, making the developed application a platform-independent and installation- free toolkit. This indicates that any device with a web browser has the capability to visualize vector data without the need of a full-scale GIS desktop application. Eventually, the developed system can be extended to build an enterprise level collaborative GIS platform for users and developers to share and analyze their data. This online visualization tool is just an inception, opening the gates to a whole new horizon of things that can be possible through WebGIS.

Abstract

The subset sum problem, also referred to as SSP, is an NP-Hard computational problem. SSP has its applications in broad domains like cryptography, number theory, operations research and complexity theory. The most famous algorithm for solving SSP is Backtracking Algorithm which has exponential time complexity. Therefore, our goal is to design and develop better alternate enumeration techniques for faster generation of SSP solutions. Given the set of first n natural numbers which is denoted by X n and a target sum S, we propose various alternate enumeration techniques which find all the subsets of X n that add up to sum S. In this thesis, we present the mathematics behind this exponential problem. We analyze the distribution of power set of X n and present formulas which show definite patterns and relations among these subsets. We introduce three major distributions for power set of X n : Sum Distribution, Length-Sum Distribution and Element Distribution. These distributions are prepossessing procedures for various alternate enumeration techniques for solving SSP. We propose novel algorithms: Subset Generation using Sum Distribution, Subset Generation using Length-Sum Distribution, Basic Bucket Algorithm, Maximum and Minimum Frequency Driven Bucket Algorithms and Local Search using Maximal and Minimal Subsets for enumerating SSP. We compare the performance of these approaches against the traditional backtracking algorithm. The efficiency and effectiveness of these algorithms are presented with the help of these experimental results. Furthermore, we studied the extra subsets generated by various algorithms to get the complete solution for subset sum problem. Finally, we present a conjecture about upper bound on the number of subsets that has to be enumerated to get all solutions for Subset Sum Problem.

Abstract

A Question Answering system constructs its answers by querying a data resource. In this thesis, we develop an architecture for a multi-lingual dialog based QA system using PurposeNet based Ontology as the data resource. We have handled two unrelated domains, one of which is an open domain (recipe) while the other is a closed domain (MMTS) and the QA system is reusable with few domain based changes. In this cross-lingual setup we have considered Hindi as the user language (question-input and answer-output are in Hindi) while the Ontology is written in English language. We discuss the creation of Ontological resource in both the domains. The Ontological structures for both domains was highly influenced by PurposeNet architecture. Data for both the domains exhibit a different characteristic. While a major chunk of the MMTS domain data could be easily extracted by automated means, extracting recipe domain data was a layered approach. The action and artifact Ontology of the MMTS domain are created separately, artifact Ontology is created using automated means while action Ontology is manually populated. For recipe domain, we populated the resource using recipe blog data and then executed a post-processing step, to bring a more unified structure to the Ontology. Question analysis is a very important aspect of a QA system. We have tried to semantically and structurally classify questions in Hindi. Structural classification helps us in parsing the questions correctly and hence identify the question arguments correctly. Semantic classification helps us in mapping the question arguments to the Ontology and hence extract the answers from the data resource. We also study polysemous question types (kya and kaise) in Hindi. These questions are partly tackled by the dialog system which is integrated in the QA system. We give an architecture of a QA system using PurposeNet based Ontology created in OWL, with Pellet reasoner (for data inference). The design of the QA system ensures a multilingual architecture and domain independence. After understanding the question type and its requirements, we create Sparql queries, answers of which are extracted from the knowledgebase. We have handled all kinds of question types giving a major emphasis on non-factoid questions including why and how. The structure of PurposeNet helps in identifying the answers to these questions effectively. We provide a graph based algorithm for answering these question types efficiently. As said earlier we also support the QA system with a dialog system which can interact with the user before, during or after a question answering cycle. If a QA system finds an ambiguity, incompleteness or incorrectness in a question, it asks for user interference using the dialog module. We maintain the state of the question and start processing from this state on user’s input to efficiently process questions faster. To test the premise of domain-independence of the QA system, we first create it for MMTS domain and then extended to recipe domain. Testing against gold data gives us a decent accuracy of 76.2% and 63.75% for MMTS and recipe domains respectively. The answers we receive from the QA system is cross-verified by human evaluators on correctness and readability. The results are extremely promising with scores of 2.32/3.00 and 2.25/3.00 respectively for both the domains.

Abstract

Social media sites such as Twitter and Facebook have emerged as popular tools for people to express their opinions and sentiments on various topics. Large amount of data provided by these media is extremely valuable for mining trending topics and events. However, this massive volume also dictates that the mining approach be efficient in terms of computations and storage. In this thesis, we propose an efficient, scalable system to detect events from tweets. The system does not employ any Twitter-specific features, and thus, can be readily adapted to any other social media site. Since tweets are very short and diverse in nature, traditional approaches, meant for typical long/well-formatted documents, can not be applied to tweets. Tweets are written informally with a lot of abbreviations and mistakes. Since tweets are very short, statistical concepts like tf.idf can not be directly used on them. Our approach detects events by exploring their textual and temporal components. The system does not require any target entity to be specified; it automatically detects generic events from a set of tweets. The key components of our system are an extraction scheme for event representative keywords, an efficient storage mechanism to store their appearance patterns, and a hierarchical clustering technique based on the common co-occurring features of keywords. We evaluate our system on two data-sets, one provided by VAST challenge 2011 and other published by US based users in January 2013. Our approach is efficient in terms of computational time and memory, and achieves high precision across two different datasets. The detected events are easy to interpret, and encompass a wide range of topics.

Abstract

Sponsored search is one of the most dominant modes of online advertising on the web. In sponsored search, advertisers bid on relevant keywords to advertise their product. For an incoming search query, advertisements from the ad campaigns containing the query keywords are shown along with the search results. If multiple advertisers demand to be shown on the same query’s results page, they are ranked for the allocation of ad space. The ranking is determined by multiple factors including the bid amount of the advertiser on the query keywords, relevance of ad content to the search query, Click-Through-Rate (CTR) and budget of the advertiser. The ecosystem of sponsored search has three main stakeholders - search engine, advertisers and users. Search engines aim to maximize the revenue by showing ads. Advertisers want to maximize the reach of their service or increase the sales. Users see advertisements on the search results page. Some of the key research challenges in sponsored search are query-ad relevance, click-through-rate prediction, optimal auction design, optimum utilization of ad space of rare (tail) queries and click-fraud detection. In this thesis, related to sponsored search, we have investigated approaches to exploit the ad space of tail queries. It is well established that search queries tend to follow a heavy-tailed Zipf distribution wherein a large fraction of queries occur too infrequently. Such infrequent query set is called long tail. Advertising on long tail queries is challenging as long tail queries are encountered rarely which makes them hard to interpret for sponsored search. Also, it has been observed that during keyword auctions, advertisers tend to bid for the head keywords to reach more users. This creates a high demand for the head query keywords and little or no demand for the tail query keywords. The long tail phenomenon also makes it quite difficult for an advertiser to capture the relevant keywords from the long tail. The above stated factors result in under-utilization of a significant amount of the ad space provided by tail queries in sponsored search which is identified as the research issue. We propose two approaches for the utilization of ad space of tail queries by proposing that instead of bidding on keywords, advertisers should bid upon high level concepts. In the first approach, we propose bidding on concepts by organizing concepts into a two level taxonomy. In the second approach, we propose a generalized approach by considering organization of concepts into a multi-level taxonomy. In the first approach, we have proposed an improved framework to cover more advertisers by exploiting the notions of coverage and concept taxonomy based on the log data of search queries. The proposed framework allows to form the distinct groups of keywords such that each group of keywords could be allocated to meet the demands of the advertiser. We model each search session as a transactionand queries occurring in a session form the items of the transaction. Coverage patterns are then mined from these session-based transactions. The coverage patterns fuse tail keywords together into multiple groups to maximize the unique visitors and two-level concept taxonomy ensures that groups are meaningful. A comprehensive framework has been proposed to map the extracted coverage patterns and the demands of the advertisers to allocate incoming queries to advertisers. We have conducted experiments on a real world dataset of AOL web search engine and found out that it is possible to meet the demands of more advertisers with the proposed approach. It was found out that the proposed approach is able to provide diverse but meaningful group of keywords which allows the advertiser to display advertisement to appropriate users based on the requirements. In the second approach, we propose that advertisers should bid upon high level concepts represented by a multi-level taxonomy instead of search keywords during ad space auctions. Advertisers are free to bid on any node of the taxonomy. Bidding on any node in the taxonomy provides more flexibility to the advertisers to target the potential consumers. However, to allocate children nodes of bidding nodes to advertisers, the flat model of coverage patterns cannot be used. To address the issues of interdependency of concepts on each other, we exploit search query logs and a taxonomy to extract level-wise coverage patterns. We further propose an end-to-end architecture which takes search query logs, axonomy and advertising demands as inputs and allocates an incoming search query to the advertisers. The corresponding architecture is used to perform allocation of incoming queries to advertisers for sponsored search. Experiments on a real world dataset of AOL search query logs show improvement in performance with respect to ad space utilization and reach of the advertisements. Overall, we have proposed two approaches for improving the utilization of ad

Abstract

Autonomous Navigation in indoor environment where human and robot occupy the same workspace is a challenging problem, robots should behave in a socially acceptable way otherwise they will cause discomfort for humans which could possibly lead to confusion and disastrous results. In recent years autonomous navigation systems have been a primary focus in robotics. A wheelchair is a mechanical device that can often assist people with disabilities. It comes under Rehabilitation Technologies or assistive technologies. It effectively uses wheels and mechanical support to overcome a loss of legs or leg control. Manual wheelchairs can be operated by persons who can use their upper body or someone available to assist. They can help people who have motor control problems, spinal injuries and amputation. An autonomous wheel chair can also help people who have lost motor control of their legs as well as their arms. They can help in moving patients in hospitals as well as moving heavy equipments in a warehouse like environment. The thesis contributes in the following ways. Firstly, we develop a wheel chair capable of autonomously navigating in an indoor environment. We also develop a novel approach to predict human intentions and introduce a probabilistic variant of time scaled collision cone constraints. These constraints allows us to relate space of collision free velocities to an associated confidence measure. Secondly, it develops an optimization framework for extracting a specific solution from the entire solution space of collision free velocities, depending on the factors such as distance from goal, probability of collision , robots kinematics and dynamic constraints such as turning radius, maximum acceleration and maximum velocity.

Abstract

In recent years, there has been a surge in finding vulnerabilities in browsers. This is mainly attributed to the ability of browser to host various services by gluing different applications. However, most of the research has gone into addressing web-related vulnerabilities like, XSS, SSL, SQLi etc. In this work, we focus on other type of vulnerabilities namely low-level or implementation level bugs. We specifically target embedded interpreters in browsers, as these software process codes that may come from a malicious site. Our contribution is to advance state of the art in interpreter testing. Fuzzing is an automated black box testing technique used for finding security vulnerabilities in the software by providing random data as input. Several frameworks for typical applications (e.g. network protocols, files formats, API‘s, applications and other targets) have been written so far. However, for interpreter testing, very few fuzzers exist. We present an automated evolutionary fuzzing technique to find bugs in JavaScript interpreters. However, in the case of an interpreter, fuzzing is challenging because the inputs are piece of codes that should be syntactically / semantically valid to pass the interpreter’s elementary checks. On the other hand, the fuzzed input should also be uncommon enough to trigger exceptional behavior in the interpreter, such as crashes, memory leaks and failing assertions. In our approach, we use evolutionary computing techniques, specifically genetic programming, to guide the fuzzer in generating uncommon input code fragments that may trigger exceptional behavior in the interpreter. We implement a prototype named IFuzzer to evaluate our technique on real-world examples. IFuzzer uses the language grammar to generate valid inputs. We applied IFuzzer first on an older version of the JavaScript interpreter of Mozilla (to allow for a fair comparison to existing work) and found 40 bugs, of which 12 were exploitable. On subsequently targeting the latest builds of the interpreter, IFuzzer found 17 bugs, of which four were security bugs.

Abstract

The thesis presents end-to-end frameworks for joint semantic and motion segmentation in outdoor dynamic scenes in both monocular and stereo setup. Dynamic scene understanding is a challenging problem and motion segmentation plays a crucial role in solving it. Incorporating semantics and motion enhances the overall perception of the dynamic scene. For applications of outdoor robotic navigation, joint learning methods have not been extensively used for extracting spatio-temporal features or adding different priors into the formulation. The task becomes even more challenging without stereo information being incorporated. The thesis proposes an approach to fuse semantic features and motion clues using CNNs, to address the problem of monocular semantic motion segmentation. We deduce semantic and motion labels by integrating optical flow as a constraint with semantic features into dilated convolution network. The pipeline consists of three main stages i.e Feature extraction, Feature amplification and Multi Scale Context Aggregation to fuse the semantics and flow features. Our joint formulation shows significant improvements in monocular motion segmentation over the state of the art methods on challenging KITTI tracking dataset. The focus in the second part of the thesis is temporally consistent joint semantic and motion segmentation. Segmenting moving objects in a video sequence has been a challenging problem and critical to outdoor robotic navigation. While recent literature have laid focus on regularizing object labels over a sequence of frames, exploiting the spatio-temporal features for motion segmentation has been scarce. Particularly in real world dynamic scenes, existing approaches tend to fail in segmenting moving objects with large camera motion. In this thesis, we present an approach for exploiting semantic information and temporal constraints in a joint framework for motion segmentation in a video. We propose a formulation for inferring per-frame joint semantic and motion labels using semantic potentials from dilated CNN framework and motion potentials from depth and geometric constraints. We integrate the potentials obtained into a 3D(space-time) fully connected CRF framework with overlapping/connected blocks. We solve for a feature space embedding in the spatio-temporal space by enforcing temporal constraints using optical flow and long term tracks as a least-squares problem. We evaluate our approach on KITTI Tracking benchmark and demonstrate results superior to the state-of-the-art in motion segmentation.

Abstract

Natural language processing is a field of artificial intelligence and computational linguistics that aims at bridging the gap between human beings and computers. It deals with processing natural languages in various forms like speech and text. Processing a natural language happens at various levels i.e, word, phrase, sentence, syntax, semantics and discourse. In this work we present our efforts at making advancements at syntax and semantic levels in dependency parsing. Dependency parsing involves discovering relationships between words in a given sentence so as to understand it better. We begin this thesis with a comparative error analysis of two parsers - MALT and MST on Telugu Dependency Treebank data. We discuss the performance of both the parsers in relation to the Telugu language and then talk in detail about both the algorithmic issues of the parsers as well as the language specific constraints of Telugu. We follow this by proposing a semi-supervised approach by introducing clustered word embedding based features into dependency parsing. This involves a simple and effective semi-supervised method to introduce features that incorporate dependency label clusters derived from a large annotated corpus into data driven dependency parsing. We demonstrate the effectiveness of the approach in a series of experiments on Hindi language data. We then propose a neural network based classifier voting approach to dependency parsing using multiple classifiers as component systems in an ensemble and a neural network algorithm as an oracle. We show significant improvements over the best component systems for both transition-based and graph-based dependency parsing.